Containing all permutations
From MaRDI portal
Abstract: Numerous versions of the question "what is the shortest object containing all permutations of a given length?" have been asked over the past fifty years: by Karp (via Knuth) in 1972; by Chung, Diaconis, and Graham in 1992; by Ashlock and Tillotson in 1993; and by Arratia in 1999. The large variety of questions of this form, which have previously been considered in isolation, stands in stark contrast to the dearth of answers. We survey and synthesize these questions and their partial answers, introduce infinitely more related questions, and then establish an improved upper bound for one of these questions.
Recommendations
Cites work
- A construction of short sequences containing all permutations of a set as subsequences
- A lower bound on the length of a sequence containing all permutations as subsequences
- A method and two algorithms on the theory of partitions
- An explicit universal cycle for the (n-1)-permutations of an n-set
- Asymptotic bounds for permutations containing many different patterns
- Bounds on superpatterns containing all layered permutations
- Combinatorics of permutations
- Dense packing of patterns in a permutation
- Faster generation of shorthand universal cycles for permutations
- scientific article; zbMATH DE number 3505007 (Why is no real title available?)
- scientific article; zbMATH DE number 617582 (Why is no real title available?)
- scientific article; zbMATH DE number 6850346 (Why is no real title available?)
- Magical mathematics. The mathematical ideas that animate great magic tricks. With a foreword by Martin Gardner
- Non-uniqueness of minimal superpermutations
- On a conjecture of H. Gupta
- On Permutation-Embedding Sequences
- On permutation-generating strings and rosaries
- On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
- Restricted permutations
- Short permutation strings
- Shorter strings containing all \(k\)-element permutations
- Shortest string containing all permutations
- Shortest string containing all permutations
- Shorthand universal cycles for permutations
- Superpatterns and universal point sets
- The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
- Universal cycles for combinatorial structures
- Universal cycles for permutation classes
- Universal cycles for permutations
- Universal cycles of k-subsets and k-permutations
- Universal layered permutations
- Unsolved problems in number theory
Cited in
(14)- Shortest prefix strings containing all subset permutations
- Shorter strings containing all \(k\)-element permutations
- A construction of short sequences containing all permutations of a set as subsequences
- Lower bounds for superpatterns and universal sequences
- Supertrees
- Skip letters for short supersequence of all permutations
- Universality of random permutations
- scientific article; zbMATH DE number 4168689 (Why is no real title available?)
- Non-uniqueness of minimal superpermutations
- scientific article; zbMATH DE number 1741021 (Why is no real title available?)
- Quasipolynomiality of the Smallest Missing Induced Subgraph
- Critical properties of bipartite permutation graphs
- An asymptotically tight lower bound for superpatterns with small alphabets
- Constant time and space updates for the sigma-tau problem
This page was built for publication: Containing all permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144492)
