Javascript中的Itertools.combinations

Question

在JavaScript中有没有类似于Python的itertools的库？我对排列和组合特别感兴趣。

我没有使用Node.js。

我想这样做：

array = ['a', 'b', 'c', 'd'];

//return non-duplicate combinations of length 2
['a', 'b']
['a', 'c']
['a', 'd']
['b', 'c']
['b', 'd']
['c', 'd']

谢谢！:)

Answer 1

您可以使用递归方法来获取指定大小的给定数组的排列。

​

function getPermutations(array, size) {

    function p(t, i) {
        if (t.length === size) {
            result.push(t);
            return;
        }
        if (i + 1 > array.length) {
            return;
        }
        p(t.concat(array[i]), i + 1);
        p(t, i + 1);
    }

    var result = [];
    p([], 0);
    return result;
}

var array = ['a', 'b', 'c', 'd'];

console.log(getPermutations(array, 2));

.as-console-wrapper { max-height: 100% !important; top: 0; }

​

Answer 2

您可以使用我的es-iter库，它几乎是Python的itertools的一对一的端口，但是是以JS的方式。

https://github.com/abozhilov/ES-Iter#combinationsr

Answer 3

我喜欢itertools.combinations并且想要一个节省内存的JavaScript

生成函数，但无法快速找到可接受的库，因此我使用了自己的库。

它在TypeScript中(用来帮助我记账)，但我将在底部附加转换后的JavaScript。

function* range(start: number, end: number) {
  for (; start <= end; ++start) { yield start; }
}

function last(arr: T[]) { return arr[arr.length - 1]; }

function* numericCombinations(n: number, r: number, loc: number[] = []): IterableIterator {
  const idx = loc.length;
  if (idx === r) {
    yield loc;
    return;
  }
  for (let next of range(idx ? last(loc) + 1 : 0, n - r + idx)) { yield* numericCombinations(n, r, loc.concat(next)); }
}

function* combinations(arr: T[], r: number) {
  for (let idxs of numericCombinations(arr.length, r)) { yield idxs.map(i => arr[i]); }
}

所有的黑魔法都在numericCombinations函数，它是一个递归生成器-请参阅

yield*..。实际的combinations函数只是包装它以匹配Python API。

我可以把这个放在一个.ts文件，并将以下内容放在它的底部：

if (module === require.main) {
  const shorts = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'.split('');
  let i = 0;
  for (let o of combinations(shorts, 7)) { i++; }
  console.log(i);
}

和Node打印输出133784560在我2015年的老式笔记本电脑上，只需不到2.5分钟，内存使用量就会降到最低。也就是说，它生成了所有

100 3400万您可以从一副52张扑克牌中选择7张牌(即，所有完整的德州手中的牌)，而不会增加内存负担或过度嵌套递归函数调用。

(Python3可以在20秒内完成此操作，速度比…快7倍对上述欢迎的加速。)

JavaScript代码：

function* range(start, end) {
  for (; start <= end; ++start) { yield start; }
}
function last(arr) { return arr[arr.length - 1]; }
function* numericCombinations(n, r, loc = []) {
  const idx = loc.length;
  if (idx === r) {
    yield loc;
    return;
  }
  for (let next of range(idx ? last(loc) + 1 : 0, n - r + idx)) { yield* numericCombinations(n, r, loc.concat(next)); }
}
function* combinations(arr, r) {
  for (let idxs of numericCombinations(arr.length, r)) { yield idxs.map(i => arr[i]); }
}