integer-partitions.js

// Translation of https://gist.github.com/bsidhom/c136b6bd26dcff64d9ca443a5bd022a3 into JS for use in the browser.
const main = () => {
  const n = 10;
  for (const partition of genPartitions(n)) {
    console.log(partition);
  }
};

const genPartitions = function* (n) {
  const prefix = [];
  const gen = function* (minStart, n) {
    if (n < 0) {
      return;
    } else if (n == 0) {
      yield [...prefix];
    } else {
      for (let i = minStart; 2 * i <= n; i++) {
        // Try to recurse as long as we can fit at least 2 entries with
        // the new minimum prefix.
        // NOTE: This can be made pretty "efficient" since we share the
        // prefix itself and only need to copy the final output at yield
        // time. On the other hand, there are nearly-exponentially-many
        // partitions, so "efficiency" is relative (see Hardy-Ramanujan
        // asymptotics).
        prefix.push(i);
        yield* gen(i, n - i);
        prefix.pop();
      }
      // You can _always_ fall back to stuffing n into its own part.
      yield [...prefix, n];
    }
  };
  yield* gen(1, n);
};

main();