# All unique combinations of n numbers

How is the algorithm or process called which calculates all unique combinations of n numbers? By unique I mean that this 1234 is the same as this 1243.

Example: Take this 4 numbers and list all unique combinations:

1
2
3
4


Output:

1
2
3
4
12
13
14
23
24
34
123
124
134
234
1234

-
Why did you not take 134? – Phira Nov 19 '12 at 17:49
Thank you, I forgot it. – arminb Nov 19 '12 at 17:51
These are the non-empty subsets, and you can generate them all by running $k$ from $1$ to $2^{n}-1$, write $k$ as a binary $n$-digit number, and then generate the set for $k$ by adding $i$ if the $i$th binary digit of $k$ is $1$. – Thomas Andrews Nov 19 '12 at 17:53
Higher-Order Perl discusses this problem and provides code to solve it, I think in Chapter 5. It is available online for free. – MJD Nov 19 '12 at 17:57

There are $2^n-1$ non-empty subsets of the set $\{1,...,n\}$. Given a number $k=1,...,2^n-1$, we can write the $k$ as an $n$-digit binary number, and then put $i$ in the set $A_k$ if the $i$th binary digit of $k$ is $1$.

For example, $n=3$ yields: $$\begin{array}{cc}\text k & \text {binary} & \text{set}\\ 1 & 001 & \{3\}\\ 2 & 010 & \{2\}\\ 3 & 011 & \{2,3\}\\ 4 & 100 & \{1\}\\ 5 & 101 & \{1,3\}\\ 6 & 110 & \{1,2\}\\ 7 & 111 & \{1,2,3\} \end{array}$$

-
Thanks! It's so simple why haven't I thought about to consider it as binary counting where each element represents a bit :-) – arminb Nov 19 '12 at 18:04

For $n$ numbers, the output consists of $2^n-1$ entries, which is the number of nonempty subsets of $\{1,\ldots,n\}$.

-
Yeah, he wants to generate the list of them, it seems. – Thomas Andrews Nov 19 '12 at 17:54
Thank you but that wasn't my question. I'd like to know the name of the process which calculates all uniqe combinations of n numbers. If there is a name :-) – arminb Nov 19 '12 at 17:54

If you want to list them, the easiest way is to count from $0$(if you allow the empty set) or $1$ (if not) to $2^n-1$ in binary. At each value, use the bits that are turned on to represent the elements. So when you get to $11_{10}=1011_2$ you output $134$

-