# Discrete Mathematics & Theoretical Computer Science

## 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 ρ, for _{k,n}: i → ki (&mod;kn+1)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) space. Consequently it is possible to
realise the ^{2})(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