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