Admin at 21:56, 17 March 2019

2019-03-17T21:56:12Z

← Older revision		Revision as of 21:56, 17 March 2019
Line 78:		Line 78:

	=Flags=		=Flags=

			{{AOCPFlag}}

	{{CombinatoricsFlag}}		{{CombinatoricsFlag}}

Admin at 20:30, 6 August 2017

2017-08-06T20:30:32Z

← Older revision		Revision as of 20:30, 6 August 2017
Line 74:		Line 74:

	[[AOCP/Multinomial Coefficients]]		[[AOCP/Multinomial Coefficients]]



			=Flags=

			{{CombinatoricsFlag}}

			{{AlgorithmsFlag}}

			[[Category:Combinatorics]]
			[[Category:Permutations]]
			[[Category:Multisets]]

Admin: Created page with "=Generating permutations in Cool-Lexicographic Order= The task of actually generating all of the permutations of words that contain a certain set of characters is an extremel..."

2017-08-06T20:29:52Z

Created page with "=Generating permutations in Cool-Lexicographic Order= The task of actually generating all of the permutations of words that contain a certain set of characters is an extremel..."

New page

=Generating permutations in Cool-Lexicographic Order=

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 several ways:
* lexicographic order, or sorted order
* 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
* Cool-lexicographic order (see 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:
* Visits every permutation of integer multiset E
* Call to init(E) creates singly linked list that stores elements of E in non-increasing order
* head, min, and inc point to first, second to last, and last nodes, respectively
* All variables are pointers
* phi is null
* If E = {1,1,2,4}, then first three visit(E) calls will produce the configurations:
** 4 2 1 1
** 1 4 2 1
** 4 1 2 1

Notes on variables:
* head points to first node of current permutation
* i points to ith node of current permutation
* afteri points to the (i+1)st node of current permutation

to apply the prefix shift of length k, the two pointers k and beforek are used:
* k points to the kth node of the current permutation
* beforek points to the (k-1)st node of the current permutation

Note that the visit(head) call denotes a new permutation that has been generated
* visit(head) happens when new permutation pointed to by head
* Represents passing control back to consumer requesting permutations
* Work in init(E) would also be done by consumer

When does the loop stop?
* Condition on loop ensures algorithm continues until it generates tail(E)
* Rather than generating tail(E) as separate case after oop ends, it initializes linked list to tail(E)
* This is the very first permutation visited

Here is the algorithm:

<pre>
[head, i afteri] <- init(E)
visit(head)
while (afteri.next != null or afteri.value < head.value) do:
if (afteri.next != null and i.value >= afteri.next.value):
beforek <- afteri
else
beforek <- i
end
k <- beforek.next
beforek.next <- k.next
k.next <- head
if (k.value < head.value):
i <- k
end
afteri <- i.next
head <- k
visit(head)
end
</pre>

=Related Pages=

[[String Permutations]]

[[AOCP/Combinatorics]]

[[AOCP/Multinomial Coefficients]]

Cool - Revision history

Admin at 21:56, 17 March 2019

Admin at 20:30, 6 August 2017

Admin: Created page with "=Generating permutations in Cool-Lexicographic Order= The task of actually generating all of the permutations of words that contain a certain set of characters is an extremel..."