Interleaving array {a1,a2,....,an,b1,b2,...,bn} to {a1,b1,a2,b2,a3,b3} in O(n) time and O(1) space

Question

I have to interleave a given array of the form

{a1,a2,....,an,b1,b2,...,bn} 

as

{a1,b1,a2,b2,a3,b3} 

in O(n) time and O(1) space.

Example:

Input - {1,2,3,4,5,6}
Output- {1,4,2,5,3,6}

This is the arrangement of elements by indices:

Initial Index    Final Index
 0                   0
 1                   2
 2                   4
 3                   1
 4                   3
 5                   5

By observation after taking some examples, I found that ai (i<n/2) goes from index (i) to index (2i) & bi (i>=n/2) goes from index (i) to index (((i-n/2)*2)+1). You can verify this yourselves. Correct me if I am wrong.

However, I am not able to correctly apply this logic in code.

My pseudo code:

for (i = 0 ; i < n ; i++)
    if(i < n/2)
        swap(arr[i],arr[2*i]);
    else
        swap(arr[i],arr[((i-n/2)*2)+1]);

It's not working.

How can I write an algorithm to solve this problem?

Answer 1

Element bn is in the correct position already, so lets forget about it and only worry about the other N = 2n-1 elements. Notice that N is always odd.

Now the problem can be restated as "move the element at each position i to position 2i % N"

The item at position 0 doesn't move, so lets start at position 1.

If you start at position 1 and move it to position 2%N, you have to remember the item at position 2%N before you replace it. The the one from position 2%N goes to position 4%N, the one from 4%N goes to 8%N, etc., until you get back to position 1, where you can put the remaining item into the slot you left.

You are guaranteed to return to slot 1, because N is odd and multiplying by 2 mod an odd number is invertible. You are not guaranteed to cover all positions before you get back, though. The whole permutation will break into some number of cycles.

If you can start this process at one element from each cycle, then you will do the whole job. The trouble is figuring out which ones are done and which ones aren't, so you don't cover any cycle twice.

I don't think you can do this for arbitrary N in a way that meets your time and space constraints... BUT if N = 2^x-1 for some x, then this problem is much easier, because each cycle includes exactly the cyclic shifts of some bit pattern. You can generate single representatives for each cycle (called cycle leaders) in constant time per index. (I'll describe the procedure in an appendix at the end)

Now we have the basis for a recursive algorithm that meets your constraints.

Given [a1...an,b1...bn]:

1. Find the largest x such that 2^x <= 2n

2. Rotate the middle elements to create [a1...ax,b1...bx,ax+1...an,bx+1...bn]

3. Interleave the first part of the array in linear time using the above-described procedure, since it will have modulus 2^x-1

4. Recurse to interleave the last part of the array.

Since the last part of the array we recurse on is guaranteed to be at most half the size of the original, we have this recurrence for the time complexity:

T(N) = O(N) + T(N/2)
     = O(N)

And note that the recursion is a tail call, so you can do this in constant space.

Appendix: Generating cycle leaders for shifts mod 2^x-1

A simple algorithm for doing this is given in a paper called "An algorithm for generating necklaces of beads in 2 colors" by Fredricksen and Kessler. You can get a PDF here: https://core.ac.uk/download/pdf/82148295.pdf

The implementation is easy. Start with x 0s, and repeatedly:

1. Set the lowest order 0 bit to 1. Let this be bit y
2. Copy the lower order bits starting from the top
3. The result is a cycle leader if x-y divides x
4. Repeat until you have all x 1s

For example, if x=8 and we're at 10011111, the lowest 0 is bit 5. We switch it to 1 and then copy the remainder from the top to give 10110110. 8-5=3, though, and 3 does not divide 8, so this one is not a cycle leader and we continue to the next.