Universal cycles for permutations

被引：26

作者：

Johnson, J. Robert ^{[1
]}

机构：

[1] Univ London, Sch Math Sci, London E1 4NS, England

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 17期

关键词：

Universal cycles; Combinatorial generation; Permutations;

D O I：

10.1016/j.disc.2007.11.004

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A universal cycle for permutations is a word of length it! such that each of the it! 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. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：5264 / 5270

页数：7