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

<p>It is an explanation of the paper: <a href="http://arxiv.org/abs/0805.1598" rel="nofollow noreferrer">http://arxiv.org/abs/0805.1598</a>.</p>

<p>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$).</p>

<p>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. </p>

CC BY-SA 3.0
2012-10-15T00:44:15.640Z
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.
Radu GRIGore
CC BY-SA 3.0
2012-10-15T00:32:38.700Z
2012-10-15T00:38:46.507Z
2017-04-13T12:48:30.830Z
Aryabhata
<p>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 &gt; n/2$. Then you can just "pointer jump" through the array, swapping by re-applying the function.</p>

<p>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.</p>

CC BY-SA 3.0
2012-10-14T17:12:40.460Z
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.
Robert Robere
CC BY-SA 3.0
2012-10-14T16:58:21.643Z
2012-10-14T16:58:21.643Z
Robert Robere
<p>The problem is surprisingly non-trivial. Here is a nice solution by Ellis and Markov, <a href="http://webhome.cs.uvic.ca/~jellis/Publications/merge.ps">In-Situ, Stable Merging by way of the Perfect Shuffle</a> (section 7). Ellis, Krahn and Fan, <a href="http://webhome.cs.uvic.ca/~jellis/Publications/shuffle.ps">Computing the Cycles in the Perfect Shuffle Permutation</a> succeed in selecting "cycle leaders", at the expense of more memory. Also related is the nice paper by Fich, Munro and Poblete, <a href="http://www.cs.utoronto.ca/~fich/permuting.ps">Permuting In Place</a>, 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.</p>

<p>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} &amp; \mathbf{67}89 \\
012\mathbf{567} &amp; \mathbf{34}89 \\
051627 &amp; 3849
\end{array}
$$</p>

<p>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} &lt; n_t/2$. The total complexity of the inner shuffles is $O(2^{k_0} + \cdots + 2^{k_w}) = O(n)$.</p>

<p>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, <a href="http://www.sciencedirect.com/science/article/pii/0012365X7890002X">Necklaces of beads in $k$ colors and $k$-ary de Bruijn sequences</a>; Fredricksen and Kessler, <a href="http://www.sciencedirect.com/science/article/pii/0012365X86900890">An algorithm for generating necklaces of beads in two colors</a>).</p>

<p>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 &amp; 001 &amp; 010 &amp; 011 &amp; 100 &amp; 101 &amp; 110 &amp; 111 \\
000 &amp; 100 &amp; 001 &amp; 101 &amp; 010 &amp; 110 &amp; 011 &amp; 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 <em>all</em> 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 <em>new</em> string is a cycle leader.</p>

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

<p>The cycle leaders are highlighted.</p>

CC BY-SA 3.0
2012-10-15T00:45:08.960Z
See also Aryabhata's answer, which uses http://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!
Yuval Filmus
CC BY-SA 3.0
2012-10-20T03:26:03.157Z
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.
Johny
CC BY-SA 3.0
2012-10-14T22:21:32.760Z
2012-10-14T22:21:32.760Z
Yuval Filmus
<p>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.</p>

<p>Mathworld has a brief page on <a href="http://mathworld.wolfram.com/RiffleShuffle.html">riffle shuffle</a>. 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$.</p>

<p>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.)</p>

<p>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 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
0 &amp; 2 &amp; 4 &amp; 1 &amp; 3 &amp; 5\end{pmatrix}=\begin{pmatrix}0 \end{pmatrix} \begin{pmatrix}5 \end{pmatrix} \begin{pmatrix}1 &amp; 2 &amp; 4 &amp;3 \end{pmatrix}.
$$</p>

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

<p>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.</p>

<p>Good resources on the related mathematics are just as valuable as an algorithm. Thanks!</p>

CC BY-SA 3.0
2012-10-14T10:38:42.567Z
There is a $O(n\lg n)$ time solution (with $O(1)$ extra space). I don't know any linear-time solution.
Radu GRIGore
CC BY-SA 3.0
2012-10-14T13:06:07.067Z
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.
Yuval Filmus
CC BY-SA 3.0
2012-10-14T13:43:54.873Z
@Radu Similar to [this question](http://cstheory.stackexchange.com/questions/12798/stable-comparison-sort-with-o1-auxiliary-memory-and-on-log-n-average-ru), this problem probably does not have a solution using only $O(1)$ extra space, but $O(\log n)$ extra space.
Tyson Williams
CC BY-SA 3.0
2012-10-14T14:37:10.417Z
@TysonWilliams, I meant extra words, obviously. This one is a better reference, btw: http://www.computational-geometry.org/mailing-lists/compgeom-announce/2003-December/000852.html
Radu GRIGore
CC BY-SA 3.0
2012-10-14T14:46:22.790Z
(See especially the part that says how only complexity theorists use bit-level RAM and everyone else uses word-level RAM. :) That doesn't mean the others don't know the difference.)
Radu GRIGore
CC BY-SA 3.0
2012-10-14T15:11:51.993Z
@Radu Exactly, which is why complexity theorists like myself make sure that everyone else understands the difference.
Tyson Williams
CC BY-SA 3.0
2012-10-14T22:29:37.383Z
I take my comment (and vote to close) back! (Though the question is answered in the literature.)
Yuval Filmus
CC BY-SA 3.0
2012-10-15T04:06:08.133Z
I heard this question from a CS student last week, who heard it at a job interview.
Jeffε
<ds.algorithms><time-complexity>
Linear time in-place riffle shuffle algorithm
Johny
# Linear time in-place riffle shuffle algorithm

(Asked by: username_0 on 2012-10-14)

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](http://mathworld.wolfram.com/RiffleShuffle.html). 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!

**Tags:** ds.algorithms, time-complexity

> **Comments:**
> **username_1**: There is a $O(n\lg n)$ time solution (with $O(1)$ extra space). I don't know any linear-time solution.  
> **username_2**: 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.  
> **username_3**: @Radu Similar to [this question](http://cstheory.stackexchange.com/questions/12798/stable-comparison-sort-with-o1-auxiliary-memory-and-on-log-n-average-ru), this problem probably does not have a solution using only $O(1)$ extra space, but $O(\log n)$ extra space.  
> **username_1**: @TysonWilliams, I meant extra words, obviously. This one is a better reference, btw: http://www.computational-geometry.org/mailing-lists/compgeom-announce/2003-December/000852.html  
> **username_1**: (See especially the part that says how only complexity theorists use bit-level RAM and everyone else uses word-level RAM. :) That doesn't mean the others don't know the difference.)  
> **username_3**: @Radu Exactly, which is why complexity theorists like myself make sure that everyone else understands the difference.  
> **username_2**: I take my comment (and vote to close) back! (Though the question is answered in the literature.)  
> **username_4**: I heard this question from a CS student last week, who heard it at a job interview.  

---

## 3 answers

### Answer by username_2 on 2012-10-14. Score: 12 | Accepted answer

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](http://webhome.cs.uvic.ca/~jellis/Publications/merge.ps) (section 7). Ellis, Krahn and Fan, [Computing the Cycles in the Perfect Shuffle Permutation](http://webhome.cs.uvic.ca/~jellis/Publications/shuffle.ps) 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](http://www.cs.utoronto.ca/~fich/permuting.ps), 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](http://www.sciencedirect.com/science/article/pii/0012365X7890002X); Fredricksen and Kessler, [An algorithm for generating necklaces of beads in two colors](http://www.sciencedirect.com/science/article/pii/0012365X86900890)).

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.

> **Comments:**
> **username_2**: See also username_5's answer, which uses http://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!  
> **username_0**: 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.  

---

### Answer by username_5 on 2012-10-15. Score: 6

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.

> **Comments:**
> **username_1**: 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.  

---

### Answer by username_6 on 2012-10-14. Score: 2

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.

> **Comments:**
> **username_6**: 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.  

---

