Gray code for derangements

被引：22

作者：

Baril, JL ^{[1
]}

Vajnovszki, V ^{[1
]}

机构：

[1] Univ Bourgogne, CNRS, LE21, UMR 5158, F-21078 Dijon, France

来源：

DISCRETE APPLIED MATHEMATICS | 2004年 / 140卷 / 1-3期

关键词：

restricted permutations; gray codes; generating algorithms;

D O I：

10.1016/j.dam.2003.06.002

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We give a Gray code and constant average time generating algorithm for derangements, i.e., permutations with no fixed points. In our Gray code, each derangement is transformed into its successor either via one or two transpositions or a rotation of three elements. We generalize these results to permutations with number of fixed points bounded between two constants. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：207 / 221

页数：15

共 18 条

[1]

Akl S.G, 1980, BIT, V20, P2

[2]

AKL SG, 1989, DESIGN ANAL PARALLEL

[3]

Chase P., 1989, Congr. Numer., V69, P215

[4]

Comtet L., 1974, ADV COMBINATORICS

[5] AN ALGORITHM FOR GENERATING SUBSETS OF FIXED SIZE WITH A STRONG MINIMAL CHANGE PROPERTY [J].

EADES, P ;

MCKAY, B .

INFORMATION PROCESSING LETTERS, 1984, 19 (03) :131-133

[6] A CAT algorithm for generating permutations with a fixed number of inversions [J].

Effler, S ;

Ruskey, F .

INFORMATION PROCESSING LETTERS, 2003, 86 (02) :107-112

[7]

KNUTH DE, 2002, ART COMPUTER PROGRAM, V4

[8] GENERATING PERMUTATIONS OF A BAG BY INTERCHANGES [J].

KO, CW ;

RUSKEY, F .

INFORMATION PROCESSING LETTERS, 1992, 41 (05) :263-269

[9]

KORSH J, 2002, CONSTANT TIME GENERA

[10] Loopless generation of up-down permutations [J].

Korsh, JF .

DISCRETE MATHEMATICS, 2001, 240 (1-3) :97-122

← 1 2 →