# 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'
...
```