Combinatorial Problem: Finding N Combinations

As a first problem, Iet's use a very simple problem from combinatorics-- can you find all possible N combinations of items from a set?

In other words, given a set {1, 2, 3, 4, 5} and an N value of 3, we'd be looking for all combinations/subsets of length/size 3. In this case, they would be {1, 2, 3}, {1, 2, 4}, and so on.

Note that the ordering is not important in a combination. so {1, 2, 3} and {3, 2, 1} are considered the same thing.

Let's now look at the pseudo-code for this N-combination problem:

xxxxxxxxxx

routine: combos

input: set

output: display N combinations

assumption: position of the first item is zero and result set is empty at start

​

base case:

1. If all combinations starting with items in positions < (size-N) have been printed. Stop

​

recursive case:

Combos(set,result)

1. Repeat for each items i in the set:

    a. Put the item i in the result set

    b. if the result set has N items, display it

        else

        recursively call combos with (the input set without item i) and (the result set)

    c. Remove the item i from result set