Partitions

A partition of a set is a division of it into disjoint subsets whose union is the set itself.

For example, the partitions of the set {a, b, c, d} are:

{{a, b, c, d}}
{{a, b, c}, {d}}
{{a, b, d}, {c}}
{{a, b}, {c, d}}
{{a, b}, {c}, {d}}
{{a, c, d}, {b}}
{{a, c}, {b, d}}
{{a, c}, {b}, {d}}
{{a, d}, {b, c}}
{{a}, {b, c, d}}
{{a}, {b, c}, {d}}
{{a, d}, {b}, {c}}
{{a}, {b, d}, {c}}
{{a}, {b}, {c, d}}
{{a}, {b}, {c}, {d}}

The scheme I am using is as follows: a partition is represented by an array of the same size as the set, and each element in the array is an integer specifying the subset in the partition in which the corresponding element occurs. For example, the array [0, 0, 0, 0] indicates that every element occurs in set 0, the first set, i.e., the partition {{a, b, c, d}}, while the array [0, 1, 2, 3] puts every element in its own set, i.e., the partition {{a}, {b}, {c}, {d}}.

The correspondences for the partitions of a 4-set are as follows:

[0, 0, 0, 0] = {{a, b, c, d}}
[0, 0, 0, 1] = {{a, b, c}, {d}}
[0, 0, 1, 0] = {{a, b, d}, {c}}
[0, 0, 1, 1] = {{a, b}, {c, d}}
[0, 0, 1, 2] = {{a, b}, {c}, {d}}
[0, 1, 0, 0] = {{a, c, d}, {b}}
[0, 1, 0, 1] = {{a, c}, {b, d}}
[0, 1, 0, 2] = {{a, c}, {b}, {d}}
[0, 1, 1, 0] = {{a, d}, {b, c}}
[0, 1, 1, 1] = {{a}, {b, c, d}}
[0, 1, 1, 2] = {{a}, {b, c}, {d}}
[0, 1, 2, 0] = {{a, d}, {b}, {c}}
[0, 1, 2, 1] = {{a}, {b, d}, {c}}
[0, 1, 2, 2] = {{a}, {b}, {c, d}}
[0, 1, 2, 3] = {{a}, {b}, {c}, {d}}

Having established how to represent partitions, the algorithm simply needs to produce the arrays shown above. At each step:

  1. Find the rightmost element that is no more than any element to its left
  2. Increment it
  3. Set all of the elements after it to 0
unsigned int next_partition(unsigned int *ar, size_t len)
{	
	unsigned int result = 0;
	if (ar[len - 1] < len - 1) {
		unsigned int i;
		unsigned int finished = 0;
		unsigned int changed = 0;
		/* Find the rightmost element no more than the other elements */
		for (i = len - 1; !finished && !changed; i--) {
			unsigned int j, max = 0;
			/* Find the highest element to the left of this one */
			for (j = 0; j < i; j++) {
				if (ar[j] > max) {
					max = ar[j];
				}
			}
			if (ar[i] <= max) {
				/* Increment */
				ar[i]++;
				changed = 1;
				/* Set the following elements to 0 */
				for (j = i + 1; j < len; j++) {
					ar[j] = 0;
				}
			}
			finished = i == 1;
		}
		result = 1;
	}

	return result;
}