具有置换长度参数的javascript置换生成器

Question

我在那里看到了一些发电机,但它们都制成了一个平方矩阵.例如,你给它一个三个项目的列表,它将假设长度的输出也是三个.但是,我想指定项目和长度.

声音就像一个简单的问题,不能相信没有可用的库.如果那里有一个经过测试的库,我想避免自己写这个.任何建议都会很棒.

我发现的例子

var list = 'abc';
perms = permutations(list);
//you cannot define the length

例

var list = 'abc';
var length = 3;

perms = permutations(list,length);

console.log(perms);

/* output
a,a,a
a,b,c
a,b,a
a,c,a
c,a,a
...
*/

我希望能够改变长度,并相应地创建排列

length = 2

a,a
a,b
b,b
b,a

length = 4

a,a,a,a 
a,a,a,b
....

Answer 1

您可以将长度想象为表示插槽数.考虑到N是初始列表中的元素数,每个插槽都有N种可能性.因此,给定三个值[1,2,3],您将得到总3 x 3 x 3 = 27排列.

这是我的尝试.包括评论!

var list = [1,2,3];

var getPermutations = function(list, maxLen) {
    // Copy initial values as arrays
    var perm = list.map(function(val) {
        return [val];
    });
    // Our permutation generator
    var generate = function(perm, maxLen, currLen) {
        // Reached desired length
        if (currLen === maxLen) {
            return perm;
        }
        // For each existing permutation
        for (var i = 0, len = perm.length; i < len; i++) {
            var currPerm = perm.shift();
            // Create new permutation
            for (var k = 0; k < list.length; k++) {
                perm.push(currPerm.concat(list[k]));
            }
        }
        // Recurse
        return generate(perm, maxLen, currLen + 1);
    };
    // Start with size 1 because of initial values
    return generate(perm, maxLen, 1);
};

var res = getPermutations(list, 3);
console.log(res);
console.log(res.length); // 27

fiddle

Answer 2

如果您正在寻找基于性能的答案，您可以使用数组的长度作为数字基数，并基于此基数访问数组中的元素，基本上用数组中的值替换基数中的实际值，并使用计数器按顺序访问每个值：

const getCombos = (arr, len) => {
  const base = arr.length
  const counter = Array(len).fill(base === 1 ? arr[0] : 0)
  if (base === 1) return [counter]
  const combos = []
  const increment = i => {
    if (counter[i] === base - 1) {
      counter[i] = 0
      increment(i - 1)
    } else {
      counter[i]++
    }
  }

  for (let i = base ** len; i--;) {
    const combo = []
    for (let j = 0; j < counter.length; j++) {
      combo.push(arr[counter[j]])
    }
    combos.push(combo)
    increment(counter.length - 1)
  }

  return combos
}

const combos = getCombos([1, 2, 3], 3)
console.log(combos)

对于较小的用例，如上面的示例，性能应该不是问题，但是如果您要将给定数组的大小从 3 增加到 10，并将长度从 3 增加到 5，那么您已经从 27 ( 3 ³ ) 组合到 100,000 (10 ⁵ )，您可以在这里看到性能差异：