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 7
Since 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 6
and 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 4
If 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 7
You can find the next larger combination as follows. Write the target above the given combination
4 5 6 7 largest combination
1 2 6 7 given combination
Compare 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.
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 7
is
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 ... K
which is the first K of
1 2 3 ....... N
Now 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 N
you 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 can be modified for Visual Basic, FORTRAN and any other BASIC-like compiler.
Function Main
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)
Next
Print n; "things"
Print " ";
For i = 1 To N 'print the items
Print i; 'indicator
Next
Print
For i = 1 To N
Print " " + item(i); 'item indicated
Next
Print
Print " taken"; K; "at a time:"
Print
'First combination
For i = 1 To K
index(i) = i
Next
Do 'go through all combinations
Print " ";
For i = 1 To K 'print the current combination
Print " " + Format$(index(i)); 'indicator
Next
Print " ";
For i = 1 To K
Print item(index(i)); 'item indicated
Next
Print
Incr count 'count the number of combinations
i = K 'start with last item
Do
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
Next
Exit Do
Else 'cannot increase index(i)
Decr i 'back up one
If i = 0 Then Exit Do 'if cannot back up, done
End If
Loop
Loop Until i = 0
Print
Print " C("; Format$(N); ","; Format$(K); ") ="; count
Print " Press any key."
WaitKey$
End Function