Discrete Mathematics & Theoretical Computer Science

DMTCS

Volume 5 n° 1 (2002), pp. 169-180


author:John Ellis and Hongbing Fan and Jeffrey Shallit
title:The Cycles of the Multiway Perfect Shuffle Permutation
keywords:perfect shuffle permutation, cycle decomposition
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 (&mod;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.

If your browser does not display the abstract correctly (because of the different mathematical symbols) you can look it up in the PostScript or PDF files.

reference: John Ellis and Hongbing Fan and Jeffrey Shallit (2002), The Cycles of the Multiway Perfect Shuffle Permutation , Discrete Mathematics and Theoretical Computer Science 5, pp. 169-180
bibtex:For a corresponding BibTeX entry, please consider our BibTeX-file.
ps.gz-source:dm050111.ps.gz (46 K)
ps-source:dm050111.ps (146K)
pdf-source:dm050111.pdf (106 K)

The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.

Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.


Automatically produced on Sat Jun 19 18:02:57 CEST 2004 by gustedt