Generating Derangements by Interchanging at Most Four Elements

摘要

For the set S = {1, 2,..., n}, a permutation π: S→ S such that π(i) = i is called a complete permutation, and the string π(l) π(2)... π(n) is called a derangement. In this paper, the authors consider the generation of a list that contains one instance of every derangement. Sequential generation, which sequentially generates a string by interchanging characters in the string, can generate the list more efficiently when fewer characters are interchanged. If P(S) denotes the list of derangements and deg(P(S)) denotes the maximum value of the numbers of characters that are interchanged, no list of derangements such that deg(P(S)) = O(1) is known as of today. In this paper, the authors notice that a derangement can be decomposed into mutually disjoint cycles to show that there exists no list of derangements such that deg(P(S)) = 2. Also, in the second half of this paper, they consider an algorithm for generating a list for which deg(T(S)) = 4 for |S|≥ 4. According to this algorithm, the average number of characters that are interchanged is roughly 2.980.