When exploring higher dimensional spaces, we sometimes run into polytopes whose coordinates involve even permutations of coordinates, such as those pretty rhodomorphs (pentagonal polytopes). When dealing with these polytopes, we want an efficient way of generating all their vertices, which involves generating even permutations of particular sets of coordinates.

While there are plenty of resources online that tell you how to generate all permutations, how to determine whether a given permutation is even, and even how to generate a random even permutation, there seem to be a lack of information on how to enumerate all even permutations in a systematic and efficient manner. Of course, you could just enumerate all permutations and then go through each one and run a parity check algorithm on it, discarding it if it's odd, but parity check algorithms in general are O(n log n), and this quickly adds up when you need to check each generated permutation.

So why not get it right the first time? It's possible to generate all even permutations in lexicographic order with O(1) space. Here's how.