In-place permuting and perfect shuffling using involutions

DOI10.1016/J.IPL.2013.02.017MaRDI QIDQ396603zbMATH OpenOpenAlexFDO

Authors Qingxuan Yang, John Ellis, Khalegh Mamakani, Frank Ruskey

Publication date 13 August 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.1958

zbMATH Keywords

analysis of algorithmscombinatorial problemsinvolutionparallel algorithmsperfect shufflepermutation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05) Parallel algorithms in computer science (68W10) Analysis of algorithms (68W40)

Abstract: We show that any permutation of $1,2,\mathrm{...},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(lo{g}^{2}N)$. The second method applies to the general case where $N$ is a multiple of $k$; here the time is $O(NlogN)$ and the space is $O(lo{g}^{2}N)$. If $k=2$ the space usage of the first method can be reduced to $O(logN)$ on a machine that has a SADD (population count) instruction.

Recommendations

• scientific article; zbMATH DE number 1808170
• Raising permutations to powers in place
• A generalization of the perfect shuffle
• A heuristic to accelerate in-situ permutation algorithms
• scientific article; zbMATH DE number 1108880

Cites work

• Algorithms – ESA 2004
• Computing the cycles in the perfect shuffle permutation
• How to write a permutation as a product of involutions (and why you might care)
• scientific article; zbMATH DE number 1808170 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 3557795 (Why is no real title available?)
• scientific article; zbMATH DE number 1437310 (Why is no real title available?)
• scientific article; zbMATH DE number 3204712 (Why is no real title available?)
• Permuting in Place
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.

Cited in

(7)

• McLaren's masterpiece
• scientific article; zbMATH DE number 1808170 (Why is no real title available?)
• Permuting streaming data using RAMs
• Raising permutations to powers in place
• scientific article; zbMATH DE number 1437310 (Why is no real title available?)
• The weighted k-path vertex cover problem on series-parallel graphs
• Involution factorizations of Ewens random permutations

This page was built for publication: In-place permuting and perfect shuffling using involutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396603)