## Enumerating even permutations

Discuss interdimensional programming, Java applets and so forth.

### Enumerating even permutations

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. quickfur
Pentonian

Posts: 2735
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

### Re: Enumerating even permutations

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.
The dream you dream alone is only a dream
the dream we dream together is reality.

\(\LaTeX\ \) at https://greasyfork.org/en/users/188714-wendy-krieger wendy
Pentonian

Posts: 1964
Joined: Tue Jan 18, 2005 12:42 pm
Location: Brisbane, Australia

### Re: Enumerating even permutations

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

Posts: 2735
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

### Re: Enumerating even permutations

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.
The dream you dream alone is only a dream
the dream we dream together is reality.

\(\LaTeX\ \) at https://greasyfork.org/en/users/188714-wendy-krieger wendy
Pentonian

Posts: 1964
Joined: Tue Jan 18, 2005 12:42 pm
Location: Brisbane, Australia

### Re: Enumerating even permutations

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;                }            }        }`
Mrrl
Trionian

Posts: 165
Joined: Sun May 29, 2011 7:37 am 