In-place permuting and perfect shuffling using involutions

DOI10.1016/J.IPL.2013.02.017zbMATH Open1366.68214arXiv1204.1958OpenAlexW2027252214MaRDI QIDQ396603FDOQ396603

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

Publication date: 13 August 2014

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

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.

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

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

zbMATH Keywords

permutationanalysis of algorithmsinvolutionparallel algorithmscombinatorial problemsperfect shuffle

Mathematics Subject Classification ID

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

Cites Work

• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing the cycles in the perfect shuffle permutation
• Permuting in Place
• Title not available (Why is that?)
• How to write a permutation as a product of involutions (and why you might care)
• Algorithms – ESA 2004

Cited In (6)

• Permuting streaming data using RAMs
• McLaren's masterpiece
• The weighted \(k\)-path vertex cover problem on series-parallel graphs
• Title not available (Why is that?)
• Raising permutations to powers in place
• Title not available (Why is that?)

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)