Computing the cycles of the k-way shuffle permutation in linear time

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

rho(k,n) : i --> ki mod (kn+1), i in {1, 2, ..... , 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 presented in Computing the Cycles in the Perfect Shuffle Permutation

The Cycles of the Multi-way Perfect Shuffle Permutation ,
J. Ellis, H. Fan and J. Shallit,

Discrete Mathematics & Theoretical Computer Science, Volume 5 no. 1, 2002, pp. 169-180.