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

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

您可以使用递归生成器函数来完成大部分工作。 Array.from生成器将结果填充到数组中。let vec = ['a', 'b', 'c'];function* combo(n, k = 0, prefix = []) {&nbsp; if (n == 0) yield prefix;&nbsp; else for (let i = k; i < vec.length; ++i) {&nbsp; &nbsp; yield* combo(n - 1, i, [...prefix, vec[i]]);&nbsp; }}let test = Array.from(combo(3));console.log(JSON.stringify(test));

Answer 2

更新版本受Wyck 解决方案的启发，我制作了另一个版本。这个干净多了。它使用与 Wyck 几乎相同的技术，但跳过了生成器代码。const makeBags = (n, xs, prefix = []) =>&nbsp;&nbsp; n == 0&nbsp; &nbsp; ? [prefix]&nbsp; &nbsp; : xs .flatMap ((v, i) => makeBags (n - 1, xs .slice (i), [...prefix, v]))console .log (&nbsp; JSON .stringify (makeBags (3, ['a', 'b', 'c'])))

Answer 3

请注意，尽管附加默认参数看起来可能用于尾调用优化，但此代码尚未准备好用于 TCO。我的第一个解决方案这是一个简单的递归解决方案，如果字母列表为空，则返回空列表，否则确定要包含多少个首字母，并在剩余字母上重复。我不知道这是否在任何意义上都比原始版本更优化，除了代码清洁度方面。但它更通用，接受一个参数来告诉输出中有多少项与列表中的项数分开。const range = (lo, hi) =>&nbsp;&nbsp; [...Array (hi + 1 - lo)] .map ((_, i) => i + lo)const prefixAll = (p, xs) =>&nbsp;&nbsp; xs .map (x => [...p, ...x])const groupsOf = (n, [x = undefined, ...xs]) =>&nbsp;&nbsp;&nbsp; x == undefined&nbsp; &nbsp; ? []&nbsp; &nbsp; : [&nbsp; &nbsp; &nbsp; &nbsp; Array (n) .fill (x),&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; ...range (1, n) .flatMap (i => prefixAll (Array (n - i) .fill (x), groupsOf (i, xs)))&nbsp; &nbsp; &nbsp; ]console .log (&nbsp; groupsOf (3, ['a', 'b', 'c']))

Answer 4

range 是一个简单的效用函数： range(3, 10) //=> [3, 4, 5, 6, 7, 8, 9, 10]prefixAll是一个助手，如果愿意，可以内联。它只是在第二个参数中的每个数组前面加上第一个参数中的值。prefixAll(['a', 'b'], [['c'], ['c', 'c'], ['c', 'd']])&nbsp;//=> [['a', 'b', 'c'], ['a', 'b', 'c', 'c'], ['a', 'b', 'c', 'd']]虽然这并不太复杂，但几乎可以肯定有一个更好的解决方案，它不涉及Array (n) .fill (x)，将递归步骤作为一个简单的flatMap. 但我现在没有时间弄清楚。