# Subsets

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:
1. Move it one cell to the right
2. 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 {