Programming: How do I find all possibilities of a combination?

Question

In a program, how would I write a function to calculate all of the possible outcomes of a combination (not just the number of possibilities)? For example, I have 6 values: A, B, C, D, E, and F. How would I write a program to give me the possible combinations if I were to choose three of those values (ex. ABC, ABD, ABE, ABF, ACD...)? Also keep in mind that I do not want "ACB" if I already have "ABC", so order doesn't matter. Thank you!

Answer 1

Pseudo-code:

char[] letters = {'A', 'B', 'C', 'D', 'E', 'F'};
for(int i = 0; i < 4; i++)
{
    for(int j = i + 1; j < 5; j++)
    {
        for(int k = j + 1; k < 6; k++)
        {
            print(letters[i] + letters[j] + letters[k]);
        }
    }
}

Basically, you select any letter as your first. Then, you select any other letter "greater" than your first as your second. Then, you select any other letter "greater" than your second as your third. This makes sure that equivalent permutations with different arrangements are not counted twice.

Answer 2

You can use dynamic programming. In your example,you have $6 \choose 3$ combinations. Of these $5 \choose 2$ include $A$ and $5 \choose 3$ do not include $A$. So if we define a procedure listcombo(alphabet,n,r), where alphabet is the list of characters, n is the length of the alphabet, and r is the number of characters desired, you can do

listcombo(alphabet,n,r)  
    prepend alphabet[0] to the return list of listcombo(alphabet[1:],n-1,r)  
    append to this the return list of listcombo(alphabet[1:],n,r)

The resulting combinations will all be in the order the items are listed in alphabet. You need to deal with the fact that when $n \lt r$ the return list should be empty and should not be included at the next level.