Parallel and sequential in-place permuting and perfect shuffling using involutions

Original · EN

We show that any permutation of 1,2,...,N can be written as the product of two involutions. As a consequence, any permutation of the elements of an array can be performed in-place in parallel in time O(1). In the case where the permutation is the k-way perfect shuffle we develop two methods for efficiently computing such a pair of involutions. The first method works whenever N is a power of k; in this case the time is O(N) and space O(² N). The second method applies to the general case where N is a multiple of k; here the time is O(N N) and the space is O(² N). If k=2 the space usage of the first method can be reduced to O(N) on a machine that has a SADD (population count) instruction.