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

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 = []) {

  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));

Answer 2

更新版本

受Wyck 解决方案的启发，我制作了另一个版本。这个干净多了。它使用与 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']))

)

Answer 3

请注意，尽管附加默认参数看起来可能用于尾调用优化，但此代码尚未准备好用于 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'])

)

Answer 4

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. 但我现在没有时间弄清楚。