Enumerating even permutations

[quickfur]

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.

[wendy]

For n up to five, one can rapidly determine whether a permutation is even or odd thus. You add extra as needed to make 5.

1. write one order around the verticies of a pentagon.

2. draw inside this pentagon, a line connecting the vertices in the order that they appear in order 2. Connect the first and last.

If the figure has an even number of crossings (0 or 2), then it is an even permutation. If the figure has an odd number (1 or 5), then it's an odd permutation.

The 15-14 puzzle resolves to even and odd permutations.

[quickfur]

Cool! That's a very neat way of determining the parity of a permutation. Are there any equivalents in higher dimensions?

[wendy]

The necessary conditions for this to happen is when x mod 4 = 1. There are two parts: the first is that the line must be reversable, ie AB..CD is even to DC..BA. This happens when there is an even number of pairs (ie 0,1 mod 4). The second condition is that a cyclic permutation must be even, eg AB..CD = B..CDA This happens for odd numbers, ie 1,3 mod 4. You can then close the lot into a polygon.

In the case of n=9, the thing breaks down, since the same general figure (eg a fish with a tail), can be even or odd, accordingly to how the numbers fall. That is, there are figures with a single crossing, that are even, and with a single crossing that are odd. For a particular shape, if any is even(odd), all of the rest are the same.

[Mrrl]

Enumerating of even permutations in 20 lines. Memory = N words, total time=O(N!):

Code: Select all

        void CalcPerm(int N){
            int[] P=new int[N];
            int u=1;
            for(int i=0;i<N;i++){ u*=i+1; P[i]=i+1; }
            for(int f=1;f<u;f++){
                if(f%2==1){ for(int i=0;i<N;i++) Console.Write("{0} ",P[i]); Console.WriteLine(); }
                int a=0,b=f;
                for(int k=N;k>0;k--){
                    int b1=b/k,c1=b%k;
                    if(c1!=0){
                        if(b1%2!=0) c1=k-c1;
                        c1+=a;
                        int p=P[c1]; P[c1]=P[c1-1]; P[c1-1]=p;
                        break;
                    }
                    a+=(b1+1)%2; b=b1;
                }
            }
        }