Discrete Mathematics & Theoretical Computer Science
| 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.