Generate all partitions of a set

set-partitions.js

// NOTE: Building this up en route to a hopefully-clean _multiset_ partition generator.
const main = () => {
  const set = [1, 2, 3, 4];
  for (const partition of genPartitions(set)) {
    console.log(partition);
  }
};

// Generate all partitions of the given set (given as an array of unique items).
// If the items are given in _ascending_ order, then the generator will yield
// unique partitions in lexicographical order, each partition being further
// canonicalized by lexicographical order.
const genPartitions = function* (set) {
  const gen = function* (prefix, set, minFirstPartIndex) {
    // prefix is the existing leading (sub)partition we have built so far.
    // set is the remaining set of items to be partitioned
    // minFirstPartIndex is the index of the first item which is allowed to be
    //    inserted into the already-existing first part (if any).
    if (set.length == 0) {
      yield prefix.map((part) => part.slice());
    } else {
      // Add the leading element to its own part and recurse. This is always
      // admissible because it necessarily comes first in lexicographical order
      // and this branch has necessarily not been explored previously.
      const x = set[0];
      yield* gen([...prefix.map((part) => part.slice()), [x]], set.slice(1), 0);
      if (prefix.length > 0) {
        // If we have an existing first-part, iteratively try to add every
        // valid index into that same part before recursing. Note that in this
        // case, we avoid duplicates and non-canonical order by skipping to the
        // first allowed index from the outer stack frame. That outer frame has
        // already looped to place other items into the currently-building first
        // part, and those items must not be replaced.
        for (let i = minFirstPartIndex; i < set.length; i++) {
          const x = set[i];
          yield* gen(
            [
              ...prefix.slice(0, -1).map((part) => part.slice()),
              [...prefix.at(-1), x],
            ],
            set.toSpliced(i, 1),
            i,
          );
        }
      }
    }
  };
  yield* gen([], set, 0);
};

main();