Short permutation strings

A permutation string is a string of symbols over the numerals 1, 2, …, n such that all permutations of the string 1 2 … n are subsequences. The search for short permutation strings arose out of studies into the complexity of shortest path algorithms by Karp and others. The results in the sequel are presented independent of such studies because they are felt to be of intrinsic combinatorial interest 1]. An algorithm for constructing permutation strings of length n²−2n+4 is given.