Even’s algorithm enumerates permutations in change-ringing order with a mutable array. Each number carries a direction; a number is mobile when a smaller neighbor lies immediately in that direction. section 6.2.5
Generate the next permutation by repeating these steps:
- Start with 0 through n−1, assigning every element the left direction. section 6.2.5
- Find the largest mobile element by checking its directed neighbor. section 6.2.5
- Swap that element with its neighbor, then reverse the directions of every larger element. section 6.2.5
- Stop when no element is mobile. section 6.2.5
Four-element enumeration
For four elements, the algorithm begins 0123, 0132, 0312, 3012, 3021, and 0321, eventually producing all 24 permutations.
