12
$\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 
  • 0
    What if there are repetitions in the number? How would you find all unique combinations for 1134?2017-02-20

3 Answers 3

13

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
4

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$

3

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

  • 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