Shortest string containing all permutations |
| |
Authors: | PJ Koutas TC Hu |
| |
Institution: | Mathematics Research Center, The University of Wisconsin, Madison, Wisc. 53706, USA |
| |
Abstract: | In this paper, we consider the problem of constructing a shortest string of {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!) permutations of {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.We shall first give a rule for constructing a string of {1,2,…,n} of infinite length and the show that the leftmost n2?2n+4 digits of the string contain all the n! permutations (for n≥3). We conjecture that the number of digits f(n) = n2?2n+4 (for n≥3) is the minimum.Then we study a new function F(n,k) which is the minimum number of digits required for a string of n digits to contain all permutations of i digits, i≤k. We conjecture that F(n,k) = k(n?1) for 4≤k ≤n?1. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|