Skip to content

Instantly share code, notes, and snippets.

@lorenzos
Created October 2, 2021 23:01
Show Gist options
  • Save lorenzos/87a4fa6031af47b978a20dce1cd016df to your computer and use it in GitHub Desktop.
Save lorenzos/87a4fa6031af47b978a20dce1cd016df to your computer and use it in GitHub Desktop.
Generate all partitions of a set of elements
// GENERATES ALL PARTITIONS OF A SET OF ELEMENTS
// A thorough definition can be found on Wikipedia: https://en.wikipedia.org/wiki/Partition_of_a_set
// Implementation of: https://stackoverflow.com/a/20530130
// First, let's solve a simpler problem: how to find all partitions consisting of exactly two parts.
// For an n-element set, we can count an int from 0 to (2^n)-1. This creates every n-bit pattern,
// with each bit corresponding to one input element. If the bit is 0, we place the element in the
// first part; if it is 1, the element is placed in the second part.
// This leaves one problem: For each partition, we'll get a duplicate result where the two parts are
// swapped. To remedy this, we'll always place the first element into the first part. We then only
// distribute the remaining n-1 elements by counting from 0 to (2^(n-1))-1.
// Now that we can partition a set into two parts, we can write a recursive function that solves the
// rest of the problem. The function starts off with the original set and finds all two-part-partitions.
// For each of these partitions, it recursively finds all ways to partition the second part into two
// parts, yielding all three-part partitions. It then divides the last part of each of these partitions
// to generate all four-part partitions, and so on.
export default (array) => {
if (!Array.isArray(array)) return null;
return getAllPartitions([], array);
};
const getAllPartitions = (fixedParts, suffixElements) => {
const partitions = [];
// A trivial partition consists of the fixed parts followed by all suffix elements as one block
partitions.push([...fixedParts, suffixElements]);
// Get all two-group-partitions of the suffix elements and sub-divide them recursively
const suffixPartitions = getTuplePartitions(suffixElements);
for (const suffixPartition of suffixPartitions) {
const subPartitions = getAllPartitions([...fixedParts, suffixPartition[0]], suffixPartition[1]);
for (const subPartition of subPartitions) {
partitions.push(subPartition);
}
}
return partitions;
};
const getTuplePartitions = (elements) => {
// No result if less than 2 elements
if (elements.length < 2) return [];
// Generate all 2-part partitions
const partitions = [];
for (let pattern = 1; pattern < (1 << (elements.length - 1)); pattern++) {
// Create the two result sets and assign the first element to the first set
const resultSets = [ [elements[0]], [] ];
// Distribute the remaining elements
for (let index = 1; index < elements.length; index++) {
resultSets[(pattern >> (index - 1)) & 1].push(elements[index]);
}
partitions.push(resultSets);
}
return partitions;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment