Combinatorial

Z←a‼R returns an array whose values depend upon which Combinatorial Function is chosen by the left operand a.

R is a non-negative numeric scalar or one- or two-element vector. If R has only one element, it is treated as if the value were duplicated as in 2⍴R. For convenience in the description below, the two elements are referred to as M and N as in (M N)←2⍴R.

a is a non-negative numeric scalar or one- or two- element vector which serves as the Selector for the Twelve Combinatorial Functions. The first element (Function Selector) in a is a non-negative integer for each of the Twelve functions (where the number is written here as a decimal number with three digits to emphasize that each digit has a separate meaning): 000   M Pigeons in N holes 001   Partitions of the number M into no more than N parts 002   Partitions of the number M into N parts 010   M Combinations of N items 011   M Multisets of N items 012   Compositions of the number M into N parts   a.k.a. Partitions of the number M into N ordered parts 100   M Pigeons in N holes 101   Partitions of the set {⍳M} into no more than N parts 102   Partitions of the set {⍳M} into N parts 110   M Permutations of N items 111   M Tuples of N items 112   Partitions of the set {⍳M} into N ordered parts

The second element (Count/Generate Flag) in a is an optional Integer value where 0 (the default) means Count the number of elements in the Combinatorial Function as applied to R and values greater than 0 mean generate the array of elements. If the Generate Flag is 1, generate the array in an unspecified order. Certain Function Selectors (see the individual Combinatorial Functions) accept values greater than 1. In particular, the value 2 generates the array in Lexicographic order, and 3 generates the array in Gray Code order.

The symbol ‼ (U+203C) can be entered from the default keyboard layout with Alt-’k’ or Ctrl-’k’, depending upon your choice of keyboard layouts.

Introduction

Counting and generating items is fundamental in mathematics, but has been sorely lacking in APL (notwithstanding the counting functions !N and M!N); instead we have had to rely upon a patchwork of various library routines.

Moreover, most APL papers on the topic have focused on the implementation of the algorithms rather than their organization and syntax mostly because, at the time, there was no unifying concept nor common syntax.

The main purpose of this document is to present in APL a unified organizing principle to classify and access various Combinatorial Algorithms.

A secondary purpose is to shed light on the relationships between the various algorithms through a new perspective provided by Gian-Carlo Rota’s clever way to fit them into a single organizational framework.

The goal of this document is to describe a single APL primitive to both Count and Generate various Combinatorial Arrays: permutations, combinations, compositions, partitions, etc. The unifying (and very APL-like) principle for such a primitive is Gian-Carlo Rota's Twelvefold Way as described in Richard Stanley's "Enumerative Combinatorics" and Knuth’s TAoCP, Vol. 4A among other references.

The Twelvefold Way

This elegant notion consolidates twelve Combinatorial Algorithms into a single 2×2×3 array based on the simple concept of placing balls into boxes (urns, to you old-timers). The three dimensions of the array can be described as follows:

• The Balls may be labeled (or not) {2 ways},
• The Boxes may be labeled (or not) {2 ways}, and
• The Capacity of Balls in a Box may be one of (at most one | unrestricted | at least one) {3 ways}.

Amazingly, these twelve choices spanning three dimensions knit together within a single concept (balls in boxes) all of the following interesting, fundamental, and previously disparate and disorganized Combinatorial Algorithms:

• Permutations
• Combinations
• Compositions
• Multisets
• Partitions of a set
• Partitions of a number
• Tuples
• Pigeon Holes

As mentioned above, although the first element of the Function Selector is an integer, it is written here with three digits to emphasize that each digit has a separate meaning. Those meanings are exactly related to the 2×2×3 array mentioned above.

• The first digit represents the Balls as Unlabeled (0) or Labeled (1)
• The second digit represents the Boxes as Unlabeled (0) or Labeled (1)
• The third digit represents the Capacity of Balls in a Box as one of At most One (0), Unrestricted (1), or At Least One (2).

For example:

• A function selector of 010 means unlabeled balls (0), labeled boxes (1), and at most one ball per box (0). If we have 2 unlabeled balls (●●) and 4 labeled boxes (1234) with at most one ball per box, there are 6 (↔ 2!4) ways to meet these criteria:

  ● ●         1 2 3 4

  ● ●     1 2 3 4

  ●         ● 1 2 3 4

  ● ●     1 2 3 4

  ●     ● 1 2 3 4

  ● ● 1 2 3 4

  ⇐ Box Contents ⇐ Box Labels (blank = Unlabeled)

  from which it is easy to see that these criteria correspond to M combinations of N items (↔ M!N).

  ► Notice how we obtain the generated answer as a 6×M matrix. In this example, it is obtained by reading the Box Labels in ascending order (6 M⍴1 2, 1 3, 1 4, 2 3, 2 4, 3 4). Also note that because each individual Combination is always written in ascending order, that explains why the Function Selector uses Unlabeled Balls and Labeled Boxes with At Most One Ball per Box. That is, the use of Unlabeled Balls forces us to read in ascending order the labels on the Labeled Boxes; because there are M Balls and At Most One Ball Per Box we are assured of obtaining exactly M box labels per row.
• A function selector of 110 means labeled balls (1), labeled boxes (1), and at most one ball in each box (0). If we have 3 labeled balls (❶❷❸) and 3 labeled boxes (123) with at most one ball per box, there are 6 (↔ !⍠¯3 3 ↔ 3×2×1) ways to meet these criteria:

  ❶ ❷ ❸ 1 2 3

  ❷ ❶ ❸ 1 2 3

  ❷ ❸ ❶ 1 2 3

  ❶ ❸ ❷ 1 2 3

  ❸ ❶ ❷ 1 2 3

  ❸ ❷ ❶ 1 2 3

  If we have 2 labeled balls (❶❷) and 3 labeled boxes (123) with at most one ball per box, there are 6 (↔ !⍠¯2 3 ↔ 3×2) ways to meet these criteria:

  ❶ ❷     1 2 3

  ❷ ❶     1 2 3

  ❷     ❶ 1 2 3

  ❶     ❷ 1 2 3

  ❶ ❷ 1 2 3

  ❷ ❶ 1 2 3

  from which it is easy to see that these criteria correspond to M permutations of N items. When M=N, this is the # permutations of ⍳N, (↔ !N), and when M<N, this is the # M-permutations, also called the Falling Factorial (!⍠((-M) N)).

  ► Notice how we obtain the generated answer as a 6×M matrix differently from the Combinations example. In the two Permutations examples, it is obtained by reading the Box Labels in ascending order of the Ball Labels. For the first Permutations example (with M=3), the generated answer is 6 M⍴1 2 3, 2 1 3, 3 1 2, 1 3 2, 2 3 1, 3 2 1, and for the second one (with M=2), it is 6 M⍴1 2, 2 1, 3 1, 1 3, 2 3, 3 2. It is common to need a different method of generating the answer for many of these Combinatorial Algorithms.

As a side note, the above examples reveal one of the many insights the Twelvefold Way provides into Combinatorial Algorithms. Previously, you might not have seen any connection between the algorithms for Combinations and Permutations, but, as the above examples show, they are closely related in that they differ only in the use of labeled (1) vs. unlabeled (0) balls; both algorithms use labeled boxes (1) with at most one ball per box (0).

Labeled vs. Unlabeled

Boxes

For most cases, the boxes are the columns of the result. Two or more labeled boxes may hold identical content, but because the boxes are labeled, they are considered distinct. On the other hand, unlabeled boxes with identical content are indistinguishable. For example, the following (partial) configurations of 3 unlabeled balls (●●●) in 3 unlabeled boxes

● ● ●

● ● ●

● ● ●

are all considered equivalent and are counted only once because the boxes are unlabeled.

Similarly, the following (partial) configurations of 3 labeled balls (❶❷❸) in 2 unlabeled boxes

❶ ❷ ❸

❸ ❶ ❷

❷ ❶ ❸

❸ ❷ ❶

are also all considered equivalent and are counted only once, again because the boxes are unlabeled.

Note that the order of the (labeled) balls within a box is ignored which means that even if the boxes were labeled, the first and third configurations above are equivalent, as are the second and fourth.

Balls

In a similar manner, the counts and generations for combinations (010) and permutations (110) differ by a factor of !M, this time because of the balls: one is unlabeled and the other labeled. That is, the count for M combinations of N items is

M!N ↔ (!N)÷(!N-M)×!M

and the count for M permutations of N items is

!⍠((-M) N) ↔ (!N)÷!N-M

Of course, when M=N, the permutation count is the familiar !N.

The Functions

The array of functions can be displayed as follows in a table organized by the Function Selector:

FS Table	Balls Per Box
	At Most One xx0	Unrestricted xx1	At least One xx2
M unlabeled balls 00x N unlabeled boxes	M pigeons 000 into N holes	partitions of M 001 into ≤N parts	partitions of M 002 into N parts
M unlabeled balls 01x N labeled boxes	M-combinations    010 of N items	M-multisets 011 of N items	compositions of M 012 into N parts
M labeled balls 10x N unlabeled boxes	M pigeons 100 into N holes	partitions of {⍳M}    101 into ≤N parts	partitions of {⍳M}    102 into N parts
M labeled balls 11x N labeled boxes	M-permutations 110 of N items	M-tuples 111 of N items	partitions of {⍳M} 112 into N ordered parts

Click on one of the above colored cells to see more detail on that function.

Examples

► Almost without exception, the counts for these functions grow quite rapidly as the arguments increase (hence the term Combinatorial Explosion). It's a good idea to check the Count value before trying to Generate the corresponding array.

The expression 110‼M N produces M Permutations of N items. When M=N, it represents the usual Permutation function.

      110‼3     ⍝ Count the !3 Permutations
6
      110 1‼3   ⍝ Generate the !3 Permutations
1 2 3
1 3 2
3 1 2
3 2 1
2 3 1
2 1 3
      110 2‼3 ⍝ Generate the !3 Permutations in Lexicographic order
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
      110 1‼2 3 ⍝ Generate the 2 Permutations of 3 items
1 2
2 1
1 3
3 1
2 3
3 2
      perm←{110 1‼⍵} ⍝ Permutation function
      perm 3
1 2 3
1 3 2
3 1 2
3 2 1
2 3 1
2 1 3

The expression 10‼M N produces M Combinations of N items.

      comb←{10 1‼⍺ ⍵} ⍝ Combinations function
      3 comb 5
1 2 3
1 2 4
1 3 4
2 3 4
1 2 5
1 3 5
2 3 5
1 4 5
2 4 5
3 4 5
      10 2‼3 5 ⍝ Combinations in Lexicographic order
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

The expression 1‼M N produces Partitions of M into at most N parts (as a nested array).

      1‼7 3
8
      ⍪1 1‼7 3
 7     
 6 1   
 5 2   
 5 1 1 
 4 3   
 4 2 1 
 3 3 1 
 3 2 2

If you have seen the movie “The Man Who Knew Infinity” (2015) (about the life and academic career of the brilliant Indian mathematician Srinivasa Ramanujan), you may recall that at one point it focuses on the problem of calculating p(200) — the number of Partitions of the number 200 into at most 200 parts. This number can be calculated by

      1‼200
3972999029388

in a few hundred-thousandths of a second.

Special Cases

The problem of counting Partitions of M Into At Most M Parts has been well studied. As alluded to above, the brilliantly intuitive Indian mathematician Srinivasa Ramanujan along with G. H. Hardy and Hans Rademacher have provided a convergent series which can produce an exact value for this number. Fortunately, this algorithm (referred to as Hardy-Ramanujan-Rademacher or HRR) has been coded by Frederik Johansson using the open source library MPFR (Multiple Precision Floating Point) and is available in the open source library FLINT (Fast Library for Number Theory). This code is used for the function 1‼M when M is in the range 395 < M < 2³¹ on the 32-bit version of NARS2000, and in the range 395 < M < 2⁶³ on the 64-bit version. The code is so efficient that it can calculate 1‼1E12 in under a minute (on a 64-bit machine only!). However, if you try this, be sure to assign the result to a variable as otherwise it will display a number with 1,113,996 digits!

Correspondingly, because partitions of M into N non-negative parts (001) is the same as partitions of N+M into N positive parts (002), (i.e., 1‼M N ←→ 2‼(M+N) N), the case of 2‼(2×M) M also takes advantage of the fast algorithm.

Memoization

This technique is a form of caching used to speed up certain algorithms, particularly recursive ones.

Two of the Combinatorial Functions (001 and 002) are dependent on the following recurrence relation for Partition Numbers defined on integer n and k:

P(0,0) = 1
P(n,k) = 0				for n≤0 or k≤0
P(n,k) = P(n-k,k) + P(n-1,k-1)

Within a session of the interpreter, these values are cached internally so that subsequent requests for already calculated Partition Numbers are sped up significantly.

Three other Combinatorial Functions (101, 102, and 112) are dependent on the Stirling numbers of the 2nd kind. They satisfy the following recurrence relation defined on integer n≥0 and k≥0:

S(0,0) = 1
S(0,n) = S(n,0) = 0			for n>0
S(n,k) = k × S(n-1,k) + S(n-1,k-1)

These numbers are also cached internally by the interpreter so as to speed up subsequent access.

In case you need to clear the cache so as to time the internal algorithms starting with an empty cache, use the expression

      ∘‼1
Cache cleared

Note that this expression does not clear certain caching internal to the above HRR algorithm in FLINT.

History

The idea of consolidating these twelve algorithms into a single primitive is credited to Gian-Carlo Rota through a series of lectures given at the Massachusetts Institute of Technology (MIT). The mathematics behind the Twelvefold Way is described in several places, most notably in Richard Stanley's Enumerative Combinatorics, and Wikipedia. The name was suggested by Joel Spencer.

Implementation

This Combinatorial Operator is implemented in the Released version of NARS2000 and may be downloaded from here. For an in-depth look at the Twelvefold Way and its implementation in APL, see Smith's paper.

Conclusions

• Rota’s amazing Twelvefold Way of consolidating numerous Combinatorial Algorithms through the unifying concept of Balls in Boxes into a single organizational framework is presented and each algorithm is discussed in detail with examples.
• This organizational framework is ideally suited for implementation in APL for both counting and generation by referencing the individual algorithms using a function selector as the (left) operand to a new monadic primitive operator.
• Insight into these Combinatorial Algorithms is gained when viewed from the perspective of the Twelvefold Way. To wit:
  • The relationships among the algorithms is made clearer when comparing their APL versions, especially through identities.
  • The algorithms are shown to have considerable dependence amongst themselves as shown through APL identities.
  • Interesting similarities within the function selector table are identified and are worthy of further investigation.
• Thanks to the work of D. E. Knuth in his TAoCP Vol 4A, each of the twelve ways has a high quality algorithm behind it.
• Finally, APL programmers need no longer search for the fastest APL program to generate any of several Combinatorial Counts or Generations as the fastest way is now available primitively.

Acknowledgments

No paper is written in isolation, and this paper is no exception. I’d like to thank David Liebtag, Roy Sykes, Norman Thomson, Jim Brown, Roger Hui, and Michael Turniansky for their helpful advice and suggestions.