The set of all subsets of a set is called the power set.
For example, the power set of the set {a, b, c} consists of the sets:
{} {a} {b} {c} {a, b} {a, c} {b, c} {a, b, c}
Note that:
- The empty set {} is in the power set
- The set itself is in the power set
The set of all subsets of a particular size, or k-subsets, are combinations.
A subset can be represented as an array of boolean values of the same size as the set, called a characteristic vector. Each boolean value indicates whether the corresponding element in the set is present or absent in the subset.
This gives following correspondences for the set {a, b, c}:
[0, 0, 0] = {} [1, 0, 0] = {a} [0, 1, 0] = {b} [0, 0, 1] = {c} [1, 1, 0] = {a, b} [1, 0, 1] = {a, c} [0, 1, 1] = {b, c} [1, 1, 1] = {a, b, c}
The algorithm then simply needs to produce the arrays shown above. Observing how they change, one can derive the following algorithm:
- Find the rightmost 1 with a 0 on its right. If it exists:
- Move it one cell to the right
- Move all of the 1s on its right, which are packed on the right hand side, to the cells immediately behind it
- Otherwise, If all of the 1s are on the right hand side and ar[0] is 0, add another 1 and move the other 1s immediately behind it
- Otherwise, all subsets have been produced, so return the array to its starting arrangement of all 0s
unsigned int next_subset(unsigned int *ar, size_t n) { int i, ones = 0; unsigned int found = 0; unsigned int result = 1; /* Find the rightmost 1 with a 0 on its right, or the number of 1s */ for (i = n - 2; !found && i >= 0; i--) { found = ar[i] == 1 && ar[i + 1] == 0; ones += ar[i + 1] == 1; } if (found) { /* Move the 1 right */ ar[++i] = 0; ar[++i] = 1; /* Pack the 1s to its right immediately behind it */ i++; for (; i < n; i++, ones--) { if (ones > 0) { ar[i] = 1; } else { ar[i] = 0; } } } else if (ar[0] == 0) { /* Add a new 1 and place them all at the beginning */ for (i = 0; i < n; i++) { if (i < ones + 1) { ar[i] = 1; } else { ar[i] = 0; } } } else { /* Finished, return to the starting arrangement */ for (i = 0; i < n; i++) { ar[i] = 0; } result = 0; } return result; }