Geodesic
The Cycles of the Multiway Perfect Shuffle Permutation
Discrete mathematics & theoretical computer science, Tome 5 (2002).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2002_5_a14,
     author = {Ellis, John and Fan, Hongbing and Shallit, Jeffrey},
     title = {The {Cycles} of the {Multiway} {Perfect} {Shuffle} {Permutation}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {5},
     year = {2002},
     doi = {10.46298/dmtcs.308},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.308/}
}
TY  - JOUR
AU  - Ellis, John
AU  - Fan, Hongbing
AU  - Shallit, Jeffrey
TI  - The Cycles of the Multiway Perfect Shuffle Permutation
JO  - Discrete mathematics & theoretical computer science
PY  - 2002
VL  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.308/
DO  - 10.46298/dmtcs.308
LA  - en
ID  - DMTCS_2002_5_a14
ER  - 
%0 Journal Article
%A Ellis, John
%A Fan, Hongbing
%A Shallit, Jeffrey
%T The Cycles of the Multiway Perfect Shuffle Permutation
%J Discrete mathematics & theoretical computer science
%D 2002
%V 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.308/
%R 10.46298/dmtcs.308
%G en
%F DMTCS_2002_5_a14
Ellis, John; Fan, Hongbing; Shallit, Jeffrey. The Cycles of the Multiway Perfect Shuffle Permutation. Discrete mathematics & theoretical computer science, Tome 5 (2002). doi : 10.46298/dmtcs.308. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.308/

Cité par Sources :