Parallel and sequential in-place permuting and shuffling using involutions
Qingxuan Yang,
Department of Computer Science,
University of Peking, China.
John Ellis,
Department of Computer Science,
University of Victoria, Canada.
Khalegh Mamakani,
Department of Computer Science,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
We show that any permutation of $\{1,2,\ldots,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(\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 count) instruction.
-
Download: postscript file.
Download: pdf file.
-
Appears in
Information Processing Letters, 113 (2013) 386-391.
-
Submitted to a conference and rejected, June 2012.
-
Submitted to Information Processing Letters, April 9, 2012.
-
The SADD instruction referred to in the abstract is from Don Knuth's
MMIX machine.
Of course, many other machines have an equivalent instruction.
-
The program used in the timing of the algorithm:
YER.c.
-
Typos: There are some typos in the routine modInv$(M,r)$ in the paper.
-
Line 2: $i \in \{1,2,\ldots,kM-2\}$
-
Line 3: $x$ should be $i$.
-
Line 4: $j := g\ (r(i/g)^{-1} \bmod{( kM-1)/g })$
We thank Sergio Mergen for noting that there were some typos in this routine.
Here is a link to some Maple code that generates the comparisons used in the figure:
YERmaple.pdf.
-
Please send me a note if
you download one of these files.
It's always nice to know who's reading your papers.
-
Selected citations:
-
Yang, J., Shao, Z., Zhou, K., Xu, J., Xu, P.,
Design of micro-optics array to realize two dimensional perfect shuffle transform,
Optical Switching and Networking,
12 (2014) 68-79.
Back to list of publications.
