mat ← m ##.cmat n                           ⍝ ⍺-combination matrix of ⍳⍵.

Returns  an  m!n-row,  m-column, matrix of the m-item combination vectors of ⍳n.
Both  rows  and  row  items  of  the result are in ascending order, thus for any
⍺ ⍵≥0:

        {⍵≡⍳⍴⍵}⍋⍺ cmat ⍵            ⍝ Rows in ascending order.

        ∧/{{⍵≡⍳⍴⍵}⍋⍵}¨↓⍺ cmat ⍵     ⍝ Items in each row in ascending order.

Technical notes:

Notice that a combination matrix can be divided into sections, some of which are
themselves, combination matrices. For example:

                             ┌─┬───┐              ┌───┐
                  1 2 3      │1│2 3│              │1 2│
                  1 2 4      │1│2 4│              │1 3│
                  1 2 5      │1│2 5│      1 , 1 + │1 4│     1 , 1 + 2 cmat 4
                  1 3 4      │1│3 4│              │2 3│
    3 cmat 5  =>  1 3 5  =>  │1│3 5│  =>    ⍪     │2 4│  =>   ⍪
                  1 4 5      │1│4 5│              │3 4│
                  2 3 4      ├─┴───┤              └───┘
                  2 3 5      │2 3 4│              ┌─────┐
                  2 4 5      │2 3 5│          1 + │1 2 3│       1 + 3 cmat 4
                  3 4 5      │2 4 5│              │1 2 4│
                             │3 4 5│              │1 3 4│
                             └─────┘              │2 3 4│
                                                  └─────┘

This observation leads to the recurrence relationship:

    ⍺ cmat ⍵ ←→ (1,1+(⍺-1)cmat ⍵-1)⍪1+⍺ cmat ⍵-1

Successive transformations of the expression on the right, produce:

        Expression                              Transformation
        ----------                              --------------
        (1,1+(⍺-1)cmat ⍵-1)⍪1+⍺ cmat ⍵-1        [0] cmat → ∇
                  ¯¯¯¯          ¯¯¯¯
    →   (1,1+(⍺-1)∇⍵-1)⍪1+⍺ ∇⍵-1                [1] ⍺⍪⍵ → ↑⍪/⍺ ⍵
                       ¯
    →   ↑⍪/(1,1+(⍺-1)∇ ⍵-1)(1+⍺ ∇ ⍵-1)          [2] ⍺ ⍵ → ⌽ ⍵ ⍺
            ¯¯¯¯¯¯¯¯¯¯¯¯¯¯  ¯¯¯¯¯¯¯¯¯
    →   ↑⍪/⌽(1+⍺ ∇ ⍵-1)(1,1+(⍺-1)∇⍵-1)          [3] ⍺({}⍵) → {}\⍺ ⍵
                        ¯¯
    →   ↑⍪/⌽{1,⍵}\(1+⍺ ∇ ⍵-1)(1+(⍺-1)∇⍵-1)      [4] (1+⍺)(1+⍵) → 1+⍺ ⍵
                   ¯¯         ¯¯
    →   ↑⍪/⌽{1,⍵}\1+(⍺ ∇ ⍵-1)((⍺-1)∇⍵-1)        [5] (⍺{}⍵)(ß{}⍵) → ⍺ ß{}¨⊂⍵
                     ¯¯¯      ¯¯¯¯¯¯
    →   ↑⍪/⌽{1,⍵}\1+(⍺-0 1)¨∇⍵-1                [6]

Notice  transformation[3]:  ⍺({}⍵) → {}\⍺ ⍵,  which  applies  a  function to the
_second_  item of a 2-vector. Using this technique, we can avoid temporary local
names in situations such as:

    lft rgt←pair ⋄ lft({···⍵}rgt)           ⍝ clumsier.

    {···⍵}\pair                             ⍝ neater.

The base cases for the recursion are:

    0 cmat ⍵ → 1 0⍴0
    ⍺ cmat 0 → 0 ⍺⍴0

or:
    0∊⍺ ⍵:(⍺=0)⍺⍴0

The (index-origin independent) code is therefore:

    cmat←{                              ⍝ ⍺-combination matrix of ⍳⍵.
        0∊⍺ ⍵:(⍺=0)⍺⍴0                  ⍝ done if zero ⍺ or ⍵, otherwise,
        ↑⍪/⌽{⎕IO,⍵}\1+(⍺-0 1)∇¨⍵-1      ⍝ catenate sub-combinations.
    }

Notice  however,  that  the  algorithm is inefficient in the same way as a naïve
coding  of  →fibonacci←, in that the function is applied to the _same_ arguments
many  times  over. If we display the arguments for the function calls as a tree,
by injecting:

        ⎕←(,↑(⍴⎕LC)⍴⊂'·   '),'[',(⍕⍺ ⍵),']'

as the first line of the function, we see the following "dependency tree", where
[⍺ ⍵] stands for (⍺ cmat ⍵):

      2 cmat 4
·   [2 4]
·   ·   [2 3]
·   ·   ·   [2 2]
·   ·   ·   ·   [2 1]
·   ·   ·   ·   ·   [2 0]
·   ·   ·   ·   ·   [1 0]
·   ·   ·   ·   [1 1]
·   ·   ·   ·   ·   [1 0]
·   ·   ·   ·   ·   [0 0]
·   ·   ·   [1 2]
·   ·   ·   ·   [1 1]
·   ·   ·   ·   ·   [1 0]
·   ·   ·   ·   ·   [0 0]
·   ·   ·   ·   [0 1]
·   ·   [1 3]
·   ·   ·   [1 2]
·   ·   ·   ·   [1 1]
·   ·   ·   ·   ·   [1 0]
·   ·   ·   ·   ·   [0 0]
·   ·   ·   ·   [0 1]
·   ·   ·   [0 2]

This is interpreted:

    [2 4] depends on
    ·   [2 3] which depends on
    ·   ·   [2 2] which depends on
    ·   ·   ···
        and
    ·   ·   [1 2] which depends on     ⍝ [1 2] evaluated here.
    ·   ·   ···
    and
    ·   [1 3] which depends on
    ·   ·   [1 2] which depends on     ⍝ [1 2] evaluated again here.
    ·   ·    ···
··· and so on.

Notice  how [1 2], together with its whole sub tree, is evaluated twice. In this
case,  [2 4] generates 21 function calls. This number increases very rapidly and
in general, [⍵ ⍵] generates (¯1+2*⍵+1) calls.
                                                              ┌─┐     ┌───┐
The dependencies are better represented as a _lattice_, where │↑│ and │←--│ mean
"depends on":                                                 │|│     └───┘
                                                              └─┘
    [2 4]←--[2 3]←--[2 2]←--[2 1]←--[2 0]
    ↑       ↑       ↑       ↑
    |       |       |       |
    [1 3]←--[1 2]←--[1 1]←--[1 0]
    ↑       ↑       ↑
    |       |       |
    [0 2]   [0 1]   [0 0]

This expresses exactly the same recurrence relationship as the tree, except that
in  this representation, the nodes are _shared_. Notice how the lattice has only
12,  as opposed to the tree's 21 nodes. If we can find a way to evaluate each of
its nodes only once, a significant performance benefit should result.

In  fact,  we can do a little better than this. We chose [⍺ 0] and [0 ⍵] as base
cases for the recursion, because we can "conjure these results out of thin air".
Looking  at  the  lattice,  we see a column at the base of the "ramp", which has
values  [2 2] [1 1] [0 0].  As  we  know that [⍵ ⍵] = (1 ⍵⍴⍳⍵) for all ⍵, we can
equally  easily  use  [⍵ ⍵]  and [0 ⍵] as base cases, as long as we make special
provision  for starting values from _inside_ the ramp where ⍺>⍵. This enables us
to trim the lattice to:

    [2 4]←--[2 3]←--[2 2]
    ↑       ↑
    |       |
    [1 3]←--[1 2]←--[1 1]
    ↑       ↑
    |       |
    [0 2]   [0 1]

A slightly larger example (4 cmat 8), shows more clearly what's going on. Notice
that  this lattice has 24 nodes, while its corresponding dependency _tree_ would
have 325.

    [4 8]←--[4 7]←--[4 6]←--[4 5]←--[4 4]
    ↑       ↑       ↑       ↑
    |       |       |       |
    [3 7]←--[3 6]←--[3 5]←--[3 4]←--[3 3]
    ↑       ↑       ↑       ↑
    |       |       |       |
    [2 6]←--[2 5]←--[2 4]←--[2 3]←--[2 2]
    ↑       ↑       ↑       ↑
    |       |       |       |
    [1 5]←--[1 4]←--[1 3]←--[1 2]←--[1 1]
    ↑       ↑       ↑       ↑
    |       |       |       |
    [0 4]   [0 3]   [0 2]   [0 1]

The  diagram  suggests  using  right-to-left  or  bottom-to-top  _reduction_  to
accumulate  values towards the top left corner which is the required result. For
reasons  that  will  become apparent, reduction from the right turns out to be a
slightly better bet. Using ⎕ML←2, so that "↑" means "first":

    ↑↑{⍺···⍵}/ [0 4] ··· [0 2] [0 1] ,⊂ [4 4] ··· [2 2] [1 1]

Now,  as  the  [0 ⍵]'s  all have the same value: (1 0⍴0), we can substitute this
value for ⍺ _inside_ the reduction's operand and ignore the value that is passed
into  the  operand function as left argument. This means that we may replace the
vector [0 4] ··· [0 2] [0 1] by _any_ vector providing it has the same number of
items:  (⍳⍵-⍺) will suffice.

    ↑↑{(1 0⍴0)···⍵}/ (⍳⍵-⍺),⊂ [4 4] ··· [2 2] [1 1]

Finally,  to  squeeze out the last drop of refinement, we can compute the little
array  (1 0⍴0)  just  once and bind it as an operand to the reduction's operand,
where it becomes "⍺⍺".

    ↑↑(1 0⍴0){⍺⍺···⍵}/ (⍳⍵-⍺),⊂ [4 4] ··· [2 2] [1 1]

The base cases: [4 4] ··· [2 2] [1 1], evaluate to ({1 ⍵⍴⍳⍵}¨+\⍺⍴1), noting that
(+\⍺⍴1) is an origin independent expression for "1 to ⍺", which gives:

    ↑↑(1 0⍴0){⍺⍺···⍵}/ (⍳⍵-⍺),⊂{1 ⍵⍴⍳⍵}¨+\⍺⍴1

At this point, we can cover the "special provision" for the null case where ⍺>⍵.
The result is a matrix of shape (0 ⍺), so the reshape becomes: (⍺≤⍵){⍺ ⍵⍴⍳⍵}.

    ↑↑(1 0⍴0){⍺⍺···⍵}/ (⍳⍵-⍺),⊂(⍺≤⍵){⍺ ⍵⍴⍳⍵}¨+\⍺⍴1

Now  all  that  remains,  is  to  code  the workings of the reduction's operand:
{⍺⍺···⍵}. Each application of the operand will take a _column_ of the lattice as
right argument and a nominal [0 ⍵] as left operand.

Transposing  the  rightmost  column  of  the  lattice above, the operand will be

applied to:    ⍵: [4 4]   [3 3]   [2 2]   [1 1]  ⍺⍺: [0 1]
                  ↓       ↓       ↓       ↓          ↓
with result:      [4 5]←--[3 4]←--[2 3]←--[1 2]←-----'

To  achieve  this  result,  we need to do a further, but this time, _cumulative_
reduction. Without accumulation, the result of the "inner" reduction in the case
above  would be [4 5], whereas we need the whole vector [4 5] ··· [1 2], but ex-
cluding the initial base case ⍺⍺:[0 1], to pass back to the outer reduction. The
template for such a reduction is:

    ¯1↓↑{(⍺ ··· ↑⍵),⍵}/(⊂···),···,(⊂···),(⊂⊂···)
      ││     │  │  │    │          │      └────── _Extra_ rightmost enclosure,
      ││     │  │  │    │          │                      for accumulation.
      ││     │  │  │    └──────────┴───────────── Items of reduction argument.
      ││     │  │  └─── Prefix new result item to accumulation.
      ││     │  └────── First item of accumulated result.
      ││     └───────── Operation between successive left and right args.
      │└─────────────── Disclose vector result of vector reduction.
      └──────────────── Discard initial base case ⍺⍺:[0 1].

Substituting our specific cases:

    ¯1↓↑{(⍺ ··· ↑⍵),⍵}/⍵,⊂⊂⍺⍺

The  remaining "···" is exactly the expression developed right back at the start
for the "tree" algorithm: ⍪/⌽{⎕IO,⍵}\1+···, so the complete operand function is:

    ¯1↓↑{(⍪/⌽{⎕IO,⍵}\1+⍺(↑⍵)),⍵}/⍵,⊂⊂⍺⍺

A last tweak is to "factor out" (⊂⊂⍺⍺) to where ⍺⍺ is generated, so that:

        ···(1 0⍴0){···{···}/⍵,⊂⊂⍺⍺}/···
becomes:    __                ¯¯
        ···(⊂⊂1 0⍴0){···{···}/⍵,⍺⍺}/···

The final code looks like this. Notice that apart from the specification of ⎕ML,
it's  a one-liner. More to the point, there are no assignments, tests or control
branches; it is a single expression:

    cmat←{⎕ML←2                             ⍝ ⍺-combination matrix of ⍳⍵.
        ↑↑(⊂⊂1 0⍴0){                        ⍝ base-case: [0 ⍵].
            ¯1↓↑{                           ⍝ removing base case from,
                (⍪/⌽{⎕IO,⍵}\1+⍺(↑⍵)),⍵      ⍝ accumulation of,
            }/⍵,⍺⍺                          ⍝ sub- (⍺ ⍵-1) combinations,
        }/(⍳0⌈⍵-⍺),⊂(⍺≤⍵){⍺ ⍵⍴⍳⍵}¨⌽+\⍺⍴1    ⍝ with base cases [⍺ 0].
    }

Alternative codings
-------------------
John  Niss  Hansen  suggests  the  following  much  simpler coding. Effectively,
the  function  generates  all binary numbers of width ⍵ and selects those with ⍺
bits set. Each binary "mask" is then used to select a different ⍺ combination of
numbers  from  0  to ⍵-1.  This  works  well  for small values of ⍵ but the sub-
expression  (⍳⍵⍴2)  uses  an  exponential  amount  of space (and time) as ⍵ gets
larger. The function assumes ⎕io=0.

      cmat←{↑⌽((⍺=+/¨t)/t←,⍳⍵⍴2)/¨⊂⍳⍵}

VMJ suggests the following one-line speedy alternative for small-to-medium sized
results.

      cmat←{⎕ML←3 ⋄ ⊃⊃{{(</2↑[⎕IO+1]⊃⍵)/⍵},⍺∘.,⍵}/(⍳⍺)+⊂(-⎕IO)+⍳⍵-⍺-1}

and also:

      cmat←{
           (⎕IO ⎕ML)←1 3 ⋄ wd←⍺ ⋄ mx←⍵
           ⊃↑2{⍺>wd:⍵
               a←2⊃⍵
               b←mx-a+wd-⍺ ⋄ q←∊a+⍳¨b
               (⍺+1)∇((b/↑⍵),¨q)q
           }2⍴⊂⍳⍵-⍺-1
       }

This  version  is based on Ken Gradney's code, which was published in Vector Vol
18.1:

      cmat←{
          ⎕ML←3 ⋄ n←1+⍵-⍺ ⋄ c←(⍺-1)+⍳n

          c{⎕IO≥↑⍺:↑⍵
              m←⌽+\⌽↑1↓⍵
              (⍺-1)∇((m/⍺-1),(↑⍵)[∊((↑m)-m)+⍳¨m;])m
          }((n,1)⍴c)(n⍴1)
      }


Roger Hui proposes this short coding:

      cmat←{⊖⊃⍪/{k,¨⍪\1+⍵}⍣⍺⊢(⊂⍉⍪⍬),d⍴⊂0 0⍴k←⌽⍳1+d←⍵-⍺}

which  is  faster than the others except on really large arguments (when it is a
bit slower).

Roger says:  The ⊖ is needed because Dyalog does not have "suffix scan" (⊖f⍀⊖⍵).
I am led to doing the regular APL scan on the reversed argument,  then reversing
the whole thing at the end.

Examples:

      display 0 cmat 5
┌⊖┐
↓0│
└~┘

      display 1 cmat 5
┌→┐
↓1│
│2│
│3│
│4│
│5│
└~┘

      display 2 cmat 5
┌→──┐
↓1 2│
│1 3│
│1 4│
│1 5│
│2 3│
│2 4│
│2 5│
│3 4│
│3 5│
│4 5│
└~──┘

      display 3 cmat 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│
└~────┘

      display 4 cmat 5
┌→──────┐
↓1 2 3 4│
│1 2 3 5│
│1 2 4 5│
│1 3 4 5│
│2 3 4 5│
└~──────┘

      display 5 cmat 5
┌→────────┐
↓1 2 3 4 5│
└~────────┘

      display 6 cmat 5
┌→──────────┐
⌽0 0 0 0 0 0│
└~──────────┘

      ⍉↑{⍴⍵ cmat 5}¨0 to 6                      ⍝ Row and column sizes.
1 5 10 10 5 1 0
0 1  2  3 4 5 6

      2{⍵[⍺ cmat⍴⍵]}'scissors' 'paper' 'stone'  ⍝ 2-combos of nested vector.
 scissors  paper
 scissors  stone
 paper     stone

      ↓3{⍵[⍺ cmat⍴⍵]}'abcde'                    ⍝ 3-combos of char vector.
 abc  abd  abe  acd  ace  ade  bcd  bce  bde  cde

      display¨0 1 2 3∘.cmat 0 1 2 3             ⍝ Combos of small vectors.
 ┌⊖┐      ┌⊖┐      ┌⊖┐      ┌⊖┐
 ↓0│      ↓0│      ↓0│      ↓0│
 └~┘      └~┘      └~┘      └~┘
 ┌→┐      ┌→┐      ┌→┐      ┌→┐
 ⌽0│      ↓1│      ↓1│      ↓1│
 └~┘      └~┘      │2│      │2│
                   └~┘      │3│
                            └~┘
 ┌→──┐    ┌→──┐    ┌→──┐    ┌→──┐
 ⌽0 0│    ⌽0 0│    ↓1 2│    ↓1 2│
 └~──┘    └~──┘    └~──┘    │1 3│
                            │2 3│
                            └~──┘
 ┌→────┐  ┌→────┐  ┌→────┐  ┌→────┐
 ⌽0 0 0│  ⌽0 0 0│  ⌽0 0 0│  ↓1 2 3│
 └~────┘  └~────┘  └~────┘  └~────┘

      ⎕io←0 ⋄ 2 cmat 4                          ⍝ Code is "origin sensitive".
0 1
0 2
0 3
1 2
1 3
2 3

      ⍉ ∘.{⍬⍴⍴⍺ cmat ⍵}⍨ 0 to 12                ⍝ Pascal's triangle.
1  0  0   0   0   0   0   0   0   0  0  0 0
1  1  0   0   0   0   0   0   0   0  0  0 0
1  2  1   0   0   0   0   0   0   0  0  0 0
1  3  3   1   0   0   0   0   0   0  0  0 0
1  4  6   4   1   0   0   0   0   0  0  0 0
1  5 10  10   5   1   0   0   0   0  0  0 0
1  6 15  20  15   6   1   0   0   0  0  0 0
1  7 21  35  35  21   7   1   0   0  0  0 0
1  8 28  56  70  56  28   8   1   0  0  0 0
1  9 36  84 126 126  84  36   9   1  0  0 0
1 10 45 120 210 252 210 120  45  10  1  0 0
1 11 55 165 330 462 462 330 165  55 11  1 0
1 12 66 220 495 792 924 792 495 220 66 12 1

See also: pmat fibonacci rr

Back to: contents

Back to: Workspaces