Shortest prefix strings containing all subset permutations (Q1109773): Difference between revisions

\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.