Shortest prefix strings containing all subset permutations

DOI10.1016/0012-365X(87)90193-2MaRDI QIDQ1109773zbMATH OpenFDO

Authors Alejandro A. Schäffer

Publication date 1987

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(87)90193-2

zbMATH Keywords

permutationssequencesshortest string

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Review text

\textit{D. E. Knuth} poses the following problem: What is the length of the shortest string consisting of elements of \(\{\) 1,2,...,n\(\}\) that contains all permutations of the set as subsequences? [\textit{V. Chvátal, D. A. Klarner} and \textit{D. E. Knuth}, Selected combinatorial research problems, Technical report CS-72-292, Stanford University (1972)]. In the paper under review, the author studies an incremental variation on this problem first proposed by \textit{P. J. Koutas} and \textit{T. C. Hu} [Discrete Math. 11, 125-132 (1975; Zbl 0296.05004)]. The problem can be viewed as follows: For \(k=1\) one needs n distinct digits to find each of the n possible permutations. In going from k to \(k+1\), one starts with a string containing all k-element permutations as subsequences, and one adds as few digits as possible to the end of the string so that the new string contains all \((k+1)\)-element permutations. The author gives a new construction that given shorter strings then the best previous construction. The lower bound for the number of digits added in successive suffixes is also presented.

Recommendations

• scientific article; zbMATH DE number 4168689
• Shorter strings containing all \(k\)-element permutations
• Containing all permutations
• A construction of short sequences containing all permutations of a set as subsequences
• Non-uniqueness of minimal superpermutations

Cites work

• A lower bound on the length of a sequence containing all permutations as subsequences
• A new bound on the length of the shortest string containing all r- permutations
• On Permutation-Embedding Sequences
• Short permutation strings
• Short strings containing all k-element permutations
• Shortest string containing all permutations

Cited in

(6)

• Shorter strings containing all \(k\)-element permutations
• A construction of short sequences containing all permutations of a set as subsequences
• 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?)
• Containing all permutations

This page was built for publication: Shortest prefix strings containing all subset permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109773)