Combinatorial: Difference between revisions

From NARS2000
Jump to navigationJump to search
No edit summary
No edit summary
Line 4: Line 4:
     <table border="0" cellpadding="5" cellspacing="0" summary="">
     <table border="0" cellpadding="5" cellspacing="0" summary="">
     <tr>
     <tr>
       <td valign="top"><apll>Z←a‼V</apll></td>
       <td valign="top"><apll>Z←a‼R</apll></td>
       <td></td>
       <td></td>
       <td></td>
       <td></td>
Line 13: Line 13:
</tr>
</tr>
<tr>
<tr>
   <td><apll>V</apll> is a non-negative numeric scalar or one- or two-element vector.  If <apll>V</apll> has only one element, it is treated as if the value were duplicated as in <apll>2⍴V</apll>.  For convenience in the description below, the two elements are referred to as <apll>L</apll> and <apll>R</apll> as in <apll>(L R)←2⍴V</apll>.</td>
   <td><apll>R</apll> is a non-negative numeric scalar or one- or two-element vector.  If <apll>R</apll> has only one element, it is treated as if the value were duplicated as in <apll>2⍴R</apll>.  For convenience in the description below, the two elements are referred to as <apll>M</apll> and <apll>N</apll> as in <apll>(M N)←2⍴R</apll>.</td>
</tr>
</tr>
<tr>
<tr>
Line 22: Line 22:
       <tr>
       <tr>
         <td>[[CombinatorialCase000/100|<apll>000</apll>]]</td>
         <td>[[CombinatorialCase000/100|<apll>000</apll>]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase000/100|<apll>L</apll> Pigeons in <apll>R</apll> holes]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase000/100|<apll>M</apll> Pigeons in <apll>N</apll> holes]]</td>
       </tr>
       </tr>
       <tr>
       <tr>
         <td>[[CombinatorialCase001|<apll>001</apll>]]</td>
         <td>[[CombinatorialCase001|<apll>001</apll>]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase001|Partitions of the number <apll>L</apll> into no more than <apll>R</apll> parts]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase001|Partitions of the number <apll>M</apll> into no more than <apll>N</apll> parts]]</td>
       </tr>
       </tr>
       <tr>
       <tr>
         <td>[[CombinatorialCase002|<apll>002</apll>]]</td>
         <td>[[CombinatorialCase002|<apll>002</apll>]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase002|Partitions of the number <apll>L</apll> into <apll>R</apll> parts]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase002|Partitions of the number <apll>M</apll> into <apll>N</apll> parts]]</td>
       </tr>
       </tr>
       <tr>
       <tr>
         <td>[[CombinatorialCase010|<apll>010</apll>]]</td>
         <td>[[CombinatorialCase010|<apll>010</apll>]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase010|<apll>L</apll> Combinations of <apll>R</apll> items]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase010|<apll>M</apll> Combinations of <apll>N</apll> items]]</td>
       </tr>
       </tr>
       <tr>
       <tr>
         <td>[[CombinatorialCase011|<apll>011</apll>]]</td>
         <td>[[CombinatorialCase011|<apll>011</apll>]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase011|<apll>L</apll> Multisets of <apll>R</apll> items]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase011|<apll>M</apll> Multisets of <apll>N</apll> items]]</td>
       </tr>
       </tr>
       <tr>
       <tr>
         <td valign="top">[[CombinatorialCase012|<apll>012</apll>]]</td>
         <td valign="top">[[CombinatorialCase012|<apll>012</apll>]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase012|Compositions of the number <apll>L</apll> into <apll>R</apll> parts]]<br />
         <td>&nbsp;&nbsp;[[CombinatorialCase012|Compositions of the number <apll>M</apll> into <apll>N</apll> parts]]<br />
&nbsp;&nbsp;a.k.a. Partitions of the number <apll>L</apll> into <apll>R</apll> ordered parts</td>
&nbsp;&nbsp;a.k.a. Partitions of the number <apll>M</apll> into <apll>N</apll> ordered parts</td>
       </tr>
       </tr>
       <tr>
       <tr>
         <td>[[CombinatorialCase000/100|<apll>100</apll>]]</td>
         <td>[[CombinatorialCase000/100|<apll>100</apll>]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase000/100|<apll>L</apll> Pigeons in <apll>R</apll> holes]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase000/100|<apll>M</apll> Pigeons in <apll>N</apll> holes]]</td>
       </tr>
       </tr>
       <tr>
       <tr>
         <td>[[CombinatorialCase101|<apll>101</apll>]]</td>
         <td>[[CombinatorialCase101|<apll>101</apll>]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase101|Partitions of the set <apll>{⍳L}</apll> into no more than <apll>R</apll> parts]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase101|Partitions of the set <apll>{⍳M}</apll> into no more than <apll>N</apll> parts]]</td>
       </tr>
       </tr>
       <tr>
       <tr>
         <td>[[CombinatorialCase102|<apll>102</apll>]]</td>
         <td>[[CombinatorialCase102|<apll>102</apll>]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase102|Partitions of the set <apll>{⍳L}</apll> into <apll>R</apll> parts]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase102|Partitions of the set <apll>{⍳M}</apll> into <apll>N</apll> parts]]</td>
       </tr>
       </tr>
     <tr>
     <tr>
         <td>[[CombinatorialCase110|<apll>110</apll>]]</td>
         <td>[[CombinatorialCase110|<apll>110</apll>]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase110|<apll>L</apll> Permutations of <apll>R</apll> items]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase110|<apll>M</apll> Permutations of <apll>N</apll> items]]</td>
       </tr>
       </tr>
     <tr>
     <tr>
         <td>[[CombinatorialCase111|<apll>111</apll>]]</td>
         <td>[[CombinatorialCase111|<apll>111</apll>]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase111|<apll>L</apll> Tuples of <apll>R</apll> items]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase111|<apll>M</apll> Tuples of <apll>N</apll> items]]</td>
       </tr>
       </tr>
       <tr>
       <tr>
         <td>[[CombinatorialCase112|<apll>112</apll>]]</td>
         <td>[[CombinatorialCase112|<apll>112</apll>]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase112|Partitions of the set <apll>{⍳L}</apll> into <apll>R</apll> ordered parts]]</td>
         <td>&nbsp;&nbsp;[[CombinatorialCase112|Partitions of the set <apll>{⍳M}</apll> into <apll>N</apll> ordered parts]]</td>
       </tr>
       </tr>
     </table>
     </table>
Line 83: Line 83:
==Introduction==
==Introduction==


Counting and generating items is fundamental in mathematics, but has been sorely lacking in APL (notwithstanding the counting functions <apll>!R</apll> and <apll>L!R</apll>); instead we have had to rely upon a patchwork of various library routines.
Counting and generating items is fundamental in mathematics, but has been sorely lacking in APL (notwithstanding the counting functions <apll>!N</apll> and <apll>M!N</apll>); 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.
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.
Line 213: Line 213:
|}
|}


from which it is easy to see that these criteria correspond to L combinations of R items (<apll>↔ L!R</apll>).</li>
from which it is easy to see that these criteria correspond to <apll>M</apll> combinations of <apll>N</apll> items (<apll>↔ M!N</apll>).</li>


<li>A function selector of [[CombinatorialCase110|<apll>110</apll>]] means labeled balls (1), labeled boxes (1), and at most one ball in each box (0).
<li>A function selector of [[CombinatorialCase110|<apll>110</apll>]] means labeled balls (1), labeled boxes (1), and at most one ball in each box (0).
Line 360: Line 360:
</ul>
</ul>


from which it is easy to see that these criteria correspond to <apll>L</apll> permutations of <apll>R</apll> items.  When <apll>L=R</apll>, this is the # permutations of <apll>⍳R</apll>, (<apll>↔ !R</apll>), and when <apll>L&lt;R</apll>, this is the # <apll>L</apll>-permutations, also called the [[Variant#Rising_and_Falling_Factorials|Falling Factorial]] (<apll>!⍠(-L) R</apll>).
from which it is easy to see that these criteria correspond to <apll>M</apll> permutations of <apll>N</apll> items.  When <apll>M=N</apll>, this is the # permutations of <apll>⍳N</apll>, (<apll>↔ !N</apll>), and when <apll>M&lt;N</apll>, this is the # <apll>M</apll>-permutations, also called the [[Variant#Rising_and_Falling_Factorials|Falling Factorial]] (<apll>!⍠(-M) N</apll>).


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 in labeled boxes (1) with at most one ball per box (0).
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 in labeled boxes (1) with at most one ball per box (0).
Line 454: Line 454:
===Balls===
===Balls===


In a similar manner, the counts and generations for combinations ([[CombinatorialCase010|<apll>010</apll>]]) and permutations ([[CombinatorialCase110|<apll>110</apll>]]) differ by a factor of <apll>!L</apll>, this time because of the balls:  one is unlabeled and the other labeled.  That is, the count for <apll>L</apll> combinations of <apll>R</apll> items is
In a similar manner, the counts and generations for combinations ([[CombinatorialCase010|<apll>010</apll>]]) and permutations ([[CombinatorialCase110|<apll>110</apll>]]) differ by a factor of <apll>!M</apll>, this time because of the balls:  one is unlabeled and the other labeled.  That is, the count for <apll>M</apll> combinations of <apll>N</apll> items is


<apll>L!R ↔ (!R)÷(!R-L)×!L</apll>
<apll>M!N ↔ (!N)÷(!N-M)×!M</apll>


and the count for <apll>L</apll> permutations of <apll>R</apll> items is
and the count for <apll>M</apll> permutations of <apll>N</apll> items is


<apll>!⍠(-L) R ↔ (!R)÷!R-L</apll>
<apll>!⍠(-M) N ↔ (!N)÷!N-M</apll>


Of course, when <apll>L=R</apll>, the permutation count is the familiar <apll>!R</apll>.
Of course, when <apll>M=N</apll>, the permutation count is the familiar <apll>!N</apll>.


==The Functions==
==The Functions==
Line 476: Line 476:
|align="justify"|'''At least one&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; xx2'''
|align="justify"|'''At least one&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; xx2'''
|-
|-
|align="justify"|L unlabeled balls '''00x'''<br />R unlabeled boxes
|align="justify"|M unlabeled balls '''00x'''<br />N unlabeled boxes
|align="justify" bgcolor="lightblue"|[[CombinatorialCase000/100|L&nbsp;pigeons&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 000<br />into R holes]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase000/100|M&nbsp;pigeons&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 000<br />into N holes]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase001|partitions&nbsp;of&nbsp;L&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 001<br />into ≤R parts]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase001|partitions&nbsp;of&nbsp;M&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 001<br />into ≤N parts]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase002|partitions&nbsp;of&nbsp;L&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 002<br />into R parts]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase002|partitions&nbsp;of&nbsp;M&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 002<br />into N parts]]
|-
|-
|align="justify"|L unlabeled balls '''01x'''<br />R labeled boxes
|align="justify"|M unlabeled balls '''01x'''<br />N labeled boxes
|align="justify" bgcolor="lightblue"|[[CombinatorialCase010|L-combinations&nbsp;&nbsp;&nbsp; 010<br />of R items]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase010|M-combinations&nbsp;&nbsp;&nbsp; 010<br />of N items]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase011|L-multisets&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 011<br />of R items]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase011|M-multisets&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 011<br />of N items]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase012|compositions&nbsp;of&nbsp;L&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 012<br />into R parts]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase012|compositions&nbsp;of&nbsp;M&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 012<br />into N parts]]
|-
|-
|align="justify"|L&nbsp;labeled&nbsp;balls&nbsp;&nbsp;&nbsp; '''10x'''<br />R&nbsp;unlabeled&nbsp;boxes
|align="justify"|M&nbsp;labeled&nbsp;balls&nbsp;&nbsp;&nbsp; '''10x'''<br />N&nbsp;unlabeled&nbsp;boxes
|align="justify" bgcolor="lightblue"|[[CombinatorialCase000/100|L&nbsp;pigeons&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 100<br />into R holes]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase000/100|M&nbsp;pigeons&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 100<br />into N holes]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase101|partitions&nbsp;of&nbsp;<apll>{⍳L}</apll>&nbsp;&nbsp; 101<br />into ≤R parts]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase101|partitions&nbsp;of&nbsp;<apll>{⍳M}</apll>&nbsp;&nbsp; 101<br />into ≤N parts]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase102|partitions&nbsp;of&nbsp;<apll>{⍳L}</apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 102<br />into R parts]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase102|partitions&nbsp;of&nbsp;<apll>{⍳M}</apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 102<br />into N parts]]
|-
|-
|align="justify"|L&nbsp;labeled balls&nbsp;&nbsp;&nbsp; '''11x'''<br />R&nbsp;labeled&nbsp;boxes
|align="justify"|M&nbsp;labeled balls&nbsp;&nbsp;&nbsp; '''11x'''<br />N&nbsp;labeled&nbsp;boxes
|align="justify" bgcolor="lightblue"|[[CombinatorialCase110|L-permutations&nbsp;&nbsp;&nbsp; 110<br />of R items]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase110|M-permutations&nbsp;&nbsp;&nbsp; 110<br />of N items]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase111|L-tuples&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 111<br />of R items]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase111|M-tuples&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 111<br />of N items]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase112|partitions&nbsp;of&nbsp;<apll>{⍳L}</apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 112<br />into R ordered parts]]
|align="justify" bgcolor="lightblue"|[[CombinatorialCase112|partitions&nbsp;of&nbsp;<apll>{⍳M}</apll>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 112<br />into N ordered parts]]
|}
|}


Line 503: Line 503:
<div style="background: yellow; padding-left: 1.3em; text-indent: -1.3em;">► Almost without exception, the counts for these functions grow quite rapidly as the arguments increase (hence the term [https://en.wikipedia.org/wiki/Combinatorial_explosion '''Combinatorial Explosion''']).  It's a good idea to check the '''Count''' value before trying to '''Generate''' the corresponding array.</div>
<div style="background: yellow; padding-left: 1.3em; text-indent: -1.3em;">► Almost without exception, the counts for these functions grow quite rapidly as the arguments increase (hence the term [https://en.wikipedia.org/wiki/Combinatorial_explosion '''Combinatorial Explosion''']).  It's a good idea to check the '''Count''' value before trying to '''Generate''' the corresponding array.</div>


The expression <apll>110‼L R</apll> produces <apll>L</apll> Permutations of <apll>R</apll> items.  When <apll>L=R</apll>, it represents the usual Permutation function.
The expression <apll>110‼M N</apll> produces <apll>M</apll> Permutations of <apll>N</apll> items.  When <apll>M=N</apll>, it represents the usual Permutation function.


<apll><pre>
<apll><pre>
Line 532: Line 532:
</pre></apll>
</pre></apll>


The expression <apll>10‼L R</apll> produces <apll>L</apll> Combinations of <apll>R</apll> items.
The expression <apll>10‼M N</apll> produces <apll>M</apll> Combinations of <apll>N</apll> items.


<apll><pre>
<apll><pre>
Line 549: Line 549:
</pre></apll>
</pre></apll>


The expression <apll>1‼L R</apll> produces Partitions of <apll>L</apll> into at most <apll>R</apll> parts.
The expression <apll>1‼M N</apll> produces Partitions of <apll>M</apll> into at most <apll>N</apll> parts.


<apll><pre>
<apll><pre>
Line 574: Line 574:
==Special Cases==
==Special Cases==


The problem of counting [[CombinatorialCase001|Partitions of <apll>L</apll> Into At Most <apll>L</apll> Parts]] has been well studied.  As alluded to above, the brilliantly intuitive Indian mathematician [https://en.wikipedia.org/wiki/Srinivasa_Ramanujan Srinivasa Ramanujan] along with [https://en.wikipedia.org/wiki/G._H._Hardy G. H. Hardy] and [https://en.wikipedia.org/wiki/Hans_Rademacher Hans Rademacher] have provided a convergent series which can produce an exact value for this number.  Fortunately, this algorithm (referred to as [https://en.wikipedia.org/wiki/Partition_(number_theory)#Approximation_formulas Hardy-Ramanujan-Rademacher] or HRR) has been coded by Frederik Johansson<ref name="Johansson">Johansson, F. (2012). Efficient implementation of the Hardy–Ramanujan–Rademacher formula. LMS Journal of Computation and Mathematics, 15, 341-359. doi:10.1112/S1461157012001088</ref> using the open source library [http://mpfr.org MPFR] (Multiple Precision Floating Point) and is available in the open source library [http://flintlib.org FLINT] (Fast Library for Number Theory).  This code is used for the function <apll>1‼L</apll> when <apll>L</apll> is in the range <apll>395 &lt; L &lt; 2<sup>31</sup></apll> on the 32-bit version of NARS2000, and in the range <apll>395 &lt; L &lt; 2<sup>63</sup></apll> on the 64-bit version.  The code is so efficient that it can calculate <apll>1‼1E12</apll> 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 <apll>1,113,996</apll> digits!
The problem of counting [[CombinatorialCase001|Partitions of <apll>M</apll> Into At Most <apll>M</apll> Parts]] has been well studied.  As alluded to above, the brilliantly intuitive Indian mathematician [https://en.wikipedia.org/wiki/Srinivasa_Ramanujan Srinivasa Ramanujan] along with [https://en.wikipedia.org/wiki/G._H._Hardy G. H. Hardy] and [https://en.wikipedia.org/wiki/Hans_Rademacher Hans Rademacher] have provided a convergent series which can produce an exact value for this number.  Fortunately, this algorithm (referred to as [https://en.wikipedia.org/wiki/Partition_(number_theory)#Approximation_formulas Hardy-Ramanujan-Rademacher] or HRR) has been coded by Frederik Johansson<ref name="Johansson">Johansson, F. (2012). Efficient implementation of the Hardy–Ramanujan–Rademacher formula. LMS Journal of Computation and Mathematics, 15, 341-359. doi:10.1112/S1461157012001088</ref> using the open source library [http://mpfr.org MPFR] (Multiple Precision Floating Point) and is available in the open source library [http://flintlib.org FLINT] (Fast Library for Number Theory).  This code is used for the function <apll>1‼M</apll> when <apll>M</apll> is in the range <apll>395 &lt; M &lt; 2<sup>31</sup></apll> on the 32-bit version of NARS2000, and in the range <apll>395 &lt; M &lt; 2<sup>63</sup></apll> on the 64-bit version.  The code is so efficient that it can calculate <apll>1‼1E12</apll> 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 <apll>1,113,996</apll> digits!


Correspondingly, because partitions of <apll>L</apll> into <apll>R</apll> non-negative parts ([[CombinatorialCase001|<apll>001</apll>]]) is the same as partitions of <apll>L+R</apll> into <apll>R</apll> positive parts ([[CombinatorialCase002|<apll>002</apll>]]), (i.e., <apll>1‼L R ←→ 2‼(L+R) R</apll><ref>https://en.wikipedia.org/wiki/Twelvefold_way#case_fnx</ref>), the case of <apll>2‼(2×L) L</apll> also takes advantage of the fast algorithm.
Correspondingly, because partitions of <apll>M</apll> into <apll>N</apll> non-negative parts ([[CombinatorialCase001|<apll>001</apll>]]) is the same as partitions of <apll>N+M</apll> into <apll>N</apll> positive parts ([[CombinatorialCase002|<apll>002</apll>]]), (i.e., <apll>1‼M N ←→ 2‼(M+N) N</apll><ref>https://en.wikipedia.org/wiki/Twelvefold_way#case_fnx</ref>), the case of <apll>2‼(2×M) M</apll> also takes advantage of the fast algorithm.


==Memoization==
==Memoization==

Revision as of 19:18, 13 May 2017

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 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 Boolean value where 0 (the default) means count the number of elements in the Combinatorial Function as applied to R, and 1 means generate the array of elements.
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[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 APL-like) principle for such a primitive is Gian-Carlo 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 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 in each 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).
  • 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).

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 in 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 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

The expression 1‼M N produces Partitions of M into at most N parts.

      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[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 < 231 on the 32-bit version of NARS2000, and in the range 395 < M < 263 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[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 n≥0 and k≥0:

P(0,0) = 1
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 n≥0 and k≥0:

S(0,0) = 1
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[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 in-depth 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.
    • 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.

References

  1. Rota, Gian-Carlo [1]
  2. 2.0 2.1 Wikipedia "Twelvefold Way"
  3. 3.0 3.1 Stanley, Richard P. (1997, 1999). Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press. ISBN 0-521-55309-1, ISBN 0-521-56069-1
  4. Knuth, Donald E., “The Art of Computer Programming”, Volume 4A, Combinatorial Algorithms, p. 390, Addison Wesley, ISBN 0-201-89685-0
  5. Johansson, F. (2012). Efficient implementation of the Hardy–Ramanujan–Rademacher formula. LMS Journal of Computation and Mathematics, 15, 341-359. doi:10.1112/S1461157012001088
  6. https://en.wikipedia.org/wiki/Twelvefold_way#case_fnx
  7. Joel Spencer
  8. Smith, Bob "A Combinatorial Operator", 2016-2017