Algorithm for generating all elements of a set consisting of specific $n$-tuples

Question

I was working on functional analysis last night, and then my mind got distracted by the following problem. Consider a set $$I=\{0,1\}$$Now consider a subset of $\mathbb{R^n}$ $$X=\{(x_1,x_2,\dots ,x_n):x_i\in I \forall i=1..n\}$$ $X$ contains $2^n$ elements, but I'm trying to think of an algorithm that can generate all the elements of $X$. I'm not looking for any computer code but just the general form such an algorithm would take. Is there such an algorithm that could be implemented by a computational device?

Answer 1

When I tackle this problem with school kids I want to lead them to the recursive algorithm that says, essentially, that after you've listed the subsets for some value of $n$ you can list those for $n+1$ by adding first $0$ and then $1$ to the subsets you have for $n$.

Several bonus observations:

• you've listed and counted the vertices of the cube in each dimension.

• if you prefix rather than append the new bit you've written all the numbers from $0$ to $2^{n}-1$ in base 2, in order.