The Cycles of the Multiway Perfect Shuffle Permutation
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2002-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/308/pdf |
| _version_ | 1797270239838208000 |
|---|---|
| author | John Ellis Hongbing Fan Jeffrey Shallit |
| author_facet | John Ellis Hongbing Fan Jeffrey Shallit |
| author_sort | John Ellis |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:01:07Z |
| format | Article |
| id | doaj.art-d68e5a2376954b4cad88101a621a3969 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:01:07Z |
| publishDate | 2002-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-d68e5a2376954b4cad88101a621a39692024-03-07T15:04:55ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502002-01-01Vol. 510.46298/dmtcs.308308The Cycles of the Multiway Perfect Shuffle PermutationJohn Ellis0Hongbing Fan1Jeffrey Shallit2https://orcid.org/0000-0003-1197-3820Department of Computer Science [Victoria]Department of Computer Science [Victoria]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.https://dmtcs.episciences.org/308/pdfperfect shuffle permutationcycle decomposition[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | John Ellis Hongbing Fan Jeffrey Shallit The Cycles of the Multiway Perfect Shuffle Permutation Discrete Mathematics & Theoretical Computer Science perfect shuffle permutation cycle decomposition [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | The Cycles of the Multiway Perfect Shuffle Permutation |
| title_full | The Cycles of the Multiway Perfect Shuffle Permutation |
| title_fullStr | The Cycles of the Multiway Perfect Shuffle Permutation |
| title_full_unstemmed | The Cycles of the Multiway Perfect Shuffle Permutation |
| title_short | The Cycles of the Multiway Perfect Shuffle Permutation |
| title_sort | cycles of the multiway perfect shuffle permutation |
| topic | perfect shuffle permutation cycle decomposition [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/308/pdf |
| work_keys_str_mv | AT johnellis thecyclesofthemultiwayperfectshufflepermutation AT hongbingfan thecyclesofthemultiwayperfectshufflepermutation AT jeffreyshallit thecyclesofthemultiwayperfectshufflepermutation AT johnellis cyclesofthemultiwayperfectshufflepermutation AT hongbingfan cyclesofthemultiwayperfectshufflepermutation AT jeffreyshallit cyclesofthemultiwayperfectshufflepermutation |