Generate a power set by only adding or removing a single element at a time

Question

Is there an algorithm that is capable of generating a complete power set by only removing or adding one element in each step? I'd like it to avoid duplicates, but ordering isn't important. I've tried iterating over a set with four elements looking for a pattern that can be repeated to a larger set. I've found a dozen paths, but they seem to be random. Any help would be greatly appreciated.

Example with {x, y, z}: {} {x} {x, y} {y} {y, z} {z} {x, z} {x, y, z}

Starting with an empty set, every subsequent set is built by either adding or removing one element. I'd like to do this with larger sets predictably.

Answer 1

A set of elements can be thought of equivocally as the binary string problem. Suppose your set is finite, with cardinality $n$. We know then that the power set has cardinality $2^{n}$. So set up a binary vector with $n$ elements. If there is a $1$ for a component, then the element is in the subset. Otherwise, it isn't.

Consider the set $\{A, B, C\}$.

The power set can be generated by the binary vectors, simply by counting in binary: $$ (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) $$

Answer 2

Encode your subsets as binary strings. Then, starting from the empty set $(0,0,0,\dots,0)$, start counting from 1 to $2^n$ and flip the bit corresponding to the lower $1$ in the binary expansion of your counter:

\begin{align} 000000 & \\ 100000 &\text{(counter is $1$, flip leftmost bit)}\\ 110000 &(\text{counter is $2$, flip second bit})\\ 010000 &(\text{counter is $3$, flip leftmost bit again})\\ 011000 &(\text{counter is $4$, flip third bit})\\ 111000 &(5)\\ 101000 &(6)\\ 001000 &(7)\\ 001100 &(8)\\ 101100 &(9) \end{align}

Answer 3

This really amounts to writing out a full binary tree of height $n$.

How would you do that? You would write a recursive program that says "given a tree of height $k$, let's write a tree of height $k+1$ by adding the top level nodes".

You fix some ordering of your set, then you traverse this order. Given the power set of the first $k$ elements, you obtain the power set of the $k+1$ elements by first applying mitosis, and duplicating the power set of the $k$ elements; then pick one of the copies, and add to all the entries the new element.

More specifically, here is some badly written recursive pseudo-code.

Power([1,k])
    if k=0 return Collection([1,0]) 
    else return Union(Power[0,k-1],Add(Power[0,k-1],{k}))

Add(A,B)
   return Collection(For each X in A collect Union(X,B))

Where [1,k] denotes the set $\{1,\ldots,k\}$, so [1,0] denotes the empty set.