## combinations

APL-related discussions - a stream of APL consciousness.
Not sure where to start a discussion ? Here's the place to be
Forum rules
This forum is for discussing APL-related issues. If you think that the subject is off-topic, then the Chat forum is probably a better place for your thoughts !

### combinations

Having enumerated combinations, perhaps it’d be a good idea to examine how to create them. The problem: Given integers ⍺ and ⍵, produce the table of all size ⍺ combinations of ⍳⍵, in sorted order.

Double Recursion

I believe I saw this version in Gilman & Rose, APL: An Interactive Approach, Second Edition, 1976. Translated into current Dyalog APL:

`      ⍝comb← {(0=⍺)∨⍺=⍵:⍉⍪⍳⍺ ⋄ (0,1+(⍺-1)∇ ⍵-1)⍪1+⍺ ∇ ⍵-1}      4 comb 60 1 2 30 1 2 40 1 2 50 1 3 40 1 3 50 1 4 50 2 3 40 2 3 50 2 4 50 3 4 51 2 3 41 2 3 51 2 4 51 3 4 52 3 4 5`

A double recursion can often be made faster by use of a memo operator. From A History of APL in 50 Functions [Hui 2016, §16]:

`      ⍝M←{  f←⍺⍺  i←2+'⋄'⍳⍨t←3↓,⎕cr 'f'  0=⎕NC'⍺':⍎' {T←(1+  ⍵)⍴¯1 ⋄  {',(i↑t),'¯1≢T[⍵]  :⊃T[⍵]   ⋄ ⊃T[⍵]  ←⊂',(i↓t),'⍵}⍵'           ⍎'⍺{T←(1+⍺,⍵)⍴¯1 ⋄ ⍺{',(i↑t),'¯1≢T[⍺;⍵]:⊃T[⍺;⍵] ⋄ ⊃T[⍺;⍵]←⊂',(i↓t),'⍵}⍵'}      (4 comb 9) ≡ 4 comb M 91      cmpx '4 comb   9' '4 comb M 9'  4 comb   9 → 3.17E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕  4 comb M 9 → 1.30E¯4 | -60% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕      cmpx '14 comb   19' '14 comb M 19'  14 comb   19 → 3.09E¯2 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕  14 comb M 19 → 9.84E¯4 | -97% ⎕`

The efficacy of memo can be illustrated as follows: Modify comb to record the arguments in each function call:

`      ⍝combt← {t⍪←⍺,⍵ ⋄ (0=⍺)∨⍺=⍵:⍉⍪⍳⍺ ⋄ (0,1+(⍺-1)∇ ⍵-1)⍪1+⍺ ∇ ⍵-1}      t←0 2⍴0 ⋄ x←4 combt 9      ⍴t251 2      ⍴∪t29 2      t←0 2⍴0 ⋄ x←14 combt 19      ⍴t23255 2      ⍴∪t89 2`

For 4 comb 9, the number of function calls (to combt itself) is 251, but the number of function calls with unique arguments is just 29 -- and memo ensures that repeated calls with the same arguments are not recursed (do not engender further function calls).

Likewise, for 14 comb 19, the function call numbers are 23255 versus 89.

Single Recursion

The double recursion reduces to a single recursion by realizing that to produce ⍺ comb ⍵, it suffices to have
• The (⍺-1)comb(⍵-1) result.
• The number of times each element of ⍳1+⍵-⍺ occurs as a leading element. (Note that these are an instance of Pascal’s Ladder.)
The following is from Some Uses of { and } [Hui 1987, §4.1], translated into current Dyalog APL:

`      ⍝combS←{  (⍺=0)∨⍺=⍵:(1,⍺)⍴⍳⍺  c←(⍺-1)!(⍺-1)+⊖k←⍳1+⍵-⍺  (c⌿k), ⊃ ⍪⌿ (-c) ↑¨ ⊂1+(⍺-1)∇(⍵-1)}      m←4 ⋄ n←6(m-1)combS(n-1)            m combS n0 1 2                      0 1 2 30 1 3                      0 1 2 40 1 4                      0 1 2 50 2 3                      0 1 3 40 2 4                      0 1 3 50 3 4                      0 1 4 51 2 3                      0 2 3 41 2 4                      0 2 3 51 3 4                      0 2 4 52 3 4                      0 3 4 5                           1 2 3 4                           1 2 3 5                           1 2 4 5                           1 3 4 5                           2 3 4 5      c←(m-1)!(m-1)+⊖k←⍳1+n-m      ⍉ k,⍪c 0 1 210 4 1      ⍉ {⍺,≢⍵}⌸(m combS n)[;0] 0 1 210 4 1`

Power Operator

A non-recursive version obtains by use of the power operator.

`      ⍝combP←{c←1↑⍨-≢k←⍳1+⍵-⍺ ⋄ {c[]←⊖+⍀⊖c ⋄ (c⌿k), ⊃ ⍪⌿ (-c) ↑¨ ⊂1+⍵}⍣⍺ ⊢1 0⍴0}0 combP 2     1 combP 3      2 combP 4         3 combP 5        4 combP 6              0              0 1               0 1 2            0 1 2 3              1              0 2               0 1 3            0 1 2 4              2              0 3               0 1 4            0 1 2 5                             1 2               0 2 3            0 1 3 4                             1 3               0 2 4            0 1 3 5                             2 3               0 3 4            0 1 4 5                                               1 2 3            0 2 3 4                                               1 2 4            0 2 3 5                                               1 3 4            0 2 4 5                                               2 3 4            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 c in combP (the same as that in combS) is an instance of Pascal’s Ladder. Here it is computed without use of the ! binomial coefficient function, by using repeated plus scan.

`      {+⍀⍣⍵ ⊢10⍴1}⍤0 ⍳101  1  1   1   1    1    1     1     1     11  2  3   4   5    6    7     8     9    101  3  6  10  15   21   28    36    45    551  4 10  20  35   56   84   120   165   2201  5 15  35  70  126  210   330   495   7151  6 21  56 126  252  462   792  1287  20021  7 28  84 210  462  924  1716  3003  50051  8 36 120 330  792 1716  3432  6435 114401  9 45 165 495 1287 3003  6435 12870 243101 10 55 220 715 2002 5005 11440 24310 48620      ⍕ 0~⍨¨ ((⍳10)∘.≤⊖⍳10) × {+⍀⍣⍵ ⊢10⍴1}⍤0⍳10 1  1  1   1   1    1    1   1   1  1  1  2  3   4   5    6    7   8   9     1  3  6   10  15   21   28  36        1  4  10  20  35   56   84            1  5  15  35  70   126                1  6  21  56  126                     1  7  28  84                          1  8  36                              1  9                                  1`

(Misalignments in the display are due to defects in the APL Chat Forum software.)

If you tilt your head to the left and stare at the above matrices, Pascal’s triangle appears!
Roger|Dyalog

Posts: 208
Joined: Thu Jul 28, 2011 10:53 am

### Re: combinations

A New Wrinkle

Both combS and combP make clear that the main code is executed ⍺ times. As I was thinking about that, a new wrinkle came to me. Since ⍺!⍵ ↔ (⍵-⍺)!⍵, there should be a similar relationship between ⍺ comb ⍵ and (⍵-⍺)comb ⍵. If ⍵-⍺ is much smaller than ⍺ then it should be possible to compute ⍺ comb ⍵ more efficiently by way of (⍵-⍺)comb ⍵. And so it is.

`      ⍝combW←{  n← ⍺!⍵                                   b← 0 @ (, (⍵×⍳n) +⍤¯1 ⊢(⍵-⍺)combS ⍵) ⊢(n×⍵)⍴1  ⊖ (n,⍺) ⍴ b⌿ (n×⍵)⍴⍳⍵                     }      (16 combS 19) ≡ 16 combW 191      cmpx '16 combS 19' '16 combW 19'  16 combS 19 → 1.64E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕  16 combW 19 → 6.74E¯5 | -59% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕`

Conceptually, combW is equivalent to combW1, but is faster.

`      combW1 ← {⊖ (⍳⍵) ~⍤1 ⊢(⍵-⍺)combS ⍵}      cmpx '16 combS 19' '16 combW 19' '16 combW1 19'  16 combS 19  → 1.61E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕               16 combW 19  → 6.51E¯5 | -60% ⎕⎕⎕⎕⎕⎕⎕                         16 combW1 19 → 2.78E¯4 | +72% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕`
Roger|Dyalog

Posts: 208
Joined: Thu Jul 28, 2011 10:53 am