Multiset permutation generation by transpositions

Abstract

This paper proposes a new algorithm for generating all permutations of multisets. The method uses transpositions only and adjacent transpositions are favoured. The algorithm requires a strong homogeneous transposition condition: non-adjacent transpositions are allowed only if all elements between the two permuted elements are equal to the smallest of those two elements. The storage required by the algorithm is small.

arXiv comment20 pages, 9 figures