Loopless generation of up-down permutations

被引：6

作者：

Korsh, JF ^{[1
]}

机构：

[1] Temple Univ, Dept Comp & Informat Sci, Philadelphia, PA 19122 USA

来源：

DISCRETE MATHEMATICS | 2001年 / 240卷 / 1-3期

关键词：

D O I：

10.1016/S0012-365X(00)00387-3

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

An up-down permutation P = (p(1), p(2),..., p(n)) is a permutation of the integers 1 to n which satisfies constraints specified by a sequence C=(c(1),c(2),...,c(n-1)) of U's and D's of length n-1. If c(l) is U then p(i) < p(i+1) otherwise p(i-1) > p(i). A loopless algorithm is developed for generating all the up-down permutations satisfying any sequence C. Ranking and unranking algorithms are discussed. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：97 / 122

页数：26

共 18 条

[1]

Andre D., 1881, Journal de mathematiques pures et appliquees 3e serie, V7, P167

[2] ON ZIGZAG PERMUTATIONS AND COMPARISONS OF ADJACENT ELEMENTS [J].

ATKINSON, MD .

INFORMATION PROCESSING LETTERS, 1985, 21 (04) :187-189

[3] GENERATING ALTERNATING PERMUTATIONS LEXICOGRAPHICALLY [J].

BAUSLAUGH, B ;

RUSKEY, F .

BIT, 1990, 30 (01) :17-26

[4] EFFICIENT GENERATION OF BINARY REFLECTED GRAY CODE AND ITS APPLICATIONS [J].

BITNER, JR ;

EHRLICH, G ;

REINGOLD, EM .

COMMUNICATIONS OF THE ACM, 1976, 19 (09) :517-521

[5] A LOOP-FREE ALGORITHM FOR GENERATING THE LINEAR EXTENSIONS OF A POSET [J].

CANFIELD, ER ;

WILLIAMSON, SG .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1995, 12 (01) :57-75

[6]

Dershowitz N., 1975, BIT (Nordisk Tidskrift for Informationsbehandling), V15, P158, DOI 10.1007/BF01932689

[7] LOOPLESS ALGORITHMS FOR GENERATING PERMUTATIONS, COMBINATIONS, AND OTHER COMBINATORIAL CONFIGURATIONS [J].

EHRLICH, G .

JOURNAL OF THE ACM, 1973, 20 (03) :500-513

[8] ALGORITHM - 4 COMBINATORIAL ALGORITHMS [G6] [J].

EHRLICH, G .

COMMUNICATIONS OF THE ACM, 1973, 16 (11) :690-691

[9] ON THE GENERATION OF ALL TOPOLOGICAL SORTINGS [J].

KALVIN, AD ;

VAROL, YL .

JOURNAL OF ALGORITHMS, 1983, 4 (02) :150-162

[10]

KALVIN D, 1984, COMPUT J, V27, P176

← 1 2 →