Enumerating even permutations

Discuss interdimensional programming, Java applets and so forth.

Enumerating even permutations

Postby quickfur » Fri Nov 19, 2010 11:12 pm

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: 2173
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Enumerating even permutations

Postby wendy » Mon Nov 22, 2010 7:51 am

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.
User avatar
wendy
Pentonian
 
Posts: 1527
Joined: Tue Jan 18, 2005 12:42 pm
Location: Brisbane, Australia

Re: Enumerating even permutations

Postby quickfur » Mon Nov 22, 2010 6:42 pm

Cool! That's a very neat way of determining the parity of a permutation. Are there any equivalents in higher dimensions?
quickfur
Pentonian
 
Posts: 2173
Joined: Thu Sep 02, 2004 11:20 pm
Location: The Great White North

Re: Enumerating even permutations

Postby wendy » Tue Nov 23, 2010 7:30 am

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.
User avatar
wendy
Pentonian
 
Posts: 1527
Joined: Tue Jan 18, 2005 12:42 pm
Location: Brisbane, Australia

Re: Enumerating even permutations

Postby Mrrl » Mon May 30, 2011 4:14 am

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: 162
Joined: Sun May 29, 2011 7:37 am


Return to Programming

Who is online

Users browsing this forum: No registered users and 1 guest