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.

Answer 2

The algorithm I'm going to propose is probably not o(n). It's not based on swapping elements but on moving elements which probably could be O(1) if you have a list and not an array.

Given 2N elements, at each iteration (i) you take the element in position N/2 + i and move it to position 2*i

a1,a2,a3,...,an,b1,b2,b3,...,bn
   |            |
a1,b1,a2,a3,...,an,b2,b3,...,bn
         |         |
a1,b1,a2,b2,a3,...,an,b3,...,bn
               |      |
a1,b1,a2,b2,a3,b3,...,an,...,bn

and so on.

example with N = 4

1,2,3,4,5,6,7,8
1,5,2,3,4,6,7,8
1,5,2,6,3,4,7,8
1,5,2,6,3,7,4,8

Answer 3

One idea which is a little complex is supposing each location has the following value:

1, 3, 5, ..., 2n-1 | 2, 4, 6, ..., 2n
a1,a2, ..., an | b1, b2, ..., bn 

Then using inline merging of two sorted arrays as explained in this article in O(n) time an O(1) space complexity. However, we need to manage this indexing during the process.

Answer 4

There is a practical linear time* in-place algorithm described in this question. Pseudocode and C code are included.

It involves swapping the first 1/2 of the items into the correct place, then unscrambling the permutation of the 1/4 of the items that got moved, then repeating for the remaining 1/2 array.

Unscrambling the permutation uses the fact that left items move into the right side with an alternating "add to end, swap oldest" pattern. We can find the i'th index in this permutation with this this rule:

For even i, the end was at i/2.
For odd i, the oldest was added to the end at step (i-1)/2

*The number of data moves is definitely O(N). The question asks for the time complexity of the unscramble index calculation. I believe it is no worse than O(lg lg N).