- online
- 1.0
J-ottings 55
Combination Lists
by Norman Thomson
I enjoyed R.E.Boss’s article on lists of combinations [1] because, like him, I have been fascinated both by their patterns and by algorithms which generate them. In both APL and J systematic permutation lists are easier to generate than those for combinations. In J the former are available directly through the primitive A. so that
A. 1 2 0 3
says that 1 2 0 is permutation 3 (in index origin 0) of i.3 in lexical order, a process which is reversed by dyadic A.:
3 A. 0 1 2 1 2 0
A full list of such permutations is given by e.g.
(i.@! A. i.)3 0 1 2 0 2 1 1 0 2 1 2 0 2 0 1 2 1 0
Analogously with monadic A., any combination of r integers from i.n can be put into one-to-one correspondence with the counting integers by adding appropriate values of kCr, where the k’s are the integers in the combination and r=1,2,.. , e.g. for the combination 1 3 4, 1C1 + 3C2 + 4C3 = 8 . Unlike permutations, the value of n need not appear in a combination, and so its number is independent of n. The following verb gives unique combination numbers:
ctoi=:monad : '+/(>:i.#y)!y' NB. combination to integer ctoi 1 3 4 8
A challenge is to produce itoc such that 8 itoc 3 is 1 3 4.
The emphasis in [1] is on the pragmatic matter of how to generate combinations more efficiently using lines such as [:(,.&.><@:\.)/ >:@-~ [\i.@] . This on deconstruction shows that orderly lists of combinations are a little closer to primitives in J than might at first sight be imagined. The key is the combination of box, stitch, infix and suffix, for which a preliminary note on the “fix” family of adverbs is in order, namely prefix (\ monadic), suffix (\. monadic), infix (\ dyadic) and outfix (\. dyadic). These have the general effect of making objects larger either by increasing rank as in
(,\i.5);(,\.i.5) NB. ravel prefix;suffix ┌─────────┬─────────┐ │0 0 0 0 0│0 1 2 3 4│ │0 1 0 0 0│1 2 3 4 0│ │0 1 2 0 0│2 3 4 0 0│ │0 1 2 3 0│3 4 0 0 0│ │0 1 2 3 4│4 0 0 0 0│ └─────────┴─────────┘
or by repetition with amendment:
<\.i.5 NB. box suffix
┌─────────┬───────┬─────┬───┬─┐
│0 1 2 3 4│1 2 3 4│2 3 4│3 4│4│
└─────────┴───────┴─────┴───┴─┘
The dyadic form infix delivers overlapping x-lists and outfix delivers the result of progressively removing them:
(2,\i.5);(2,\.i.5) ┌───┬─────┐ │0 1│2 3 4│ │1 2│0 3 4│ │2 3│0 1 4│ │3 4│0 1 2│ └───┴─────┘
An informal rule is that without dots (that is prefix and infix) things proceed from the left, with dots they do so from the right.
Combinations
A deconstruction of comb2 in [1] for the orderly listing of combinations begins with
|:3 ,\i. 6 NB. dyadic infix 0 1 2 3 1 2 3 4 2 3 4 5
Apply box-ravel suffix to the final row above:
<@,\.2 3 4 5
┌───────┬─────┬───┬─┐
│2 3 4 5│3 4 5│4 5│5│
└───────┴─────┴───┴─┘
and then stitch the numbers in the penultimate row on an item by item basis:
Each=.&.> 1 2 3 4 ,.Each<@,\.2 3 4 5 ┌───┬───┬───┬───┐ │1 2│2 3│3 4│4 5│ │1 3│2 4│3 5│ │ │1 4│2 5│ │ │ │1 5│ │ │ │ └───┴───┴───┴───┘
Call this form of stitching Stitch with an upper case S to distinguish it from the name of the primitive stitch:
Stitch=.,.Each <@;\.
so that the preceding display is obtained as
1 2 3 4 Stitch 2 3 4 5
By applying this successively to the columns of 3 ,\i.6, everything is in place to generalize this to a verb for generating combinations of x from y . (The name comb2 is chosen because this is the technique described by that name in [1].)
comb2=:dyad : 'z=.Stitch/|:x,\i.y' 3 comb2 6 ┌─────┬─────┬─────┬─────┐ │0 1 2│1 2 3│2 3 4│3 4 5│ │0 1 3│1 2 4│2 3 5│ │ │0 1 4│1 2 5│2 4 5│ │ │0 1 5│1 3 4│ │ │ │0 2 3│1 3 5│ │ │ │0 2 4│1 4 5│ │ │ │0 2 5│ │ │ │ │0 3 4│ │ │ │ │0 3 5│ │ │ │ │0 4 5│ │ │ │ └─────┴─────┴─────┴─────┘
A final ; (raze) could be used to transform the above into normal unboxed lists – retaining the boxes both helps appreciation of the structure, and also reduces the number of print lines required.
The integer representations of the combination list 3 comb2 6 in the order given above are
;ctoi each<"1 ;3 comb2 6 0 1 4 10 2 5 11 7 13 16 3 6 12 8 14 17 9 15 18 19
which shows that combinations generated by comb2 are not in their ‘natural’ order.
The boxed result of comb2 suggests that reduction could equally well have been applied from the right rather than the left by repeated use of the primitive verb reverse:
comb=.dyad : 'z=.|."1 Each Stitch/|.|."1 |: x ,\ i. y' 3 comb 6 ┌─────┬─────┬─────┬─────┐ │3 4 5│2 3 4│1 2 3│0 1 2│ │2 4 5│1 3 4│0 2 3│ │ │1 4 5│0 3 4│0 1 3│ │ │0 4 5│1 2 4│ │ │ │2 3 5│0 2 4│ │ │ │1 3 5│0 1 4│ │ │ │0 3 5│ │ │ │ │1 2 5│ │ │ │ │0 2 5│ │ │ │ │0 1 5│ │ │ │ └─────┴─────┴─────┴─────┘
As a bonus comb delivers the combination list in reverse counting order:
;ctoi each<"1 ;3 comb 6
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Relationship to the Pascal Triangle
The number of boxes in r comb n is one more than d=.n-r and the numbers of combinations in the various boxes are directly derivable from the Pascal Triangle whose first few numbers are:
!/~i.10 1 1 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 0 0 1 3 6 10 15 21 28 36 0 0 0 1 4 10 20 35 56 84 0 0 0 0 1 5 15 35 70 126 0 0 0 0 0 1 6 21 56 126 0 0 0 0 0 0 1 7 28 84 0 0 0 0 0 0 0 1 8 36 0 0 0 0 0 0 0 0 1 9 0 0 0 0 0 0 0 0 0 1
3 comb2 6 and 3 comb 6 both consist of 20 combinations displayed in 4 boxes, the numbers in which are obtained from the right as the first four non-zero items in row 2 counting in origin 0. More generally r comb n has d+1 boxes in which the numbers of combinations are given by the first d+1 non-zero integers in row r-1. For example for 6 comb 9 read a total of 84 combinations from the Pascal triangle, then go one up along the diagonal and read 1+6+21+56 along the row.
When r is large relative to n it is more efficient to use complementary combinations as suggested by the symmetry of the Pascal triangle, for example
time=.6!:2 time Each '2 comb 55';'53 comb2 55' ┌───────────┬─────────┐ │0.000388038│0.0130343│ └───────────┴─────────┘ time '(<i.55)-."1 Each 2 comb 55' 0.00245115
Defining an itoc verb
This challenge stated earlier requires the delivery of a unique combination, given an r and an integer i. If n is also given i must be in the range 0 .. nCr -1. To do this, first find the largest k such that kCr does not exceed i . Subtract kCr from i and carry on repeating this process for (i- kCr) and (r – 1). For example, to find combination number 8 of 3 comb n, 5C3 = 10 which exceeds 8, but 4C3 = 4 does not, so select 4 as rightmost element. 8 – 4 = 4 which exceeds 3C2, so catenate 3 to the left of 4. 4 – 3 = 1 which is less than 2C1 but equals 1C1, so that the final digit is 1 and the required combination is 1 3 4. Here is this process expressed in J:
lgstk=.4 :0
i=.<:y NB. increase k up to lgst y!k <x
while. x>: y!>:i do. i=.>:i end.
)
itoc=.4 :0
x=.x-y!r=.x lgstk y
while. y>1 do.
y=.<:y NB. decrement y
r=.(x lgstk y),r NB. catenate new value to left of r
x=.x-y!{.r end. r NB. reduce x for next iteration
)
8 itoc 3
1 3 4
Another iterative algorithm
comb and comb2 are not the only methods for constructing combination lists. For example [1] starts by describing another such algorithm, and without worrying too much about the J details, tracing the iterative steps can be used to illustrate how alternative techniques reach the same goal by different routes.
trace=.monad : 'y(1!:2)2' combi=.4 : 0 NB. d is n-r for any given nCr k=. i.>:d=.y-x NB. k is a list of integers z=.(d$<i.0 0),<i.1 0 NB. initially z is d+1 empty boxes for_j. i.x do. NB. loop thru items of i.x trace z=. k Stitch >:Each z end. ) 3 combi 6 ┌─┬─┬─┬─┐ │0│1│2│3│ └─┴─┴─┴─┘ ┌───┬───┬───┬───┐ │0 1│1 2│2 3│3 4│ │0 2│1 3│2 4│ │ │0 3│1 4│ │ │ │0 4│ │ │ │ └───┴───┴───┴───┘ ┌─────┬─────┬─────┬─────┐ │0 1 2│1 2 3│2 3 4│3 4 5│ │0 1 3│1 2 4│2 3 5│ │ │0 1 4│1 2 5│2 4 5│ │ │0 1 5│1 3 4│ │ │ │0 2 3│1 3 5│ │ │ │0 2 4│1 4 5│ │ │ │0 2 5│ │ │ │ │0 3 4│ │ │ │ │0 3 5│ │ │ │ │0 4 5│ │ │ │ └─────┴─────┴─────┴─────┘ ┌─────┬─────┬─────┬─────┐ │0 1 2│1 2 3│2 3 4│3 4 5│ │0 1 3│1 2 4│2 3 5│ │ │0 1 4│1 2 5│2 4 5│ │ │0 1 5│1 3 4│ │ │ │0 2 3│1 3 5│ │ │ │0 2 4│1 4 5│ │ │ │0 2 5│ │ │ │ │0 3 4│ │ │ │ │0 3 5│ │ │ │ │0 4 5│ │ │ │ └─────┴─────┴─────┴─────┘
Other methods are described in [2]. The relative efficiencies of algorithms are parameter dependent. These can be tested informally by e.g.
time Each '9 comb 23';'9 comb2 23';'9 combi 23' ┌────────┬────────┬────────┐ │0.251543│0.173648│0.199808│ └────────┴────────┴────────┘ (n.b. combi had the trace removed for fair comparison)