Enumerating and Generating Combinations

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 16

I should like to comment on the functions for enumerating and generating combinations given by Alan Wilson in his article on the National Lottery (see Vector Vol.14 No.1 pp.51-57). Under the heading "Which Combination?" a function COMBNUMBER is given which maps a combination c of n items out of m into a unique integer. This function can be given much more succinctly as

    ∇Z←c COMBNUMBER m;T
[1]  Z←1+((⍴c)!m)-1++/(⍳⍴T)!T←m-⌽c
    ∇

The basis for this is that positive integers can be represented uniquely by vectors of a predetermined length in such a way that the integer given by a vector cv standing for "combination vector" is +/(⍳⍴cv)!cv. For example the value of the integer represented by the combination vector 1 2 4 5 is +/(⍳4)!1 2 4 5 = 11. The uniqueness of this representation requires that the minimimum values in the successive vector positions are ⍳cv in index origin 0. Notice that a combination vector is not itself a combination.

The inverse function which computes the combination vector (cv) corresponding to a given integer is obtained in the following way. If 4=⍴cv, the cv corresponding to 11 is built up from the right by first finding the largest n for which 4!n is less than 11. This value is 5 since 4!6 is 15. Subtract 4!5 from 11 to give 6 and repeat for 3!n. The largest n is 4 since 3!5 = 10, so subtract 3!4 = 4 to give 2. Continuing in this way cv is developed as 1 2 4 5. A function which implements the above algorithm is:

    ∇Z←n CI i;K
[1]  ⍝ Z is ith combination vector of length n
[2]   →(0≠i)/L0 ⋄ →0 Z←¯1+⍳n   ⍝ first stopping condition/action
[3]  L0:→(n>1)/L1 ⋄ →0 Z←i     ⍝ second stopping condition/action
[4]  L1:K←n                    ⍝ start recursive section
[5]  L2:→(i≥n!K←K+1)/L2        ⍝ loop until K too large
[6]  Z←((n-1)CI i-n!K-1),K-1   ⍝ recurse to find lower order digits
    ∇

Using this it is now simple to represent Mr. Wilson’s NUMBERCOMB with slightly different parametrization as

    ∇Z←nm NUMBERCOMB i
[1]  Z←⌽(2⊃nm)-(↑nm)CI(!/nm)-i   ⍝ ith combination of n out of m
    ∇

These functions were given in my paper Some Combinatoric Algorithms in APL at APL75 in Pisa, and the foundations for using the combination vector representation of the integers in order to obtain orderly listings of combinations is well set out in the references given there, namely Algorithic Combinatorics by Shimon Even (Collier Macmillan, 1973) and Applied Combinatorial Mathematics ed. E.F. Beckenbeck (Wiley, 1964) — see the opening chapter "The Machine Tools of Combinatorics" by D.H. Lehmer.

Mr. Wilson observes that calculations pertinent to e.g. the National Lottery rapidly hit the phenomenon of combinatorial explosion, and a degree of pragmatism must be used in order to avoid workspace overflow. A significant advantage of representing combinations by combination vectors is that it is easy to obtain estimates of, say, the distribution of combination totals by Monte Carlo methods. Thus a reasonable short cut to full enumeration of such totals is obtained by taking say 1000 random numbers between 1 and 13,983,816, viz:

+/¨(⊂6 49)NUMBERCOMB¨1000?13983816