How to List All Combinations of a Number of Things Taken So Many at a Time
Problem: List all possible combinations of N things taken K at a time.
We first illustrate a way to do this for the particular case N = 7 and K = 4 which will make the general case clear.
Indicate the items with the numbers 1 to 7
1 2 3 4 5 6 7Since order is immaterial in a combination we will always write a combination so the numbers are in increasing order. For example 4 1 6 3 is the same combination as
1 3 4 6and will always be written that way.
Start with the combination consisting of the first K of the N items. In our example the first 4 of the 7 items is:
1 2 3 4If you think of a combination as a string, in this case 1234, this is the “smallest” combination of all the combinations when placed in lexicographical order.
The “largest” combination consists of the last K of the N items. Call it the target. In our example with N = 7 and K = 4 it is
4 5 6 7
Now suppose we are given a random combination, for example
1 2 6 7You can find the next larger combination as follows. Write the target above the given combination
4 5 6 7 largest combinationCompare each vertical pair of numbers starting from the right and moving left (here 7 below with 7 above, 6 below with 6 above, 2 below with etc.) and(1) Find the first item of the given combination that is less than the number directly above it. (If there is none we are done, that is, the given combination is the target.)(2) Increase that number by one.(3) Replace the numbers to its right with consecutive numbers. Thus if x is the new number in the previous step, make the numbers to its right x+1, x+2, etc. to the end.
1 2 6 7 given combination
In our example:(1) Scanning right to left, 2 is the first number smaller than the one above it. Per instructions we:(2) Increase 2 to 3, and(3) Change the numbers to its right to 4 and 5.Thus the next combination after
1 2 6 7is
1 3 4 5
To list all the combinations of 7 things taken 4 at a time, start with the “smallest” combination 1 2 3 4 and keep generating the next combination until you reach the target 4 5 6 7.
In general, start with the combination
1 2 3 ... Kwhich is the first K of
1 2 3 ....... NNow suppose you have the combination
index(1) index(2) index(3) ... index(K)Generate the next combination as follows. Try to increment the last index, index(K). If you can (that is, it is less than N), do it. If you cannot, go to the next to last, index(K–1), and try (is it less than N–1?), etc. Afterwards make the numbers to its right count upwards. When you must try all the way back to the first index, index(1), and find it cannot be incremented (it equals N–K+1), that is, when you have reached the target
N–K+1 ... N–2 N–1 Nyou are done. The list of combinations thus generated will be in lexicographical order.
If you want combinations of letters (or whatever), think of the above numbers as ordinal numbers 1st, 2nd, 3rd, etc. In other words, indices into the row of N letters.
The program below is written for PBCC and can be modified for Visual Basic, FORTRAN and any other BASIC-like compiler.
Local N, K, D As Long
Local i, s As Long
Local count As Long
N = 5 '<-- change to suit, N > 0
K = 3 '<-- change to suit, 0 <= K <= N
Dim item(N) As String 'N items
Dim index(K) As Long 'K indices of items of a combination
D = N - K 'fixed along with N and K
For i = 1 To N 'A B C D ...
item(i) = " " + Chr$(i + 64)
Print n; "things"
Print " ";
For i = 1 To N 'print the items
Print i; 'indicator
For i = 1 To N
Print " " + item(i); 'item indicated
Print " taken"; K; "at a time:"
For i = 1 To K
index(i) = i
Do 'go through all combinations
Print " ";
For i = 1 To K 'print the current combination
Print " " + Format$(index(i)); 'indicator
Print " ";
For i = 1 To K
Print item(index(i)); 'item indicated
Incr count 'count the number of combinations
i = K 'start with last item
If index(i) < D + i Then 'can we increase index(j) ?
Incr index(i) 'do so
For s = 1 To K - i 'reset all the index() to its right
index(i + s) = index(i) + s
Else 'cannot increase index(i)
Decr i 'back up one
If i = 0 Then Exit Do 'if cannot back up, done
Loop Until i = 0
Print " C("; Format$(N); ","; Format$(K); ") ="; count
Print " Press any key."