6533b839fe1ef96bd12a64bf

RESEARCH PRODUCT

Gray code for derangements

Vincent VajnovszkiJean-luc Baril

subject

021103 operations researchMathematics::CombinatoricsRestricted permutationsApplied Mathematics0211 other engineering and technologiesGenerating algorithms0102 computer and information sciences02 engineering and technologyFixed pointGray codes01 natural sciencesCombinatoricsGray codePermutationDerangement010201 computation theory & mathematicsBounded function[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]Discrete Mathematics and CombinatoricsConstant (mathematics)Rotation (mathematics)Rencontres numbersComputingMilieux_MISCELLANEOUSMathematics

description

AbstractWe 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.

yearjournalcountryeditionlanguage
2004-05-01Discrete Applied Mathematics
10.1016/j.dam.2003.06.002http://dx.doi.org/10.1016/j.dam.2003.06.002