Shortest String Containing all Permutations.
Abstract
In this paper, the authors consider the problem of constructing a shortest string of the set (1,2, ..., n) containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6(= 3 factorial) permutations of the set (1,2,3) and no string with less than 7 digits contains all the six permutations. Note that a given permutation, such as 1 2 3, does not have to be consecutive but must be from left to right in the string.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1975
- Accession Number
- ADA010085
Entities
People
- P. J. Koutas
- T. C. Hu
Organizations
- University of Wisconsin–Madison