如何优化包含重复值的组合？

Question

我有一个包含三个值的数组。

["a","b","c"]

我正在尝试使用上述数组创建以下组合。

0:  ["a", "a", "a"]
1:  ["a", "a", "b"]
2:  ["a", "a", "c"]
3:  ["a", "b", "b"]
4:  ["a", "b", "c"]
5:  ["a", "c", "c"]
6:  ["b", "b", "b"]
7:  ["b", "b", "c"]
8:  ["b", "c", "c"]
9:  ["c", "c", "c"]

我写的代码成功了。但是代码没有优化。我怎样才能使这段代码简单。

function test(arr, arr2=[], result=[]) {
    if (arr2.length < 3) {
        let proxy_arr = [...arr];
        Object.keys(proxy_arr).forEach(index=>{
            if (!test(arr, [...arr2].concat(proxy_arr[index]), result)) {
                result.push([...arr2].concat(proxy_arr[index]));

            } else {
                //debugger;
                arr = arr.slice(1);
            }

        }
        );
        return result;

    }
    return false;
}
result = test(["a", "b", "c"]);

Answer 1

你正在学习置换算法。

这里是不重复的解决方案

function permutateWithoutRep(permutationOptions) {
  if (permutationOptions.length === 1) {
    return [permutationOptions];
  }

  // Init permutations array.
  const permutations = [];

  // Get all permutations for permutationOptions excluding the first element.
  const smallerPermutations = permutateWithoutRep(permutationOptions.slice(1));

  // Insert first option into every possible position of every smaller permutation.
  const firstOption = permutationOptions[0];

  for (let permIndex = 0; permIndex < smallerPermutations.length; permIndex += 1) {
    const smallerPermutation = smallerPermutations[permIndex];

    // Insert first option into every possible position of smallerPermutation.
    for (let positionIndex = 0; positionIndex <= smallerPermutation.length; positionIndex += 1) {
      const permutationPrefix = smallerPermutation.slice(0, positionIndex);
      const permutationSuffix = smallerPermutation.slice(positionIndex);
      permutations.push(permutationPrefix.concat([firstOption], permutationSuffix));
    }
  }

  return permutations;
}

console.log(permutateWithoutRep(['a', 'b', 'c']))

有重复：

function permutateWithRep(
  permutationOptions,
  permutationLength = permutationOptions.length,
) {
  if (permutationLength === 1) {
    return permutationOptions.map(permutationOption => [permutationOption]);
  }

  // Init permutations array.
  const permutations = [];

  // Get smaller permutations.
  const smallerPermutations = permutateWithRep(
    permutationOptions,
    permutationLength - 1,
  );

  // Go through all options and join it to the smaller permutations.
  permutationOptions.forEach((currentOption) => {
    smallerPermutations.forEach((smallerPermutation) => {
      permutations.push([currentOption].concat(smallerPermutation));
    });
  });

  return permutations;
}

console.log(permutateWithRep(['a', 'b', 'c']))

Answer 2

更新版本

受到的启发，又做了一个版本。这个要干净得多。它使用与 Wyck 相同的技术，但跳过了生成器代码。

const makeBags = (n, xs, prefix = []) => 
  n == 0
    ? [prefix]
    : xs .flatMap ((v, i) => makeBags (n - 1, xs .slice (i), [...prefix, v]))

console .log (
  JSON .stringify (makeBags (3, ['a', 'b', 'c']))
)

请注意，虽然额外的默认参数看起来可能用于尾调用优化，但此代码尚未为 TCO 做好准备。

我的第一个解决方案

这是一个简单的递归解决方案，如果字母列表为空则返回空列表，否则确定要包含多少首字母并在剩余字母上重复。我不知道这是否在任何意义上都比原始版本更优化，除了代码清洁度方面。但它更通用，接受一个参数来告诉输出中有多少项与列表中的项数分开。

const range = (lo, hi) => 
  [...Array (hi + 1 - lo)] .map ((_, i) => i + lo)

const prefixAll = (p, xs) => 
  xs .map (x => [...p, ...x])

const groupsOf = (n, [x = undefined, ...xs]) =>  
  x == undefined
    ? []
    : [
        Array (n) .fill (x), 
        ...range (1, n) .flatMap (i => prefixAll (Array (n - i) .fill (x), groupsOf (i, xs)))
      ]

console .log (
  groupsOf (3, ['a', 'b', 'c'])
)

range 是一个简单的效用函数：range(3, 10) //=> [3, 4, 5, 6, 7, 8, 9, 10]

prefixAll 是一个助手，如果愿意，可以将其内联。它只是在第二个参数中的每个数组前面加上第一个参数中的值。

prefixAll(['a', 'b'], [['c'], ['c', 'c'], ['c', 'd']]) 
//=> [['a', 'b', 'c'], ['a', 'b', 'c', 'c'], ['a', 'b', 'c', 'd']]

虽然这不是太复杂，但几乎可以肯定有一个更好的解决方案，它不涉及 Array (n) .fill (x)，将递归步骤作为一个简单的 flatMap。但我现在没时间弄清楚。

Answer 3

您可以使用递归生成器函数来完成大部分工作。 Array.from 生成器会将结果填充到数组中。

let vec = ['a', 'b', 'c'];

function* combo(n, k = 0, prefix = []) {
  if (n == 0) yield prefix;
  else for (let i = k; i < vec.length; ++i) {
    yield* combo(n - 1, i, [...prefix, vec[i]]);
  }
}

let test = Array.from(combo(3));

console.log(JSON.stringify(test));

如何优化包含重复值的组合？

How can I optimize the combination that contains repeated values?

javascript

optimization

recursion

combinations

repeat

更新版本

我的第一个解决方案