Skip to Main content Skip to Navigation
Journal articles

The Cycles of the Multiway Perfect Shuffle Permutation

Abstract : The (k,n)-perfect shuffle, a generalisation of the 2-way perfect shuffle, cuts a deck of kn cards into k equal size decks and interleaves them perfectly with the first card of the last deck at the top, the first card of the second-to-last deck as the second card, and so on. It is formally defined to be the permutation ρ _k,n: i → ki \bmod (kn+1), for 1 ≤ i ≤ kn. We uncover the cycle structure of the (k,n)-perfect shuffle permutation by a group-theoretic analysis and show how to compute representative elements from its cycles by an algorithm using O(kn) time and O((\log kn)^2) space. Consequently it is possible to realise the (k,n)-perfect shuffle via an in-place, linear-time algorithm. Algorithms that accomplish this for the 2-way shuffle have already been demonstrated.
Document type :
Journal articles
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958980
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Thursday, March 13, 2014 - 4:55:57 PM
Last modification on : Friday, June 1, 2018 - 3:24:01 PM
Long-term archiving on: : Friday, June 13, 2014 - 12:07:47 PM

File

dm050111.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

John Ellis, Hongbing Fan, Jeffrey Shallit. The Cycles of the Multiway Perfect Shuffle Permutation. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2002, Vol. 5, pp.169-180. ⟨10.46298/dmtcs.308⟩. ⟨hal-00958980⟩

Share

Metrics

Record views

259

Files downloads

862