6533b85bfe1ef96bd12bb4af
RESEARCH PRODUCT
A loopless algorithm for generating the permutations of a multiset
Vincent Vajnovszkisubject
Discrete mathematicsMultisetMathematics::CombinatoricsGeneral Computer ScienceMultiset permutationsLoopless algorithmStructure (category theory)Context (language use)Gray codesTheoretical Computer ScienceCombinatoricsGray codePermutationLoopless generating algorithmsShuffle combinatorial objectsBinomial coefficientWord (computer architecture)Computer Science::Formal Languages and Automata TheoryMathematicsMathematicsofComputing_DISCRETEMATHEMATICSComputer Science(all)description
AbstractMany combinatorial structures can be constructed from simpler components. For example, a permutation can be constructed from cycles, or a Motzkin word from a Dyck word and a combination. In this paper we present a constructor for combinatorial structures, called shuffle on trajectories (defined previously in a non-combinatorial context), and we show how this constructor enables us to obtain a new loopless generating algorithm for multiset permutations from similar results for simpler objects.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2003-10-01 | Theoretical Computer Science |