Notes on a Problem Involving Permutations as Subsequences
Abstract
The problem (attributed to R. M. Karp by Knuth is to describe the sequences of minimum length which contain, as subsequences, all the permutations of an alphabet of n symbols. The paper catalogs come of the easy observations on the problem and proves that the minimum lengths for n=5, n=6 and n=7 are 19, 28 and 39 respectively. Also presented is a construction which yields (for n>2) many appropriate sequences of length (n sup 2)-2n+4 so giving an upper bound on length of minimum strings which matches exactly all known values.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1973
- Accession Number
- AD0759714
Entities
People
- Malcolm Newey
Organizations
- Stanford University