Essays/Combinations

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

   4 comb 6
0 1 2 3
0 1 2 4
0 1 2 5
0 1 3 4
0 1 3 5
0 1 4 5
0 2 3 4
0 2 3 5
0 2 4 5
0 3 4 5
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5

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 champion implementation to date (for time and space) is R. E. Boss's (he called it comB3 in the Vector article referred to below):

comb=: 4 : 0
  if. x e. 0 1 do. z=.<((x!y),x)$ i.y
  else. t=. |.(<.@-:)^:(i.<. 2^.x)x
    z=.({.t) ([:(,.&.><@;\.)/ >:@-~[\i.@]) ({.t)+y-x
    for_j. 2[\t do.
      z=.([ ;@:(<"1@[ (,"1 ({.j)+])&.> ])&.> <@;\.({&.><)~ (1+({.j)-~{:"1)&.>) z
      if. 2|{:j do. z=.(i.1+y-x)(,.>:)&.> <@;\.z end.
    end.
  end.
  ;z
)

This boolean version created by Erling Hellenäs is faster and uses less memory than the versions above.

combbool=: 4 : 0
k=. <"1 (-i.1+d=.y-x)|."0 1 y{.1
z=. (d$<(0,y)$0),<,:y#0
for. i.x do. z=. k (+."1)&.> ,&.>/\. (_1&|."1)&.> z end.
; z
)

The following code produces the combinations spectrum.

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

---

See also

• Article by R.E. Boss in Vector, Volume 24, Number 2
• Combination Index
• Combination Sums
• Permutations
• Next Binary String

---

Contributed by Roger Hui, with additional contributions by Oleg Kobchenko.