Efficiently determine the parity of a permutation

Question

I have an int[] array of length N containing the values 0, 1, 2, .... (N-1), i.e. it represents a permutation of integer indexes.

What's the most efficient way to determine if the permutation has odd or even parity?

(I'm particularly keen to avoid allocating objects for temporary working space if possible....)

Answer 1

I think you can do this in O(n) time and O(n) space by simply computing the cycle decomposition.

You can compute the cycle decomposition in O(n) by simply starting with the first element and following the path until you return to the start. This gives you the first cycle. Mark each node as visited as you follow the path.

Then repeat for the next unvisited node until all nodes are marked as visited.

The parity of a cycle of length k is (k-1)%2, so you can simply add up the parities of all the cycles you have discovered to find the parity of the overall permutation.

Saving space

One way of marking the nodes as visited would be to add N to each value in the array when it is visited. You would then be able to do a final tidying O(n) pass to turn all the numbers back to the original values.