Universal cycles for permutations |
| |
Authors: | J Robert Johnson |
| |
Institution: | aSchool of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK |
| |
Abstract: | A universal cycle for permutations is a word of length n! such that each of the n! possible relative orders of n distinct integers occurs as a cyclic interval of the word. We show how to construct such a universal cycle in which only n+1 distinct integers are used. This is best possible and proves a conjecture of Chung, Diaconis and Graham. |
| |
Keywords: | Universal cycles Combinatorial generation Permutations |
本文献已被 ScienceDirect 等数据库收录! |
|