Generate all partitions of a set of elements

partitions.js

// 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;
	
};