Why does array size have to be 3^k+1 for cycle leader iteration algorithm to work?

Question

The cycle leader iteration algorithm is an algorithm for shuffling an array by moving all even-numbered entries to the front and all odd-numbered entries to the back while preserving their relative order. For example, given this input:

a 1 b 2 c 3 d 4 e 5

the output would be

a b c d e 1 2 3 4 5

This algorithm runs in O(n) time and uses only O(1) space.

One unusual detail of the algorithm is that it works by splitting the array up into blocks of size 3^k+1. Apparently this is critical for the algorithm to work correctly, but I have no idea why this is.

Why is the choice of 3^k + 1 necessary in the algorithm?

Thanks!

Answer 1

This is going to be a long answer. The answer to your question isn't simple and requires some number theory to fully answer. I've spent about half a day working through the algorithm and I now have a good answer, but I'm not sure I can describe it succinctly.

The short version:

• Breaking the input into blocks of size 3^k + 1 essentially breaks the input apart into blocks of size 3^k - 1 surrounded by two elements that do not end up moving.

• The remaining 3^k - 1 elements in the block move according to an interesting pattern: each element moves to the position given by dividing the index by two modulo 3^k.

• This particular motion pattern is connected to a concept from number theory and group theory called primitive roots.

• Because the number two is a primitive root modulo 3^k, beginning with the numbers 1, 3, 9, 27, etc. and running the pattern is guaranteed to cycle through all the elements of the array exactly once and put them into the proper place.

• This pattern is highly dependent on the fact that 2 is a primitive root of 3^k for any k ≥ 1. Changing the size of the array to another value will almost certainly break this because the wrong property is preserved.

The Long Version

To present this answer, I'm going to proceed in steps. First, I'm going to introduce cycle decompositions as a motivation for an algorithm that will efficiently shuffle the elements around in the right order, subject to an important caveat. Next, I'm going to point out an interesting property of how the elements happen to move around in the array when you apply this permutation. Then, I'll connect this to a number-theoretic concept called primitive roots to explain the challenges involved in implementing this algorithm correctly. Finally, I'll explain why this leads to the choice of 3^k + 1 as the block size.

Cycle Decompositions

Let's suppose that you have an array A and a permutation of the elements of that array. Following the standard mathematical notation, we'll denote the permutation of that array as σ(A). We can line the initial array A up on top of the permuted array σ(A) to get a sense for where every element ended up. For example, here's an array and one of its permutations:

   A    0 1 2 3 4
 σ(A)   2 3 0 4 1

One way that we can describe a permutation is just to list off the new elements inside that permutation. However, from an algorithmic perspective, it's often more helpful to represent the permutation as a cycle decomposition, a way of writing out a permutation by showing how to form that permutation by beginning with the initial array and then cyclically permuting some of its elements.

Take a look at the above permutation. First, look at where the 0 ended up. In σ(A), the element 0 ended up taking the place of where the element 2 used to be. In turn, the element 2 ended up taking the place of where the element 0 used to be. We denote this by writing (0 2), indicating that 0 should go where 2 used to be, and 2 should go were 0 used to be.

Now, look at the element 1. The element 1 ended up where 4 used to be. The number 4 then ended up where 3 used to be, and the element 3 ended up where 1 used to be. We denote this by writing (1 4 3), that 1 should go where 4 used to be, that 4 should go where 3 used to be, and that 3 should go where 1 used to be.

Combining these together, we can represent the overall permutation of the above elements as (0 2)(1 4 3) - we should swap 0 and 2, then cyclically permute 1, 4, and 3. If we do that starting with the initial array, we'll end up at the permuted array that we want.

Cycle decompositions are extremely useful for permuting arrays in place because it's possible to permute any individual cycle in O(C) time and O(1) auxiliary space, where C is the number of elements in the cycle. For example, suppose that you have a cycle (1 6 8 4 2). You can permute the elements in the cycle with code like this:

int[] cycle = {1, 6, 8, 4, 2};

int temp = array[cycle[0]];
for (int i = 1; i < cycle.length; i++) {
    swap(temp, array[cycle[i]]);
}
array[cycle[0]] = temp;

This works by just swapping everything around until everything comes to rest. Aside from the space usage required to store the cycle itself, it only needs O(1) auxiliary storage space.

In general, if you want to design an algorithm that applies a particular permutation to an array of elements, you can usually do so by using cycle decompositions. The general algorithm is the following:

for (each cycle in the cycle decomposition algorithm) {
   apply the above algorithm to cycle those elements;
}

The overall time and space complexity for this algorithm depends on the following:

1. How quickly can we determine the cycle decomposition we want?
2. How efficiently can we store that cycle decomposition in memory?

To get an O(n)-time, O(1)-space algorithm for the problem at hand, we're going to show that there's a way to determine the cycle decomposition in O(1) time and space. Since everything will get moved exactly once, the overall runtime will be O(n) and the overall space complexity will be O(1). It's not easy to get there, as you'll see, but then again, it's not awful either.

The Permutation Structure

The overarching goal of this problem is to take an array of 2n elements and shuffle it so that even-positioned elements end up at the front of the array and odd-positioned elements end up at the end of the array. Let's suppose for now that we have 14 elements, like this:

 0  1  2  3  4  5  6  7  8  9 10 11 12 13

We want to shuffle the elements so that they come out like this:

 0  2  4  6  8 10 12  1  3  5  7  9 11 13

There are a couple of useful observations we can have about the way that this permutation arises. First, notice that the first element does not move in this permutation, because even-indexed elements are supposed to show up in the front of the array and it's the first even-indexed element. Next, notice that the last element does not move in this permutation, because odd-indexed elements are supposed to end up at the back of the array and it's the last odd-indexed element.

These two observations, put together, means that if we want to permute the elements of the array in the desired fashion, we actually only need to permute the subarray consisting of the overall array with the first and last elements dropped off. Therefore, going forward, we are purely going to focus on the problem of permuting the middle elements. If we can solve that problem, then we've solved the overall problem.

Now, let's look at just the middle elements of the array. From our above example, that means that we're going to start with an array like this one:

 Element    1  2  3  4  5  6  7  8  9 10 11 12
 Index      1  2  3  4  5  6  7  8  9 10 11 12

We want to get the array to look like this:

 Element    2  4  6  8 10 12  1  3  5  7  9 11
 Index      1  2  3  4  5  6  7  8  9 10 11 12

Because this array was formed by taking a 0-indexed array and chopping off the very first and very last element, we can treat this as a one-indexed array. That's going to be critically important going forward, so be sure to keep that in mind.

So how exactly can we go about generating this permutation? Well, for starters, it doesn't hurt to take a look at each element and to try to figure out where it began and where it ended up. If we do so, we can write things out like this:

• The element at position 1 ended up at position 7.
• The element at position 2 ended up at position 1.
• The element at position 3 ended up at position 8.
• The element at position 4 ended up at position 2.
• The element at position 5 ended up at position 9.
• The element at position 6 ended up at position 3.
• The element at position 7 ended up at position 10.
• The element at position 8 ended up at position 4.
• The element at position 9 ended up at position 11.
• The element at position 10 ended up at position 5.
• The element at position 11 ended up at position 12.
• The element at position 12 ended up at position 6.

If you look at this list, you can spot a few patterns. First, notice that the final index of all the even-numbered elements is always half the position of that element. For example, the element at position 4 ended up at position 2, the element at position 12 ended up at position 6, etc. This makes sense - we pushed all the even elements to the front of the array, so half of the elements that came before them will have been displaced and moved out of the way.

Now, what about the odd-numbered elements? Well, there are 12 total elements. Each odd-numbered element gets pushed to the second half, so an odd-numbered element at position 2k+1 will get pushed to at least position 7. Its position within the second half is given by the value of k. Therefore, the elements at an odd position 2k+1 gets mapped to position 7 + k.

We can take a minute to generalize this idea. Suppose that the array we're permuting has length 2n. An element at position 2x will be mapped to position x (again, even numbers get halfed), and an element at position 2x+1 will be mapped to position n + 1 + x. Restating this:

The final position of an element at position p is determined as follows:

• If p = 2x for some integer x, then 2x ↦ x
• If p = 2x+1 for some integer x, then 2x+1 ↦ n + 1 + x

And now we're going to do something that's entirely crazy and unexpected. Right now, we have a piecewise rule for determining where each element ends up: we either divide by two, or we do something weird involving n + 1. However, from a number-theoretic perspective, there is a single, unified rule explaining where all elements are supposed to end up.

The insight we need is that in both cases, it seems like, in some way, we're dividing the index by two. For the even case, the new index really is formed by just dividing by two. For the odd case, the new index kinda looks like it's formed by dividing by two (notice that 2x+1 went to x + (n + 1)), but there's an extra term in there. In a number-theoretic sense, though, both of these really correspond to division by two. Here's why.

Rather than taking the source index and dividing by two to get the destination index, what if we take the destination index and multiply by two? If we do that, an interesting pattern emerges.

Suppose our original number was 2x. The destination is then x, and if we double the destination index to get back 2x, we end up with the source index.

Now suppose that our original number was 2x+1. The destination is then n + 1 + x. Now, what happens if we double the destination index? If we do that, we get back 2n + 2 + 2x. If we rearrange this, we can alternatively rewrite this as (2x+1) + (2n+1). In other words, we've gotten back the original index, plus an extra (2n+1) term.

Now for the kicker: what if all of our arithmetic is done modulo 2n + 1? In that case, if our original number was 2x + 1, then twice the destination index is (2x+1) + (2n+1) = 2x + 1 (modulo 2n+1). In other words, the destination index really is half of the source index, just done modulo 2n+1!

This leads us to a very, very interesting insight: the ultimate destination of each of the elements in a 2n-element array is given by dividing that number by two, modulo 2n+1. This means that there really is a nice, unified rule for determining where everything goes. We just need to be able to divide by two modulo 2n+1. It just happens to work out that in the even case, this is normal integer division, and in the odd case, it works out to taking the form n + 1 + x.

Consequently, we can reframe our problem in the following way: given a 1-indexed array of 2n elements, how do we permute the elements so that each element that was originally at index x ends up at position x/2 mod (2n+1)?

Cycle Decompositions Revisited

At this point, we've made quite a lot of progress. Given any element, we know where that element should end up. If we can figure out a nice way to get a cycle decomposition of the overall permutation, we're done.

This is, unfortunately, where things get complicated. Suppose, for example, that our array has 10 elements. In that case, we want to transform the array like this:

 Initial:  1  2  3  4  5  6  7  8  9 10
 Final:    2  4  6  8 10  1  3  5  7  9

The cycle decomposition of this permutation is (1 6 3 7 9 10 5 8 4 2). If our array has 12 elements, we want to transform it like this:

 Initial:  1  2  3  4  5  6  7  8  9 10 11 12
 Final:    2  4  6  8 10 12  1  3  5  7  9 11

This has cycle decomposition (1 7 10 5 9 11 12 6 3 8 4 2 1). If our array has 14 elements, we want to transform it like this:

 Initial:  1  2  3  4  5  6  7  8  9 10 11 12 13 14
 Final:    2  4  6  8 10 12 14  1  3  5  7  9 11 13

This has cycle decomposition (1 8 4 2)(3 9 12 6)(5 10)(7 11 13 14). If our array has 16 elements, we want to transform it like this:

 Initial:  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
 Final:    2  4  6  8 10 12 14 16  1  3  5  7  9 11 13 15

This has cycle decomposition (1 9 13 15 16 8 4 2)(3 10 5 11 14 7 12 6).

The problem here is that these cycles don't seem to follow any predictable patterns. This is a real problem if we're going to try to solve this problem in O(1) space and O(n) time. Even though given any individual element we can figure out what cycle contains it and we can efficiently shuffle that cycle, it's not clear how we figure out what elements belong to what cycles, how many different cycles there are, etc.

Primitive Roots

This is where number theory comes in. Remember that each element's new position is formed by dividing that number by two, modulo 2n+1. Thinking about this backwards, we can figure out which number will take the place of each number by multiplying by two modulo 2n+1. Therefore, we can think of this problem by finding the cycle decomposition in reverse: we pick a number, keep multiplying it by two and modding by 2n+1, and repeat until we're done with the cycle.

This gives rise to a well-studied problem. Suppose that we start with the number k and think about the sequence k, 2k, 2²k, 2³k, 2⁴k, etc., all done modulo 2n+1. Doing this gives different patterns depending on what odd number 2n+1 you're modding by. This explains why the above cycle patterns seem somewhat arbitrary.

I have no idea how anyone figured this out, but it turns out that there's a beautiful result from number theory that talks about what happens if you take this pattern mod 3^k for some number k:

Theorem: Consider the sequence 3^s, 3^s·2, 3^s·2², 3^s·2³, 3^s·2⁴, etc. all modulo 3^k for some k ≥ s. This sequence cycles through through every number between 1 and 3^k, inclusive, that is divisible by 3^s but not divisible by 3^s+1.

We can try this out on a few examples. Let's work modulo 27 = 3². The theorem says that if we look at 3, 3 · 2, 3 · 4, etc. all modulo 27, then we should see all the numbers less than 27 that are divisible by 3 and not divisible by 9. Well, let'see what we get:

• 3 · 2⁰ = 3 · 1 = 3 = 3 mod 27
• 3 · 2¹ = 3 · 2 = 6 = 6 mod 27
• 3 · 2² = 3 · 4 = 12 = 12 mod 27
• 3 · 2³ = 3 · 8 = 24 = 24 mod 27
• 3 · 2⁴ = 3 · 16 = 48 = 21 mod 27
• 3 · 2⁵ = 3 · 32 = 96 = 15 mod 27
• 3 · 2⁶ = 3 · 64 = 192 = 3 mod 27

We ended up seeing 3, 6, 12, 15, 21, and 24 (though not in that order), which are indeed all the numbers less than 27 that are divisible by 3 but not divisible by 9.

We can also try this working mod 27 and considering 1, 2, 2², 2³, 2⁴ mod 27, and we should see all the numbers less than 27 that are divisible by 1 and not divisible by 3. In other words, this should give back all the numbers less than 27 that aren't divisible by 3. Let's see if that's true:

• 2⁰ = 1 = 1 mod 27
• 2¹ = 2 = 2 mod 27
• 2² = 4 = 4 mod 27
• 2³ = 8 = 8 mod 27
• 2⁴ = 16 = 16 mod 27
• 2⁵ = 32 = 5 mod 27
• 2⁶ = 64 = 10 mod 27
• 2⁷ = 128 = 20 mod 27
• 2⁸ = 256 = 13 mod 27
• 2⁹ = 512 = 26 mod 27
• 2¹⁰ = 1024 = 25 mod 27
• 2¹¹ = 2048 = 23 mod 27
• 2¹² = 4096 = 19 mod 27
• 2¹³ = 8192 = 11 mod 27
• 2¹⁴ = 16384 = 22 mod 27
• 2¹⁵ = 32768 = 17 mod 27
• 2¹⁶ = 65536 = 7 mod 27
• 2¹⁷ = 131072 = 14 mod 27
• 2¹⁸ = 262144 = 1 mod 27

Sorting these, we got back the numbers 1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26 (though not in that order). These are exactly the numbers between 1 and 26 that aren't multiples of three!

This theorem is crucial to the algorithm for the following reason: if 2n+1 = 3^k for some number k, then if we process the cycle containing 1, it will properly shuffle all numbers that aren't multiples of three. If we then start the cycle at 3, it will properly shuffle all numbers that are divisible by 3 but not by 9. If we then start the cycle at 9, it will properly shuffle all numbers that are divisible by 9 but not by 27. More generally, if we use the cycle shuffle algorithm on the numbers 1, 3, 9, 27, 81, etc., then we will properly reposition all the elements in the array exactly once and will not have to worry that we missed anything.

So how does this connect to 3^k + 1? Well, we need to have that 2n + 1 = 3^k, so we need to have that 2n = 3^k - 1. But remember - we dropped the very first and very last element of the array when we did this! Adding those back in tells us that we need blocks of size 3^k + 1 for this procedure to work correctly. If the blocks are this size, then we know for certain that the cycle decomposition will consist of a cycle containing 1, a nonoverlapping cycle containing 3, a nonoverlapping cycle containing 9, etc. and that these cycles will contain all the elements of the array. Consequently, we can just start cycling 1, 3, 9, 27, etc. and be absolutely guaranteed that everything gets shuffled around correctly. That's amazing!

And why is this theorem true? It turns out that a number k for which 1, k, k², k³, etc. mod pⁿ that cycles through all the numbers that aren't multiples of p (assuming p is prime) is called a primitive root of the number pⁿ. There's a theorem that says that 2 is a primitive root of 3^k for all numbers k, which is why this trick works. If I have time, I'd like to come back and edit this answer to include a proof of this result, though unfortunately my number theory isn't at a level where I know how to do this.

Summary

This problem was tons of fun to work on. It involves cute tricks with dividing by two modulo an odd numbers, cycle decompositions, primitive roots, and powers of three. I'm indebted to this arXiv paper which described a similar (though quite different) algorithm and gave me a sense for the key trick behind the technique, which then let me work out the details for the algorithm you described.

Hope this helps!

Answer 2

Here is most of the mathematical argument missing from templatetypedef’s answer. (The rest is comparatively boring.)

---

Lemma: for all integers k >= 1, we have 2^(2*3^(k-1)) = 1 + 3^k mod 3^(k+1).

Proof: by induction on k.

Base case (k = 1): we have 2^(2*3^(1-1)) = 4 = 1 + 3^1 mod 3^(1+1).

Inductive case (k >= 2): if 2^(2*3^(k-2)) = 1 + 3^(k-1) mod 3^k, then q = (2^(2*3^(k-2)) - (1 + 3^(k-1)))/3^k.

 2^(2*3^(k-1)) = (2^(2*3^(k-2)))^3
               = (1 + 3^(k-1) + 3^k*q)^3
               = 1 + 3*(3^(k-1)) + 3*(3^(k-1))^2 + (3^(k-1))^3
                   + 3*(1+3^(k-1))^2*(3^k*q) + 3*(1+3^(k-1))*(3^k*q)^2 + (3^k*q)^3
               = 1 + 3^k mod 3^(k+1).

---

Theorem: for all integers i >= 0 and k >= 1, we have 2^i = 1 mod 3^k if and only if i = 0 mod 2*3^(k-1).

Proof: the “if” direction follows from the Lemma. If i = 0 mod 2*3^(k-1), then

2^i = (2^(2*3^(k-1)))^(i/(2*3^(k-1)))
    = (1+3^k)^(i/(2*3^(k-1))) mod 3^(k+1)
    = 1 mod 3^k.

The “only if” direction is by induction on k.

Base case (k = 1): if i != 0 mod 2, then i = 1 mod 2, and

2^i = (2^2)^((i-1)/2)*2
    = 4^((i-1)/2)*2
    = 2 mod 3
    != 1 mod 3.

Inductive case (k >= 2): if 2^i = 1 mod 3^k, then 2^i = 1 mod 3^(k-1), and the inductive hypothesis implies that i = 0 mod 2*3^(k-2). Let j = i/(2*3^(k-2)). By the Lemma,

1 = 2^i mod 3^k
  = (1+3^(k-1))^j mod 3^k
  = 1 + j*3^(k-1) mod 3^k,

where the dropped terms are divisible by (3^(k-1))^2, so j = 0 mod 3, and i = 0 mod 2*3^(k-1).