Shortest prefix strings containing all subset permutations (Q1109773): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Short permutation strings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new bound on the length of the shortest string containing all r- permutations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Permutation-Embedding Sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A lower bound on the length of a sequence containing all permutations as subsequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Shortest string containing all permutations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Short strings containing all k-element permutations / rank | |||
Normal rank |
Latest revision as of 19:15, 18 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Shortest prefix strings containing all subset permutations |
scientific article |
Statements
Shortest prefix strings containing all subset permutations (English)
0 references
1987
0 references
\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.
0 references
sequences
0 references
shortest string
0 references
permutations
0 references