22. Combinations

{(⍺=0)∨⍺=⍵:⍉⍪⍳⍺ ⋄ (0,1+(⍺-1)∇ ⍵-1)⍪1+⍺ ∇ ⍵-1}

Generate all size m combinations of ⍳n in sorted order. For example, the size 4 combinations of ⍳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

A doubly-recursive comb can be found in the venerable APL: An Interactive Approach by Gilman and Rose [78], rendered in modern APL as follows:

comb←{(⍺=0)∨⍺=⍵:⍉⍪⍳⍺ ⋄ (0,1+(⍺-1)∇ ⍵-1)⍪1+⍺ ∇ ⍵-1}

Like other multiply-recursive functions, this definition suffers from poor performance. The performance can be greatly improved by use of the memo operator from Chapter 16. comb M provides a good balance between simplicity and efficiency.

A faster comb is possible without memo, but it’s not easy. For example, from [49d]:

comb87←{
  (⍺=0)∨⍺=⍵:⍉⍪⍳⍺
  (c/k),⊃⍪⌿(-c)↑¨⊂1+(⍺-1)∇(⍵-1) ⊣ c←(⍺-1)!(⍺-1)+⌽k←⍳1+⍵-⍺
}