<< Computer AlgorithmsUse  Ctrl +  or    to enlarge or reduce text size.

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 is written for PBCC and can be modified for Visual Basic, FORTRAN and any other BASIC-like compiler.

Function PBMain
 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