A change-ringing algorithm lists every permutation while changing only one pair of adjacent elements between successive permutations. Lexicographic order cannot guarantee this: for three elements, 021 is followed by 102, which takes more than one adjacent swap. The order 012, 021, 201, 210, 120, 102 does satisfy the restriction; its last permutation is also one adjacent swap from its first. section 6.2.4
One recursive construction inserts the new largest element into permutations of the remaining elements:
- Start with the zero-length permutation when n is zero. section 6.2.4
- For each permutation of n − 1 elements, insert n − 1 at every position. Traverse those positions from right to left for one source permutation, then left to right for the next. section 6.2.4
- Read each group of insertions before moving to the next source permutation. Consecutive insertions move the new element one place; alternating direction preserves the adjacent-swap restriction between groups. section 6.2.4
Table 6.2 Generating the three-bell permutations from the two-bell permutations
| Row |
0 right |
1 left |
|---|---|---|
| 0 |
012 |
210 |
| 1 |
021 |
120 |
| 2 |
201 |
102 |
The three-element table makes the alternating insertion directions visible. Read down each column, then move to the next column. section 6.2.4
The recursive C# implementation yields permutations rather than storing the whole sequence. An insertion helper places the new value at the selected index. The same table structure also permits direct lookup: for permutation number p, the row is p % n, the source-permutation number is p / n, and the source number’s parity determines the insertion direction. For example, zero-based number 5 in the four-element sequence is 0321. section 6.2.4
Even’s algorithm generates the same change-ringing order with a mutable array. Give every value a direction, initially left. A value is mobile when the adjacent value in its direction is smaller. Repeatedly swap the largest mobile value with that neighbor, then reverse the directions of all larger values. Stop when none is mobile. Unlike the recursive insertion approach, this uses a linear search to choose each swap; it takes O(n) work per permutation. section 6.2.5
