Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
share|improve this question
2  
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

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer
    
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\}$.

share|improve this answer
    
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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.