Integer partitions in JavaScript with internal iteration

integer-partitions-internal.js

// Turns out JS can be fast. Generators are just slow. :(
// A fairer comparison with
// https://gist.github.com/bsidhom/32162a78e602d2f620dc8ab07c71ef97
const main = () => {
  let i = 0;
  partitionsInternal(100, (_p) => {
    i++;
    if (i % 1000000 == 0) {
      console.log(i);
    }
  });
  console.log(i);

  // Original "external" style:
  // let i = 0;
  // for (const p of partitions(100)) {
  //   i++;
  //   if (i % 1000000 == 0) {
  //     console.log(i);
  //   }
  // }
  // console.log(i);
};

const partitionsInternal = (n, f) => {
  const prefix = [];
  const rec = (n, k) => {
    for (let i = k; 2 * i <= n; i++) {
      prefix.push(i);
      rec(n - i, i);
      prefix.pop();
    }
    prefix.push(n);
    f(prefix);
    prefix.pop();
  };
  rec(n, 1);
};

// This is still slow despite the fact that we directly share the underlying
// partition array with callers.
const partitions = function* (n) {
  const prefix = [];
  const gen = function* (n, k) {
    for (let i = k; 2 * i <= n; i++) {
      prefix.push(i);
      yield* gen(n - i, i);
      prefix.pop();
    }
    prefix.push(n);
    yield prefix;
    prefix.pop();
  };
  yield* gen(n, 1);
};

main();