CLR cover

Problem 125: Superwords of Shortened Permutations

On the alphabet of natural numbers, a word is an $n$-permutation if every number from $\{\sa{1},\sa{2},\dots,n\}$ appears exactly once in it (see Problems 14 and 15). A word is a shortened $n$-permutation ($n$-shortperm, in short) if it is an $n$-permutation with its last element removed. The bijection between standard permutations and shortened ones for a given $n$ implies there are $n!$ shortened $n$-permutations.

The subject of the problem is the construction of a shortest superword for all $n$-shortperms. They are of length $n!+n-2$, which meets the obvious lower bound.

Show how to construct a superword of length $n!+n-2$ for shortened $n$-permutations in linear time w.r.t. the output length.
Consider an Eulerian cycle in an appropriate graph.

References

  • B. W. Jackson. Universal cycles of k-subsets and k-permutations. Discrete Mathematics, 117(1-3):141-150, 1993.
    • F. Ruskey and A. Williams. An explicit universal cycle for the $(n-1)$-permutations of an $n$-set. ACM Trans. Algorithms, 6(3):45:1-45:12, 2010.