In-place permuting and perfect shuffling using involutions
- Yang, Qingxuan
- Ellis, John
- Mamakani, Khalegh
- Ruskey, Frank
DOIAbstract
Every 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 using simultaneous swaps in two rounds of swaps. In the case where the permutation is the k-way perfect shuffle, we develop two methods for efficiently computing the pair of involutions that accomplishes these swaps. The first method works whenever N is a power of k; in this case the time is O(N) and space O (log(2) N). The second method applies to the general case where N is a multiple of k; here the time is O (N log N) and the space is O (log(2) N). If k = 2 the space usage of the first method can be reduced to O (log N) on a machine that has a SADD (population co...
Add to ORKG