具有排列长度参数的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
....

- uptownhr

---

你目前做了什么？ - Praveen Kumar Purushothaman

长度是什么意思？ - ProllyGeek

能否检出那段代码？ - Praveen Kumar Purushothaman

@ProllyGeek 他的意思是生成排列的长度。 - Praveen Kumar Purushothaman

如果我们提供一个列表，那么我们可以更改长度吗？这有意义吗？ - ProllyGeek

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

- linstantnoodles

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⁵），你可以在这里看到性能差异：

- Kobe

Answer 3

我写了一个小型的库，使用生成器为您提供具有自定义项目和元素数量的排列组合。 https://github.com/acarl005/generatorics

const G = require('generatorics')

for (let perm of G.permutation(['a', 'b', 'c'], 2)) {
  console.log(perm);
}
// [ 'a', 'b' ]
// [ 'a', 'c' ]
// [ 'b', 'a' ]
// [ 'b', 'c' ]
// [ 'c', 'a' ]
// [ 'c', 'b' ]

- Andy Carlson

---

这是一个不错的库。 - Mr. Polywhirl