John Ellis ; Hongbing Fan ; Jeffrey Shallit - The Cycles of the Multiway Perfect Shuffle Permutation

dmtcs:308 - Discrete Mathematics & Theoretical Computer Science, January 1, 2002, Vol. 5 - https://doi.org/10.46298/dmtcs.308
The Cycles of the Multiway Perfect Shuffle PermutationArticle

Authors: John Ellis 1; Hongbing Fan 1; Jeffrey Shallit ORCID2

  • 1 Department of Computer Science [Victoria]
  • 2 Department of Computer Science [Waterloo ]

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.


Volume: Vol. 5
Published on: January 1, 2002
Imported on: March 26, 2015
Keywords: perfect shuffle permutation,cycle decomposition,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

3 Documents citing this article

Consultation statistics

This page has been seen 530 times.
This article's PDF has been downloaded 352 times.