scientific article; zbMATH DE number 3557795
This paper surveys the numerous methods that have been proposed for permutation enumeration by computer. The various algorithms which have been developed over the years are described in detail, and implemented in a modern ALGOL-like language. All of the algorithms are derived from one simple control structure. The problems involved with implementing the best of the algorithms on real computers are treated in detail. Assembly-language programs are derived and analyzed fully. The paper is intended not only as a survey of permutation generation methods, but also as a tutorial on how to compare a number of different algorithms for the same task. Among the methods discussed are those due to Heap, Wells, Boothroyd, Johnson, Trother, Ehrlich, Dershewitz, Ives, Tompkins, Paige, Peck and Schrack, Pike, Pleszczynzki, Langdon, Ord-Smith, Fischer and Krause, Schreck and Shimrat, Shen, Phillips, Dijkstra, Lehmer, and Durstenfeld. Included are algorithms for generating random permutations and for generating permutations according to a hexicographic ordering. The paper begins with simple algorithms that generate permutations by successively exchanging elements; these algorithms all have a common control structure. Then a few older algorithms are considered in the framework of the same control structure including some based on elementary operations other than exchanges. Finally, the implementation, analysis, and ``optimization of the best of the algorithms are considered in detail.
- Estimating the number of good permutations by a modified fast simulation method
- Shape distribution of height-balanced trees
- Generating stable permutations
- Computing permutation encodings
- Generating permutations of a bag by interchanges
- Hamilton-connected derangement graphs on \(S_ n\)
- The representation of permutations by trees
- Pseudorandom permutation
- Shorthand universal cycles for permutations
- Features of formation and ordering of samples
- A permutation-generating algorithm
- A systolic generation of combinations
- Gray code for derangements
- Faster backtracking algorithms for the generation of symmetry-invariant permutations
- Graph comparison via nonlinear quantum search
- A Hamilton cycle in the \(k\)-sided pancake network
- Enumerations of universal cycles for \(k\)-permutations
- On the existence of permutations conditioned by certain rational functions
- Efficient generation of random derangements with the expected distribution of cycle lengths
- Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
- A constant-time algorithm for middle levels Gray codes
- Service chain placement in SDNs
- The traveling salesman problem with few inner points
- On generation of permutations of \(m\) out of \(n\) items
- Hamiltonicity of \(k\)-sided pancake networks with fixed-spin: efficient generation, ranking, and optimality
- Integrated strategy for generating permutation
- A multi-stack method for the fast generation of permutations with minimal length increasing subsequences
- All sorts of permutations (functional pearl)
- Greedy flipping of pancakes and burnt pancakes
- scientific article; zbMATH DE number 3887092 (Why is no real title available?)
- Generation of Permutations Following Lehmer and Howell
- The art of computer programming. Vol. 4, Fasc. 0--4. Fasc. 0: Introduction to combinatorial algorithms and Boolean functions. Fasc. 1: Bitwise tricks \& techniques, binary decision diagrams. Fasc. 2: Generating all tuples and permutations. Fasc. 3: Generating all combinations and partitions. Fasc. 4: Generating all trees. History of combinatorial generation.
- scientific article; zbMATH DE number 3920477 (Why is no real title available?)
- scientific article; zbMATH DE number 4068296 (Why is no real title available?)
- Lexicographic enumeration, ranking and unranking of permutations ofrout ofnobjects
- Efficient enumeration of cyclic permutations in situ
- Observations on the generation of permutations from random sequences
- A new algorithm for generating derangements
- scientific article; zbMATH DE number 3772962 (Why is no real title available?)
- In-place permuting and perfect shuffling using involutions
- scientific article; zbMATH DE number 14344 (Why is no real title available?)
- scientific article; zbMATH DE number 510624 (Why is no real title available?)
- scientific article; zbMATH DE number 1156604 (Why is no real title available?)
- scientific article; zbMATH DE number 1783748 (Why is no real title available?)
- scientific article; zbMATH DE number 2145159 (Why is no real title available?)
- scientific article; zbMATH DE number 871160 (Why is no real title available?)
- Generating random permutations by coin tossing: classical algorithms, new analysis, and modern implementation
- Random generation of permutations of the symmetric group or the alternating group
- A non-recursive algorithm of generating an r-permutation and its applications
- Generating Permutations with k-Differences
- scientific article; zbMATH DE number 2216957 (Why is no real title available?)
- Cayley digraphs and (1,j,n)-sequencings of the alternating groups \(A_ n\)
- Generating alternating permutations lexicographically
- Packing patterns in symmetric words
- Syntactic view of sigma-tau generation of permutations
- Loopless generation of up-down permutations
- Inferring strings from position heaps in linear time
- Solving infinite-domain CSPs using the patchwork property
- How Social Influence Affects the Wisdom of Crowds in Influence Networks
- The classification of quasi-regular polyhedra of genus 2
- Binary bubble languages and cool-lex order
- Constant time and space updates for the sigma-tau problem
- Generating signed permutations by twisting two-sided ribbons
- Random and exhaustive generation of permutations and cycles
- A sum rule for derangements
- An effective approach to enumerate universal cycles for k-permutations
- Brief announcement: Optimally encoding information in chemical reaction networks
- Skipping ropes: an efficient gray code algorithm for generating wiggly permutations
- One sequence to rule them all: \( \mathcal{O}(1)\)-time parallel generation of mixed-radix Gray codes
- More permutation generation methods
- Norm bounds for rational matrix functions
- A new algorithm for generation of permutations
- Transposition generation of alternating permutations
- Gray code for permutations with a fixed number of cycles
- Parallel algorithm for generating permutations on linear array
- On generation of permutations through decomposition of symmetric groups into cosets
- Generating restricted classes of involutions, Bell and Stirling permutations
- Disjoint Hamilton cycles in the star graph
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4133641)