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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2002, 5, pp.169-180
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00958980
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:55:57
Dernière modification le : mercredi 29 novembre 2017 - 10:26:18
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:07:47

Fichier

dm050111.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958980, version 1

Collections

Citation

John Ellis, Hongbing Fan, Jeffrey Shallit. The Cycles of the Multiway Perfect Shuffle Permutation. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2002, 5, pp.169-180. 〈hal-00958980〉

Partager

Métriques

Consultations de la notice

85

Téléchargements de fichiers

163