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

Postby Roger|Dyalog on Thu Jun 04, 2020 7:05 pm

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 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 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 9
1

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
⍴t
251 2
⍴∪t
29 2
t←0 2⍴0 ⋄ x←14 combt 19
⍴t
23255 2
⍴∪t
89 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 n
0 1 2 0 1 2 3
0 1 3 0 1 2 4
0 1 4 0 1 2 5
0 2 3 0 1 3 4
0 2 4 0 1 3 5
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

c←(m-1)!(m-1)+⊖k←⍳1+n-m
⍉ k,⍪c
0 1 2
10 4 1

⍉ {⍺,≢⍵}⌸(m combS n)[;0]
0 1 2
10 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 ⍳10
1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 10
1 3 6 10 15 21 28 36 45 55
1 4 10 20 35 56 84 120 165 220
1 5 15 35 70 126 210 330 495 715
1 6 21 56 126 252 462 792 1287 2002
1 7 28 84 210 462 924 1716 3003 5005
1 8 36 120 330 792 1716 3432 6435 11440
1 9 45 165 495 1287 3003 6435 12870 24310
1 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

Postby Roger|Dyalog on Fri Jun 05, 2020 5:05 am

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 19
1
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


Return to APL Chat

Who is online

Users browsing this forum: No registered users and 1 guest