Last active
November 13, 2025 21:11
-
-
Save bsidhom/8823ef9afbf6efc721c9a279ddd605a4 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // This naively computes partitions of a _multiset_ by first creating a unique | |
| // set of indices (into that multiset) and generating all partitions of those | |
| // (necessarily unique) indices. Finally, multi-partitions are canonicalized, | |
| // deduplicated, and then printed. This only works for very small multisets | |
| // since the set of all partitions must fit into memory. It is essentially only | |
| // useful for verifying that the final algorithm does what it's supposed to do. | |
| // | |
| // My tentative strategy for the memory-friendly version is to build all | |
| // partitions in _lexicographic_ order, recursively (top-down). The general idea | |
| // is to specify the initial set in lexicographical order. Starting at the end, | |
| // remove an element and compute all partitions of that prefix. For each | |
| // discovered partition: | |
| // - _Append_ the final element into its own part. (Since it was at most tied | |
| // for the largest item, this comes _first_ lexicographically.) Yield this | |
| // one new multipartition. | |
| // - _Insert_ the final element into each possible part of the existing | |
| // sub-multipartition. Crucially, this may break the invariant that partitions | |
| // are only ever presented in lexicographical order (of the parts themselves). | |
| // To address this (canonicalize + deduplicate), omit any new partitions which | |
| // do not retain lexicographical order. (You need to check at most 2 neighbors | |
| // since the old partition was valid; but I haven't thought about it too hard | |
| // and maybe you could get away with 1). In principle, other recursive cases | |
| // should come to the same multi-partition if we didn't produce a canonical | |
| // partition. Yield each resulting multipartition. | |
| const main = () => { | |
| // NOTE: Elements must be added in ascending order. | |
| // const multiset = [1, 1, 2, 2, 3, 3, 3]; | |
| const multiset = [1, 1, 1, 2, 2, 2, 3]; | |
| const allPartitions = new Map(); | |
| for (const partition of genSetPartitions(range(0, multiset.length))) { | |
| // NOTE: We _canonicalize_ each multipartition by sorting by the | |
| // individual parts. Because of how standard set partitions are | |
| // generated, each part is internally _ascending_. | |
| const multiPartition = partition | |
| .map((part) => part.map((i) => multiset[i])) | |
| .sort(); | |
| // This naive approach generates duplicates, so we have to dedupe. | |
| const key = JSON.stringify(multiPartition); | |
| allPartitions.set(key, multiPartition); | |
| } | |
| const sortedPartitions = [...allPartitions.values()].toSorted( | |
| compareLists(compareLists(compareNative)) | |
| ); | |
| for (const partition of sortedPartitions) { | |
| console.log(partition); | |
| } | |
| console.log(); | |
| for (const partition of genMultisetPartitions(multiset, compareNative)) { | |
| console.log(partition); | |
| } | |
| // console.log(); | |
| // for (const partition of twoMultipartitions([1, 1, 2, 2], compareNative)) { | |
| // for (const partition of twoMultipartitions(multiset, compareNative)) { | |
| // console.log(partition); | |
| // } | |
| }; | |
| // Generates 2-partitions of the given set. This is not currently used, but I | |
| // wrote it to help develop the 2-multipartition routine below. It is an easier | |
| // special case to understand since you do not need to exclude duplicate items | |
| // from the first part while iterating. | |
| const twoPartitions = function* (set) { | |
| const gen = function* (firstPart, set, minFirstPartIndex) { | |
| if (set.length == 0) { | |
| // We can't allow the last part to be empty. | |
| return; | |
| } | |
| // The existing first part will always be the _least_ since a truncated | |
| // sequence comes first in lexicographical order. | |
| yield [[...firstPart], [...set]]; | |
| // Then consider all first-part combinations you can make by appending | |
| // additional elements to the first part. | |
| for (let i = minFirstPartIndex; i < set.length; i++) { | |
| // i is the index of the _next_ element to join the first part. | |
| // TODO: Adapt this to work with multisets by excluding indexes equal to | |
| // elements we've already tried. | |
| // Recurse on the remaining set elements. | |
| yield* gen([...firstPart, set[i]], set.toSpliced(i, 1), i); | |
| } | |
| }; | |
| if (set.length == 0) { | |
| yield []; | |
| } else { | |
| // The set is not empty. WLOG, always put the first element into the first | |
| // part. This ensures the partition is lexicographically sorted (among | |
| // parts). | |
| yield* gen([set[0]], set.slice(1), 0); | |
| } | |
| }; | |
| // Generates semi-weak 2-multipartitions of the given multiset. The logic is the | |
| // same as above, but excludes duplicates based on already-tried elements and it | |
| // _allows the second part to be empty_. | |
| const twoMultipartitions = function* (multiset, compareFn) { | |
| // Precondition: multiset must be an array of orderable elements, _already in | |
| // order_. | |
| const compareParts = compareLists(compareFn); | |
| const gen = function* (firstPart, multiset, minFirstPartIndex) { | |
| // NOTE: If you want _canonical_ 2-partitions (where the parts are not | |
| // labeled), uncomment this block. | |
| // if (multiset.length > 0 && compareParts(firstPart, multiset) > 0) { | |
| // // Prune this entire branch; it cannot result in any lexicographical | |
| // // partitions since the multiset is less than the first part. | |
| // // NOTE: We allow the special case where the multiset is _empty_. This | |
| // // trivially compares as less than any other part, but we explicitly want | |
| // // to allow this case. | |
| // return; | |
| // } | |
| yield [[...firstPart], [...multiset]]; | |
| let lastTried = null; | |
| for (let i = minFirstPartIndex; i < multiset.length; i++) { | |
| const x = multiset[i]; | |
| if (lastTried !== null && x === lastTried) { | |
| continue; | |
| } | |
| yield* gen([...firstPart, x], multiset.toSpliced(i, 1), i); | |
| lastTried = x; | |
| } | |
| }; | |
| if (multiset.length == 0) { | |
| throw new Error("cannot 2-partition an empty multiset"); | |
| } | |
| yield* gen([multiset[0]], multiset.slice(1), 0); | |
| }; | |
| const genMultisetPartitions = function* (multiset, compareFn) { | |
| const compareParts = compareLists(compareFn); | |
| const gen = function* (prefix, multiset) { | |
| // prefix is the existing (_fixed_) partitions that come before any new | |
| // parts. Our job is to generate all further subpartitions of this prefix | |
| // by dividing up the remaining multiset. | |
| if (multiset.length == 0) { | |
| yield [...prefix]; | |
| } else { | |
| // Precondition: there is at least 1 item in the multiset. First, split | |
| // the remaining multiset into 2 parts (second possibly empty), where each | |
| // is internally lexicographically ordered. | |
| // TODO: Give a _minimum_ first-part size to the 2-multipartition | |
| // algorithm to preemptively prune the search space. Right now, we visit | |
| // many more potential sub-partitions than are actually valid due to the | |
| // parts not being lexicographically ordered. It's not as simple as | |
| // forcing 2-multipartitions to be lexicographically ordered by part. | |
| const parts = twoMultipartitions(multiset, compareFn); | |
| for (const [firstPart, multiset] of parts) { | |
| if (prefix.length > 0 && compareParts(prefix.at(-1), firstPart) > 0) { | |
| // This is not canonical (violates inter-part order). Since all | |
| // firstParts returned by the iterator are _at least_ as great as | |
| // this, we may have more partitions to return. | |
| continue; | |
| } | |
| // Recursively partition the remaining multiset with this fixed | |
| // prefix. | |
| yield* gen([...prefix, [...firstPart]], multiset); | |
| } | |
| } | |
| }; | |
| yield* gen([], multiset.toSorted(compareParts)); | |
| }; | |
| // Standard set partition (for verification by partitioning indices). Taken from | |
| // https://gist.github.com/bsidhom/645056f81b43c29e63a737cf91854753. | |
| const genSetPartitions = function* (set) { | |
| // Set is an array, but we _assume_ each element is unique. | |
| if (set.length == 0) { | |
| yield []; | |
| } else { | |
| const last = set.at(-1); | |
| for (const partition of genSetPartitions(set.slice(0, -1))) { | |
| // Append the final element to its _own_ partition. | |
| yield [...partition, [last]]; | |
| for (let i = partition.length - 1; i >= 0; i--) { | |
| // Append the final element to _each_ part of the | |
| // sub-partition. By iterating backward, we ensure this is | |
| // lexicographically sorted (within the context of the given | |
| // recursion level). | |
| yield partition.with(i, partition.at(i).concat(last)); | |
| } | |
| } | |
| } | |
| }; | |
| // Shockingly, JavaScript does not natively support array comparisons (well, it | |
| // does by incoherent coercion). It took me way too long to figure out why | |
| // nested list sorting didn't behave the way I expected based on doing a few | |
| // hand checks with the `<` operator and test arrays. | |
| const compareNative = (a, b) => { | |
| if (a < b) { | |
| return -1; | |
| } else if (a > b) { | |
| return 1; | |
| } else { | |
| return 0; | |
| } | |
| }; | |
| const compareLists = (compareElements) => (a, b) => { | |
| const length = a.length < b.length ? a.length : b.length; | |
| for (let i = 0; i < length; i++) { | |
| const c = compareElements(a[i], b[i]); | |
| if (c < 0) { | |
| return -1; | |
| } else if (c > 0) { | |
| return 1; | |
| } | |
| } | |
| if (a.length < b.length) { | |
| return -1; | |
| } else if (a.length > b.length) { | |
| return 1; | |
| } | |
| return 0; | |
| }; | |
| const range = (start, stop, step = 1) => { | |
| const length = Math.floor((stop - start) / step); | |
| return Array.from({ length }, (_, i) => step * i + start); | |
| }; | |
| main(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment