15
$\begingroup$

Is there a linear time in-place riffle shuffle algorithm? This is the algorithm that some especially dextrous hands are capable of performing: evenly dividing an even-sized input array, and then interleaving the elements of the two halves.

Mathworld has a brief page on riffle shuffle. In particular, I'm interested in the out-shuffle variety which transforms the input array 1 2 3 4 5 6 into 1 4 2 5 3 6. Note that in their definition, the input length is $2n$.

It's straightforward to perform this in linear time if we've got a second array of size $n$ or more handy. First copy the last $n$ elements to the array. Then, assuming 0-based indexing, copy the first $n$ elements from indices $[0,1,2,...,n-1]$ to $[0, 2, 4,...,2n-2]$. Then copy the $n$ elements from the second array back to the input array, mapping indices $[0,1,2,...,n-1]$ to $[1,3,5,...,2n-1]$. (We can do slightly less work than that, because the first and last elements in the input do not move.)

One way of attempting to do this in-place involves the decomposition of the permutation into disjoint cycles, and then rearranging the elements according to each cycle. Again, assuming 0-based indexing, the permutation involved in the 6 element case is $$ \sigma=\begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 2 & 4 & 1 & 3 & 5\end{pmatrix}=\begin{pmatrix}0 \end{pmatrix} \begin{pmatrix}5 \end{pmatrix} \begin{pmatrix}1 & 2 & 4 &3 \end{pmatrix}. $$

As expected, the first and last elements are fixed points, and if we permute the middle 4 elements we get the expected outcome.

Unfortunately, my understanding of the mathematics of permutations (and their $\LaTeX$) is mostly based on wikipedia, and I don't know if this can be done in linear time. Maybe the permutations involved in this shuffling can be quickly decomposed? Also, we don't even need the complete decomposition. Just determining a single element of each of the disjoint cycles would suffice, since we can reconstruct the cycle from one of its elements. Maybe a completely different approach is required.

Good resources on the related mathematics are just as valuable as an algorithm. Thanks!

$\endgroup$
  • $\begingroup$ There is a $O(n\lg n)$ time solution (with $O(1)$ extra space). I don't know any linear-time solution. $\endgroup$ – Radu GRIGore Oct 14 '12 at 10:38
  • 4
    $\begingroup$ That's more appropriate for cs.stackexchange. In the non-uniform model, $O(n)$ times is always possible. In this case it should be possible even uniformly. $\endgroup$ – Yuval Filmus Oct 14 '12 at 13:06
  • 1
    $\begingroup$ @Radu Similar to this question, this problem probably does not have a solution using only $O(1)$ extra space, but $O(\log n)$ extra space. $\endgroup$ – Tyson Williams Oct 14 '12 at 13:43
  • 2
    $\begingroup$ I take my comment (and vote to close) back! (Though the question is answered in the literature.) $\endgroup$ – Yuval Filmus Oct 14 '12 at 22:29
  • 1
    $\begingroup$ I heard this question from a CS student last week, who heard it at a job interview. $\endgroup$ – Jeffε Oct 15 '12 at 4:06
12
$\begingroup$

The problem is surprisingly non-trivial. Here is a nice solution by Ellis and Markov, In-Situ, Stable Merging by way of the Perfect Shuffle (section 7). Ellis, Krahn and Fan, Computing the Cycles in the Perfect Shuffle Permutation succeed in selecting "cycle leaders", at the expense of more memory. Also related is the nice paper by Fich, Munro and Poblete, Permuting In Place, which gives a general $O(n\log n)$ time algorithm for the oracle model. If only an oracle for the permutation is available, the algorithm requires logarithmic space; if we also have an oracle for the inverse, it requires constant space.

Now for Ellis and Markov's solution. First, suppose $n = x+y$. Then computing the perfect shuffle of order $n$ reduces to computing the perfect shuffle of orders $x$ and $y$, with a rotation preceding them. Here is a proof by example ($n=5$, $x=3$, $y=2$): $$ \begin{array}{cc} 012\mathbf{345} & \mathbf{67}89 \\ 012\mathbf{567} & \mathbf{34}89 \\ 051627 & 3849 \end{array} $$

Ellis and Markov found an easy way to compute the perfect shuffle when $n=2^k$, using constant space and linear time. Using this, we obtain an algorithm for computing the perfect shuffle for arbitrary $n$. First, write $n = 2^{k_0} + \cdots + 2^{k_w}$ using the binary encoding of $n$, and let $n_i = 2^{k_i} + \cdots + 2^{k_w}$. Rotate the middle $n_0$ bits, shuffle the right-hand $2^{k_0}$ bits. Ignoring the righthand $2^{k_0}$ bits, rotate the middle $n_1$ bits, and shuffle the right-hand $2^{k_1}$ bits. And so on. Note that rotation is easy since the first few elements rotated function as cycle leaders. The total complexity of rotation is $O(n_0 + \cdots + n_w) = O(n)$, since $n_{t+1} < n_t/2$. The total complexity of the inner shuffles is $O(2^{k_0} + \cdots + 2^{k_w}) = O(n)$.

It remains to show how to compute the perfect shuffle when $n=2^k$. In fact, we will be able to identify cycle leaders, following classical work on necklaces (Fredricksen and Maiorana, Necklaces of beads in $k$ colors and $k$-ary de Bruijn sequences; Fredricksen and Kessler, An algorithm for generating necklaces of beads in two colors).

What is the connection? I claim that the shuffle permutation corresponds to right shifting of the binary representation. Here is a proof by example, for $n=8$: $$ \begin{array}{cccccccc} 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\ 000 & 100 & 001 & 101 & 010 & 110 & 011 & 111 \end{array} $$ Therefore, to find cycle leaders, we need to find one representative out of each equivalence class of the rotation of binary strings of length $k$. The papers mentioned above give the following algorithm for generating all cycle leaders. Start with $0^k$. At each step, we are at some point $a_1 \ldots a_k$. Find the maximal index $i$ of a zero bit, divide $k$ by $i$ to obtain $k = d\cdot i + r$, and let the following point be $(a_1\ldots a_{i-1}1)^d a_1\ldots a_r$. Whenever $r = 0$, the new string is a cycle leader.

For example, when $n=16$ this generates the sequence $$ \mathbf{0000}, \mathbf{0001}, 0010, \mathbf{0011}, \mathbf{0101}, 0110, \mathbf{0111}, \mathbf{1111}. $$

The cycle leaders are highlighted.

$\endgroup$
  • 3
    $\begingroup$ See also Aryabhata's answer, which uses arxiv.org/abs/0805.1598. That paper, "A Simple In-Place Algorithm for In-Shuffle" by Jain, uses the same idea, but instead of powers of $2$, uses powers of $3$. The point is that since $2$ is a primitive root modulo $3^k$, it is easily seen that $3^0,\ldots,3^k$ are cycle leaders. Even simpler than Ellis and Markov! $\endgroup$ – Yuval Filmus Oct 15 '12 at 0:45
  • $\begingroup$ Although I think Jain's paper is a little more straightforward, I'm preferring the earlier paper, as well as the earlier post with the most votes. $\endgroup$ – Johny Oct 20 '12 at 3:26
6
$\begingroup$

This was a seeding question at cs.stackexchange.com and an answer is here: https://cs.stackexchange.com/questions/332/in-place-algorithm-for-interleaving-an-array/400#400

It is an explanation of the paper: http://arxiv.org/abs/0805.1598.

The above algorithm generalizes for all those $k$-way shuffles (we have a $2$-way shuffle here) for which $k$ is a primitive root of some square of a prime (the paper picks $3^2$ for $k=2$).

Note that that answer deals with the permutation $j \to 2j \mod 2n+1$, (i.e. Inshuffle) and having that makes it easy to solve this problem (Outshuffle) too.

$\endgroup$
  • $\begingroup$ Ha! I completely forgot about that question, even if I participated in the discussion. This means I didn't really understand how it works that time. $\endgroup$ – Radu GRIGore Oct 15 '12 at 0:44
2
$\begingroup$

What happens if you write down the riffle shuffle as a function? If $m$ is the length of the total array, let $n = m-2$ be the length of the array after removing the first and last element. Then the shuffled index of index $i$ is $ f(i) = 2\cdot i $ if $i \leq n/2$ and $f(i) = 2 \cdot (i \mod n/2) - 1$ if $i > n/2$. Then you can just "pointer jump" through the array, swapping by re-applying the function.

Assuming random access, this would be linear time while requiring $O(1)$ extra words (for storing the value of the array at any given index), and so $O(\log n)$ extra space.

$\endgroup$
  • $\begingroup$ Ah, wait. This assumes that all of the values in the riffle permutation lie on the same cycle. This strategy would have to be modified a bit, depending on how many disjoint cycles there are. $\endgroup$ – Robert Robere Oct 14 '12 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.