String Permutations - Revision history

Admin: /* Enumerating - Stars and Bars */

2019-03-09T08:56:11Z

Enumerating - Stars and Bars

← Older revision		Revision as of 08:56, 9 March 2019
Line 114:		Line 114:

	===Enumerating - Stars and Bars===		===Enumerating - Stars and Bars===

			{{Main\|Stars and Bars}}

	The stars and bars theorem/approach is another way to look at assembling/enumerating permutations.		The stars and bars theorem/approach is another way to look at assembling/enumerating permutations.

2017-08-07T01:22:25Z

2017-08-07T01:21:50Z

Cool-Lexicographic Order

← Older revision		Revision as of 01:21, 7 August 2017
Line 136:		Line 136:

	===Cool-Lexicographic Order===		===Cool-Lexicographic Order===

			{{Main\|Cool}}

	This is a nice simple algorithm that implements an iterative, non-recursive, loopless permutation generator.		This is a nice simple algorithm that implements an iterative, non-recursive, loopless permutation generator.

2017-08-06T19:42:17Z

Cool-Lexicographic Order

@@ Line 149: / Line 149: @@
 ** 1 4 2 1
 ** 4 1 2 1
 Here is the algorithm:
 <pre>
 [head, i afteri] <- init(E)
 visit(head)

2017-08-06T19:35:37Z

Generating

← Older revision		Revision as of 19:35, 6 August 2017
Line 133:		Line 133:
	* de Bruijn cycles, where we remove an item from the front and add an item to the rear		* de Bruijn cycles, where we remove an item from the front and add an item to the rear
	* binary reflected Gray code, where we change only a single item at a time		* binary reflected Gray code, where we change only a single item at a time
			* Cool-lexicographic order (see http://webhome.csc.uvic.ca/~haron/CoolMulti.pdf)

	~~Excellent~~ simple algorithm ~~here: http://webhome~~.~~csc.uvic.ca/~haron/CoolMulti.pdf~~		===Cool-Lexicographic Order===

			This is a nice simple algorithm that implements an iterative, non-recursive, loopless permutation generator.

	Algorithm:		Algorithm:

2017-08-06T19:34:35Z

Generating

@@ Line 127: / Line 127: @@
 ==Generating==
-The task of actually generating all of the permutations of words that contain a certain set of characters is an extremely important one. Knuth covers this in Volume 4 Facsimile 2 of his [[AOCP|Art of Computer Programming]] volumes.
+The task of actually generating all of the permutations of words that contain a certain set of characters is an extremely important one. (Knuth covers this exclusively in Volume 4 Facsimile 2 of his [[AOCP|Art of Computer Programming]] volumes.)
-We can generate permutations in lexicographic order, or sorted order
+We can generate permutations in several ways:
-We can generate permutations in de Bruijn cycles, where we remove an item from the front and add an item to the rear
+Excellent simple algorithm here: http://webhome.csc.uvic.ca/~haron/CoolMulti.pdf
-We can generate permutations using binary reflected Gray code, where we change only a single item at a time
+<pre>
-Excellent simple algorithm here: http://webhome.csc.uvic.ca/~haron/CoolMulti.pdf
+[head, i afteri] <- init(E)

2017-08-06T11:07:36Z

Generating

← Older revision		Revision as of 11:07, 6 August 2017
Line 127:		Line 127:
	==Generating==		==Generating==

	The task of actually generating all of the permutations of words that contain a certain set of characters is an extremely important one. Knuth covers this in Volume 4 Facsimile 2 of his [[Art of Computer Programming]] ~~series~~.		The task of actually generating all of the permutations of words that contain a certain set of characters is an extremely important one. Knuth covers this in Volume 4 Facsimile 2 of his [[AOCP\|Art of Computer Programming]] volumes.

	We can generate permutations in lexicographic order, or sorted order		We can generate permutations in lexicographic order, or sorted order

2017-08-06T11:07:21Z

Generating

← Older revision		Revision as of 11:07, 6 August 2017
Line 127:		Line 127:
	==Generating==		==Generating==

	The task of actually generating all of the permutations of words that contain a certain set of characters can ~~be reduced~~ to a ~~simpler task, as can most permutation-generating tasks~~.		The task of actually generating all of the permutations of words that contain a certain set of characters is an extremely important one. Knuth covers this in Volume 4 Facsimile 2 of his [[Art of Computer Programming]] series.

			We can generate permutations in lexicographic order, or sorted order

			We can generate permutations in de Bruijn cycles, where we remove an item from the front and add an item to the rear

			We can generate permutations using binary reflected Gray code, where we change only a single item at a time

			Excellent simple algorithm here: http://webhome.csc.uvic.ca/~haron/CoolMulti.pdf

2017-08-06T10:50:55Z

← Older revision		Revision as of 10:50, 6 August 2017
Line 4:		Line 4:

	Write a function to find all permutations of the letters in a particular string (example: HELLO).		Write a function to find all permutations of the letters in a particular string (example: HELLO).

			==Enumerating==

	===Enumerating - Easy Case===		===Enumerating - Easy Case===
Line 122:		Line 124:
	\binom{n+k-1}{k-1}		\binom{n+k-1}{k-1}
	</math>		</math>

			==Generating==

			The task of actually generating all of the permutations of words that contain a certain set of characters can be reduced to a simpler task, as can most permutation-generating tasks.

2017-08-06T10:39:22Z

Enumerating - Infinite Letters Case

← Older revision		Revision as of 10:39, 6 August 2017
Line 110:		Line 110:

	<math>n^k</math>		<math>n^k</math>

			===Enumerating - Stars and Bars===

			The stars and bars theorem/approach is another way to look at assembling/enumerating permutations.

			If we have n objects being placed into k partitions, we can think of this as placing k-1 bars among the n objects.

			In this case, the total number of slots for objects + bars is n + k - 1, and we are placing k - 1 bars, so we have the total number of outcomes given by

			<math>
			\binom{n+k-1}{k-1}
			</math>