Itertools.combinations in Javascript

Question

Is there a similar library as Python's itertools in JavaScript? I'm interested in permutations and combinations especially.

I'm not using Node.js.

I want to do something like this:

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

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

Thanks! :)

Answer 1

I like itertools.combinations and wanted a memory-efficient JavaScript generator function, but couldn't quickly find an acceptable library so I rolled my own.

It's in TypeScript (to help me keep track of bookkeeping), but I'll append the transpiled JavaScript at the bottom.

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

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

function* numericCombinations(n: number, r: number, loc: number[] = []): IterableIterator<number[]> {
  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<T>(arr: T[], r: number) {
  for (let idxs of numericCombinations(arr.length, r)) { yield idxs.map(i => arr[i]); }
}

All the black magic is in the numericCombinations function, which is a recursive generator—see MDN documentation on yield*. The actual combinations function just wraps it to match the Python API.

I can put this in a .ts file and put this at the bottom of it:

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

and Node prints out 133784560 in less than 2.5 minutes, with minimal memory usage, on my 2015-vintage laptop. That is, it generated all hundred thirty-four million ways you can choose seven cards from a standard deck of fifty-two playing cards (i.e., all complete Texas hold ’em hands) without burdening memory or overly-nesting recursive function calls.

(Python3 can do this in 20 seconds, or 7× faster… speedups to the above welcome.)

---

JavaScript code:

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