Permutation’s Parity

If a permutation P of integers 0 thru n−1 is given as an array P of n distinct integers, each less than n, and for each k<n, P[k] is what k is permuted into, then tp(n, P) is a linear time algorithm to determine the parity of the permutation:

int tp(int n, int P[n]){int p = 0; char v[n];
  for(int j=0; j<n; ++j) v[j] = 0;
  for(int j=0; j<n; ++j)
    if(v[j]) ++p;
    else {int x = j; do {x = P[x]; v[x] = 1;} while (x!=j);}
  return p&1;}

Ocaml routine dp in this program implements this algorithm. If the array is not a permutation this code may loop or exceed array bounds. The following code ensures the preconditions:

#include <stdio.h>
void tc(int n, int P[n]){char v[n];
  for(int j=0; j<n; ++j) v[j] = 0;
  for(int j=0; j<n; ++j)
      {if(P[j]<0 || P[j]>= n) printf("range %d\n", j); v[P[j]] = 1;}
  for(int j=0; j<n; ++j) if(!v[j]) printf("missing %d\n", j);}

The following tests these routines.

#include <stdlib.h>
int main(){int const n=2003; int q[n]; for(int j=0; j<n; ++j) q[j]=j;
   for(int w=1; w<100000; ++w){int i=random()%n; int j; do j=random()%n; while (i==j);
   {int e=q[i]; q[i] = q[j]; q[j] = e;}
   if(!(w&31)) {tc(n, q); if(tp(n, q) != (w&1)) printf("Wrong parity %d\n", w);}}
   return 0;}

All together now