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 algorithm to determine the parity of the permutation:

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

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];
   {int j=n; while(j--) v[j] = 0;}
   {int j=n; while(j--) {
      if(P[j]<0 || P[j]>= n) printf("range %d\n", j);
      v[P[j]] = 1;}}
   {int j=n; while(j--) if(!v[j]) printf("missing %d\n", j);}}

The folowing tests these routines.

#include <stdlib.h>
int main(){int const n=2000; int q[n]; {int j=n; while(j--) q[j]=j;}
   {int w=100000; while(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