Essays/Combinations

Generate all size m combinations of i.n in sorted order. For example, the size 4 combinations of i.6 are:

The for. page of the dictionary contains a solution:

comb=: 4 : 0
 k=. i.>:d=.y-x
 z=. (d$<i.0 0),<i.1 0
 for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
 ; z
)

Within comb, k is a list of the possible leading digits, and successive values of z are the size m-j combinations of i.n-j , individually boxed according to the leading digit, for j = 0 1 2 ... m

   ] k=. i. >: d=.6-4
0 1 2

   ] z0=. (d$<i.0 0),<i.1 0
┌┬┬┐
││││
└┴┴┘
   $&.> z0
┌───┬───┬───┐
│0 0│0 0│1 0│
└───┴───┴───┘

   f=: 4 : 'x ,.&.> ,&.>/\. >:&.> y'
   k f^:(i.5) z0
┌───────┬───────┬───────┐
│       │       │       │
├───────┼───────┼───────┤
│0      │1      │2      │
├───────┼───────┼───────┤
│0 1    │1 2    │2 3    │
│0 2    │1 3    │       │
│0 3    │       │       │
├───────┼───────┼───────┤
│0 1 2  │1 2 3  │2 3 4  │
│0 1 3  │1 2 4  │       │
│0 1 4  │1 3 4  │       │
│0 2 3  │       │       │
│0 2 4  │       │       │
│0 3 4  │       │       │
├───────┼───────┼───────┤
│0 1 2 3│1 2 3 4│2 3 4 5│
│0 1 2 4│1 2 3 5│       │
│0 1 2 5│1 2 4 5│       │
│0 1 3 4│1 3 4 5│       │
│0 1 3 5│       │       │
│0 1 4 5│       │       │
│0 2 3 4│       │       │
│0 2 3 5│       │       │
│0 2 4 5│       │       │
│0 3 4 5│       │       │
└───────┴───────┴───────┘

combcheck has the same argument and result as comb , but incorporates checks:

combcheck=: 4 : 0
 assert. (0<:x)*.x<:y
 k=. i.>:d=.y-x
 z=. (d$<i.0 0),<i.1 0
 for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
 c=. ; z
 assert. ($c) -: (x!y),x
 assert. c -: /:~ c
 assert. c -: /:~"1 c
 assert. c -: ~. c
 assert. c -: ~."1 c
 assert. c e. i.y
)

comb1 is a slightly faster equivalent of comb .

comb1=: 4 : 0
 c=. 1 {.~ - d=. 1+y-x
 z=. i.1 0
 for_j. (d-1+y)+/&i.d do. z=. (c#j) ,. z{~;(-c){.&.><i.{.c=. +/\.c end.
)

comb2 is also equivalent to comb , but requires space (and time) exponential in the size of the result.

comb2=: ((= +/"1) |.@:I.@# ]) #:@i.@(2&^)

The following code produces the combinations spectrum.

   load 'viewmat'
   viewmat (".;]) '1 comb 8'
   ...

Essays/Combinations

See also