<< Computer Algorithms | Use Ctrl + or – to enlarge or reduce text size. |

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 as1 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 combination4 5 6 7 largest combination

1 2 6 7 given combination

Compare each vertical pair of numbers starting from the 1 2 6 7 given combination

In our example:

1 2 6 7

is1 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 of1 2 3 ....... N

Now suppose you have the combinationindex(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 targetN–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