Combinatorial - Revision history

WikiSysop at 14:27, 15 September 2023

2023-09-15T14:27:10Z

← Older revision		Revision as of 10:27, 15 September 2023
Line 18:		Line 18:
	<td><apll>a</apll> is a non-negative numeric scalar or one- or two- element vector which serves as the '''Selector''' for the Twelve Combinatorial Functions.		<td><apll>a</apll> 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 <apll>a</apll> 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 [[#The_Twelvefold_Way\|separate meaning]]):<br />		The first element ('''Function Selector''') in <apll>a</apll> 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 [[#The_Twelvefold_Way\|separate meaning]]):<br />
	<table border="0" cellpadding="1" cellspacing="0" rules="none" summary="" style="margin-left: 20px;">		<table border="0" cellpadding="1" cellspacing="0" rules="none" summary="" style="margin-left: 20px;">
	<tr>		<tr>

WikiSysop at 21:42, 7 January 2023

2023-01-07T21:42:00Z

WikiSysop at 20:43, 21 October 2017

2017-10-21T20:43:38Z

← Older revision		Revision as of 16:43, 21 October 2017
Line 73:		Line 73:
	</tr>		</tr>
	<tr>		<tr>
	<td>The second element ('''Count/Generate Flag''') in <apll>a</apll> is an optional ~~Boolean~~ value where <apll>0</apll> (the default) means '''~~count~~''' the number of elements in the Combinatorial Function as applied to <apll>R</apll>, and <apll>1</apll> ~~means~~ '''generate''' the array of elements.</td>		<td>The second element ('''Count/Generate Flag''') in <apll>a</apll> is an optional Integer value where <apll>0</apll> (the default) means '''Count''' the number of elements in the Combinatorial Function as applied to <apll>R</apll> and values greater than <apll>0</apll> mean '''generate''' the array of elements. If the '''Generate Flag''' is <apll>1</apll>, generate the array in an unspecified order. Certain Function Selectors (see the individual Combinatorial Functions) accept values greater than <apll>1</apll>. In particular, the value <apll>2</apll> generates the array in [https://en.wikipedia.org/wiki/Lexicographical_order '''Lexicographic'''] order, and <apll>3</apll> generates the array in [https://en.wikipedia.org/wiki/Gray_code '''Gray Code'''] order.</td>
	</tr>		</tr>
	<tr>		<tr>
Line 659:		Line 659:
	2 3 1		2 3 1
	2 1 3		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		110 1‼2 3 ⍝ Generate the 2 Permutations of 3 items
	1 2		1 2
Line 689:		Line 696:
	2 3 5		2 3 5
	1 4 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		2 4 5
	3 4 5		3 4 5

Sudleyplace: /* Conclusions */

2017-07-24T23:30:39Z

Conclusions

← Older revision		Revision as of 19:30, 24 July 2017
Line 763:		Line 763:
	* 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.		* 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:		* 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 relationships among the algorithms is made clearer when comparing their APL versions, especially through identities<ref name="Smith" />.
	** The algorithms are shown to have considerable dependence amongst themselves as shown through APL identities.		** The algorithms are shown to have considerable dependence amongst themselves as shown through APL identities<ref name="Smith" />.
	** Interesting similarities within the function selector table are identified and are worthy of further investigation.		** Interesting similarities within the function selector table are identified and are worthy of further investigation<ref name="Smith" />.
	* 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.		* 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<ref name="Smith" />.
	* 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.		* 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.

Sudleyplace: /* The Twelvefold Way */

2017-07-24T23:23:35Z

The Twelvefold Way

← Older revision		Revision as of 19:23, 24 July 2017
Line 121:		Line 121:

	<ul>		<ul>
	<li>A function selector of [[CombinatorialCase010\|<apll>010</apll>]] means unlabeled balls (0), labeled boxes (1), and at most one ball ~~in each~~ box (0).		<li>A function selector of [[CombinatorialCase010\|<apll>010</apll>]] means unlabeled balls (0), labeled boxes (1), and at most one ball per box (0).

	If we have 2 unlabeled balls (<span style="font-size: 2em;">●●</span>) and 4 labeled boxes (<apll>1234</apll>) with at most one ball per box, there are <apll>6</apll> (<apll>↔ 2!4</apll>) ways to meet these criteria:		If we have 2 unlabeled balls (<span style="font-size: 2em;">●●</span>) and 4 labeled boxes (<apll>1234</apll>) with at most one ball per box, there are <apll>6</apll> (<apll>↔ 2!4</apll>) ways to meet these criteria:
Line 213:		Line 213:
	\|}		\|}

	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>		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>).

			<div style="background: yellow; padding-left: 1.3em; text-indent: -1.3em;">► Notice how we obtain the generated answer as a <apll>6×M</apll> matrix. In this example, it is obtained by reading the Box Labels in ascending order (<apll>6 M⍴1 2, 1 3, 1 4, 2 3, 2 4, 3 4</apll>). 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 <apll>M</apll> Balls and At Most One Ball Per Box we are assured of obtaining exactly <apll>M</apll> box labels per row.</div></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 359:		Line 361:

	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<N</apll>, this is the # <apll>M</apll>-permutations, also called the [[Variant#Rising_and_Falling_Factorials\|Falling Factorial]] (<apll>!⍠(-M) N</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<N</apll>, this is the # <apll>M</apll>-permutations, also called the [[Variant#Rising_and_Falling_Factorials\|Falling Factorial]] (<apll>!⍠(-M) N</apll>).

			<div style="background: yellow; padding-left: 1.3em; text-indent: -1.3em;">► Notice how we obtain the generated answer as a <apll>6×M</apll> 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 <apll>M=3</apll>), the generated answer is <apll>6 M⍴1 2 3, 2 1 3, 3 1 2, 1 3 2, 2 3 1, 3 2 1</apll>, and for the second one (with <apll>M=2</apll>), it is <apll>6 M⍴1 2, 2 1, 3 1, 1 3, 2 3, 3 2</apll>. It is common to need a different method of generating the answer for many of these Combinatorial Algorithms.
			</div>
	</li>		</li>
	</ul>		</ul>

	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 algorithms use labeled boxes (1) with at most one ball per box (0).

	==Labeled vs. Unlabeled==		==Labeled vs. Unlabeled==

WikiSysop: /* Memoization */

2017-06-19T23:44:29Z

Memoization

← Older revision		Revision as of 19:44, 19 June 2017
Line 721:		Line 721:
	This [https://en.wikipedia.org/wiki/Memoization technique] is a form of caching used to speed up certain algorithms, particularly recursive ones.		This [https://en.wikipedia.org/wiki/Memoization technique] is a form of caching used to speed up certain algorithms, particularly recursive ones.

	Two of the Combinatorial Functions ([[CombinatorialCase001\|<apll>001</apll>]] and [[CombinatorialCase002\|<apll>002</apll>]]) are dependent on the following recurrence relation for [https://en.wikipedia.org/wiki/Partition_(number_theory) Partition Numbers] defined on <apll>~~n≥0~~</apll> and <apll>~~k≥0~~</apll>:		Two of the Combinatorial Functions ([[CombinatorialCase001\|<apll>001</apll>]] and [[CombinatorialCase002\|<apll>002</apll>]]) are dependent on the following recurrence relation for [https://en.wikipedia.org/wiki/Partition_(number_theory) Partition Numbers] defined on integer <apll>n</apll> and <apll>k</apll>:

	<apll><pre>P(0,0) = 1		<apll><pre>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)</pre></apll>		P(n,k) = P(n-k,k) + P(n-1,k-1)</pre></apll>

	Within a session of the interpreter, these values are cached internally so that subsequent requests for already calculated Partition Numbers are sped up significantly.		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 ([[CombinatorialCase101\|<apll>101</apll>]], [[CombinatorialCase102\|<apll>102</apll>]], and [[CombinatorialCase112\|<apll>112</apll>]]) are dependent on the [https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling numbers of the 2nd kind]. They satisfy the following recurrence relation defined on <apll>n≥0</apll> and <apll>k≥0</apll>:		Three other Combinatorial Functions ([[CombinatorialCase101\|<apll>101</apll>]], [[CombinatorialCase102\|<apll>102</apll>]], and [[CombinatorialCase112\|<apll>112</apll>]]) are dependent on the [https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling numbers of the 2nd kind]. They satisfy the following recurrence relation defined on integer <apll>n≥0</apll> and <apll>k≥0</apll>:

	<apll><pre>		<apll><pre>
	S(0,0) = 1		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)</pre></apll>		S(n,k) = k × S(n-1,k) + S(n-1,k-1)</pre></apll>

WikiSysop: /* The Twelvefold Way */

2017-06-05T17:57:53Z

The Twelvefold Way

← Older revision		Revision as of 13:57, 5 June 2017
Line 357:		Line 357:
	\|}		\|}
	\|}		\|}

			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<N</apll>, this is the # <apll>M</apll>-permutations, also called the [[Variant#Rising_and_Falling_Factorials\|Falling Factorial]] (<apll>!⍠(-M) N</apll>).
	</li>		</li>
	</ul>		</ul>

	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<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).

WikiSysop: /* Examples */

2017-05-17T14:45:08Z

Examples

← Older revision		Revision as of 10:45, 17 May 2017
Line 688:		Line 688:
	</pre></apll>		</pre></apll>

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

	<apll><pre>		<apll><pre>

WikiSysop: /* The Functions */

2017-05-17T14:41:56Z

The Functions

Show changes

WikiSysop at 19:18, 13 May 2017

2017-05-13T19:18:30Z

Show changes

← Older revision		Revision as of 17:42, 7 January 2023
Line 219:		Line 219:
	<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).

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

	{\| border="0" cellpadding="5" cellspacing="0"		{\| border="0" cellpadding="5" cellspacing="0"
Line 290:		Line 290:
	\|}		\|}

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

	{\| border="0" cellpadding="5" cellspacing="0"		{\| border="0" cellpadding="5" cellspacing="0"
Line 360:		Line 360:
	\|}		\|}

	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<N</apll>, this is the # <apll>M</apll>-permutations, also called the [[Variant#Rising_and_Falling_Factorials\|Falling Factorial]] (<apll>!⍠(-M) N</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<N</apll>, this is the # <apll>M</apll>-permutations, also called the [[Variant#Rising_and_Falling_Factorials\|Falling Factorial]] (<apll>!⍠((-M) N)</apll>).

	<div style="background: yellow; padding-left: 1.3em; text-indent: -1.3em;">► Notice how we obtain the generated answer as a <apll>6×M</apll> 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 <apll>M=3</apll>), the generated answer is <apll>6 M⍴1 2 3, 2 1 3, 3 1 2, 1 3 2, 2 3 1, 3 2 1</apll>, and for the second one (with <apll>M=2</apll>), it is <apll>6 M⍴1 2, 2 1, 3 1, 1 3, 2 3, 3 2</apll>. It is common to need a different method of generating the answer for many of these Combinatorial Algorithms.		<div style="background: yellow; padding-left: 1.3em; text-indent: -1.3em;">► Notice how we obtain the generated answer as a <apll>6×M</apll> 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 <apll>M=3</apll>), the generated answer is <apll>6 M⍴1 2 3, 2 1 3, 3 1 2, 1 3 2, 2 3 1, 3 2 1</apll>, and for the second one (with <apll>M=2</apll>), it is <apll>6 M⍴1 2, 2 1, 3 1, 1 3, 2 3, 3 2</apll>. It is common to need a different method of generating the answer for many of these Combinatorial Algorithms.
Line 465:		Line 465:
	and the count for <apll>M</apll> permutations of <apll>N</apll> items is		and the count for <apll>M</apll> permutations of <apll>N</apll> items is

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

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