APL combinations generator function

Let it all hang out

APL combinations generator function

PostPosted by manandpc » Thu Aug 16, 2012 2:54 pm

The primitive K ! N gives the number of combinations (without repetition) :
where K ! N is ( ! N ) ÷ ( ! N-K ) × ! K

Here is an optimize APL function (1 line) to generate all the combinations for K ! N
Code: Select all
      ⎕cr'comb'
z←a comb b
z←⊃⍸¨⊂[⎕IO]⌽(b⍴2)⊤(-⎕IO)+⍸a=(2*b)↑∊z∘.+z←((⌈b÷2)⍴2)⍴z∘.+z←z∘.+z←z∘.+z←z∘.+z←0 1
where ( (K ! N) K ) = ⍴K comb N

And a very fast combinations generator is this one:
Code: Select all
      ⎕cr'comb'
z ← a comb b;c
:if a ≤ 1 ⋄ z ← ⍪⍳b
:else
  :if a < b
    z ← 1+(a-1) comb b-1 ⋄ c ← ⌽(a-1)!(a-1+⎕IO)+⍳b-a
    z ← (⎕IO,z)⍪(c/1+⍳b-a),z[∊(((a-1)!b-1)-c)+⍳¨c;]
  :else
    z ← ⎕IO,1+(a-1) comb b-1
  :endif
:endif

      ⍝ Algorithm , recursive blocks by example
     
      1 0⍕⍉4 comb 8
1111111111111111111111111111111111122222222222222222222333333333344445
2222222222222223333333333444444555633333333334444445556444444555655566
3333344445556674444555667555667667744445556675556676677555667667766777
4567856786787885678678788678788788856786787886787887888678788788878888
     
      ⎕←c ← 1 0⍕⍉1+3 comb 7
22222222222222233333333334444445556
33333444455566744445556675556676677
45678567867878856786787886787887888
     
((⊂1 0⍕35⍴1),((3!⌽2+⍳4)/¨1 0⍕1+⍳4)),[0.5](c)(c[;15+⍳20])(c[;25+⍳10])(c[;31+⍳4])(c[;34+⍳1])
 11111111111111111111111111111111111  22222222222222222222  3333333333  4444  5
                                                                               
 22222222222222233333333334444445556  33333333334444445556  4444445556  5556  6
 33333444455566744445556675556676677  44445556675556676677  5556676677  6677  7
 45678567867878856786787886787887888  56786787886787887888  6787887888  7888  8

      ⎕cr'combit'
z ← a combit b;c
:if a ≤ 1 ⋄ z ← (b,b)⍴1,b⍴0
:else
  :if a < b
    z ← (a-1) combit b-1 ⋄ c ← ⌽(a-1)!(a-1+⎕IO)+⍳b-a
    z ← (1,z)⍪(-c)⌽1,(c ← c/(1-⎕IO)+⍳b-a)⌽z[∊(((a-1)!b-1)-c)+⍳¨c;]
  :else
    z ← 1,(a-1) combit b-1
  :endif
:endif
Example:
Code: Select all
      ⎕IO←1
      3 comb 5
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
      ⍴3 comb 5
10 3
      (3!5) 3
10 3
      ⎕IO←0
      3 comb 5
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
      'THING'[3 comb 5]
THI
THN
THG
TIN
TIG
TNG
HIN
HIG
HNG
ING

Note: The algorithm is very fast because it is using only ONE recursive call to construct the combinations

4 comb 8 =
1111111111111111111111111111111111122222222222222222222333333333344445
2222222222222223333333333444444555633333333334444445556444444555655566
3333344445556674444555667555667667744445556675556676677555667667766777
4567856786787885678678788678788788856786787886787887888678788788878888

1 + (3 comb 7) =
22222222222222233333333334444445556
33333444455566744445556675556676677
45678567867878856786787886787887888

22222222222222233333333334444445556
33333444455566744445556675556676677
45678567867878856786787886787887888

22222222222222233333333334444445556
33333444455566744445556675556676677
45678567867878856786787886787887888

22222222222222233333333334444445556
33333444455566744445556675556676677
45678567867878856786787886787887888

22222222222222233333333334444445556
33333444455566744445556675556676677
45678567867878856786787886787887888

All the bold values are put together to form =
22222222222222233333333334444445556 33333333334444445556 4444445556 5556 6
33333444455566744445556675556676677 44445556675556676677 5556676677 6677 7
45678567867878856786787886787887888 56786787886787887888 6787887888 7888 8

Out of 5 blocks with putting the block number on top , give 4 comb 8 =
11111111111111111111111111111111111 22222222222222222222 3333333333 4444 5
22222222222222233333333334444445556 33333333334444445556 4444445556 5556 6
33333444455566744445556675556676677 44445556675556676677 5556676677 6677 7
45678567867878856786787886787887888 56786787886787887888 6787887888 7888 8
manandpc
 
Posts: 67
Joined: Tue Jun 19, 2012 9:39 am

Re: APL combinations generator function

PostPosted by forummaster » Tue Jun 06, 2017 9:39 am

Sorry for the delay in responding. Thanks for your note about generating combinations. You helped spur me on to implement a more general Combinatorial Operator now available in the latest Alpha version:

http://www.nars2000.org/download/binaries/alpha/

and as described in the Wiki:

http://wiki.nars2000.org/index.php/Combinatorial

This operator consolidates into a common framework both the enumeration and generation of the fundamental Combinatorial Algorithms for Combinations, Permutations, Multisets, Tuples, three types of Partitions of a Number, and three types of Partitions of a Set, all written in C using high quality algorithms mostly from D. E. Knuth's TAoCP, "Combinatorial Algorithms", Vol 4A.

Thanks again very much for your suggestion. I kept it in mind over all these years until I finally came across Rota's Twelvefold Way of organizing various Combinatorial Algorithms which struck me as ideally suited to an implementation in APL.
forummaster
 
Posts: 555
Joined: Wed Jan 23, 2013 1:00 pm


Return to Open Discussion

Who is online

Users browsing this forum: No registered users and 1 guest

cron