10
$\begingroup$

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 
  • 2
    Why did you not take 134?2012-11-19
  • 1
    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$.2012-11-19
  • 1
    *Higher-Order Perl* discusses this problem and provides code to solve it, I think in Chapter 5. [It is available online for free](http://hop.perl.plover.com/book/).2012-11-19
  • 0
    What if there are repetitions in the number? How would you find all unique combinations for 1134?2017-02-20

3 Answers 3

12

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}$$

  • 0
    Thanks! It's so simple why haven't I thought about to consider it as binary counting where each element represents a bit :-)2012-11-19
3

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

  • 0
    Yeah, he wants to generate the list of them, it seems.2012-11-19
  • 0
    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 :-)2012-11-19
3

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$