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.