Combinatorial


R is a nonnegative numeric scalar or one or twoelement 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 nonnegative 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 nonnegative integer for each of the Twelve functions (where the number is written here with three digits to emphasize that each digit has a separate meaning): 

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. 
Contents
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 GianCarlo Rota^{[1]}’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 APLlike) principle for such a primitive is GianCarlo Rota's Twelvefold Way^{[2]} as described in Richard Stanley's "Enumerative Combinatorics"^{[3]} and Knuth’s TAoCP, Vol. 4A^{[4]} 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 oldtimers). 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 # Mpermutations, 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)÷(!NM)×!M
and the count for M permutations of N items is
!⍠(M) N ↔ (!N)÷!NM
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:
Click on one of the above colored cells to see more detail on that function.
Examples
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 hundredthousandths 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 HardyRamanujanRademacher or HRR) has been coded by Frederik Johansson^{[5]} 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^{31} on the 32bit version of NARS2000, and in the range 395 < M < 2^{63} on the 64bit version. The code is so efficient that it can calculate 1‼1E12 in under a minute (on a 64bit 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 nonnegative parts (001) is the same as partitions of N+M into N positive parts (002), (i.e., 1‼M N ←→ 2‼(M+N) N^{[6]}), 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(nk,k) + P(n1,k1)
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(n1,k) + S(n1,k1)
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 GianCarlo 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^{[3]}, and Wikipedia^{[2]}. The name was suggested by Joel Spencer^{[7]}.
Implementation
This Combinatorial Operator is implemented in the Released version of NARS2000 and may be downloaded from here. For an indepth look at the Twelvefold Way and its implementation in APL, see Smith's^{[8]} 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^{[8]}.
 The algorithms are shown to have considerable dependence amongst themselves as shown through APL identities^{[8]}.
 Interesting similarities within the function selector table are identified and are worthy of further investigation^{[8]}.
 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^{[8]}.
 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.
References
 ↑ Rota, GianCarlo [1]
 ↑ ^{2.0} ^{2.1} Wikipedia "Twelvefold Way"
 ↑ ^{3.0} ^{3.1} Stanley, Richard P. (1997, 1999). Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press. ISBN 0521553091, ISBN 0521560691
 ↑ Knuth, Donald E., “The Art of Computer Programming”, Volume 4A, Combinatorial Algorithms, p. 390, Addison Wesley, ISBN 0201896850
 ↑ Johansson, F. (2012). Efficient implementation of the Hardy–Ramanujan–Rademacher formula. LMS Journal of Computation and Mathematics, 15, 341359. doi:10.1112/S1461157012001088
 ↑ https://en.wikipedia.org/wiki/Twelvefold_way#case_fnx
 ↑ Joel Spencer
 ↑ ^{8.0} ^{8.1} ^{8.2} ^{8.3} ^{8.4} Smith, Bob "A Combinatorial Operator", 20162017