array interleaving problem

Question

I was looking for something over the web when I came across this question. Have no idea of how to solve it. Help me out please.

Suppose we have an array a1,a2,... ,an, b1,b2,..., bn

How to change this array to a1,b1,a2,b2, ..., an,bn in O(n) time and in O(1) space.

Answer 1

If you can transform the array into a linked-list first, the problem becomes trivial.

Answer 2

This is the sequence and notes I worked out with pen and paper. I think it, or a variation, will hold for any larger n.

Each line represents a different step and () signifies what is being moved this step and [] is what has been moved from last step. The array itself is used as storage and two pointers (one for L and one for N) are required to determine what to move next. L means "letter line" and N is "number line" (what is moved).

  A  B  C  D   1  2  3  4

L A  B  C (D)  1  2  3  4 first is L, no need to move last N
N A  B  C (3)  1  2 [D] 4
L A  B (C) 2   1 [3] D  4
N A  B  1 (2) [C] 3  D  4
L A (B) 1 [2]  C  3  D  4
N A (1)[B] 2   C  3  D  4
  A [1] B  2   C  3  D  4 done, no need to move A

Note the varying "pointer jumps" - the L pointer always decrements by 1 (as it can not be eaten into faster than that) but the N pointer jumps according to if it "replaced itself" (in spot, jump down two) or if it swapped something in (no jump so the next something can get its go!)

YMMV

Answer 3

I assume you know where the b's start? I can't think of a simple way to do it with one array, but it's trivial with two:

int x = 0;
while(a_index < b_start && b_index < array.length){
   newArray[x] = array[a_index];
   x++;
   newArray[x] = array[b_index];
   x++;
}
array = newArray;

Answer 4

First, the theory: Rearrange the elements in 'permutation cycles'. Take an element and place it at its new position, displacing the element that is currently there. Then you take that displaced element and put it in its new position. This displaces yet another element, so rinse and repeat. If the element displaced belongs to the position of the element you first started with, you have completed one cycle.

Actually, yours is a special case of the question I asked here, which was: How do you rearrange an array to any given order in O(N) time and O(1) space? In my question, the rearranged positions are described by an array of numbers, where the number at the nth position specifies the index of the element in the original array.

However, you don't have this additional array in your problem, and allocating it would take O(N) space. Fortunately, we can calculate the value of any element in this array on the fly, like this:

int rearrange_pos(int x) {
    if (x % 2 == 0) return x / 2;
    else return (x - 1) / 2 + n; // where n is half the size of the total array
}

I won't duplicate the rearranging algorithm itself here; it can be found in the accepted answer for my question.

Edit: As Jason has pointed out, the answer I linked to still needs to allocate an array of bools, making it O(N) space. This is because a permutation can be made up of multiple cycles. I've been trying to eliminate the need for this array for your special case, but without success.. There doesn't seem to be any usable pattern. Maybe someone else can help you here.

Answer 5

This problem is not as trivial as people make out to be. Homework? LOL.

The following link has a solution: http://arxiv.org/abs/0805.1598

Answer 6

This problem isn't as easy as it seems, but after some thought, the algorithm to accomplish this isn't too bad. You'll notice the first and last element are already in place, so we don't need to worry about them. We will keep a left index variable which represents the first item in the first half of the array that needs changed. After that we set a right index variable to the first item in the 2nd half of the array that needs changed. Now all we do is swap the item at the right index down one-by-one until it reaches the left index item. Increment the left index by 2 and the right index by 1, and repeat until the indexes overlap or the left goes past the right index (the right index will always end on the last index of the array). We increment the left index by two every time because the item at left + 1 has already naturally fallen into place.

Pseudocode

1. Set left index to 1
2. Set right index to the middle (array length / 2)
3. Swap the item at the right index with the item directly preceding it until it replaces the item at the left index
4. Increment the left index by 2
5. Increment the right index by 1

6. Repeat 3 through 5 until the left index becomes greater than or equal to the right index

   Interleaving algorithm in C(#)

   protected void Interleave(int[] arr)
   {
   int left = 1;
   int right = arr.Length / 2;
   int temp;

   while (left < right)  
   {  
       for (int i = right; i > left; i--)  
       {  
           temp = arr[i];  
           arr[i] = arr[i - 1];  
           arr[i - 1] = temp;  
       }  
   
   
   left += 2;  
   right += 1;  
   
   
   }  
   

   }
   This algorithm uses O(1) storage (with the temp variable, which could be eliminated using the addition/subtraction swap technique) I'm not very good at runtime analysis, but I believe this is still O(n) even though we're performing many swaps. Perhaps someone can further explore its runtime analysis.

Answer 7

Let A represent the original array a1,a2,... ,an, b1,b2,..., bn. We swap the second quarter of the array with the third quarter of the array. We then group the first and the second quarter and call this array A1 and the third and the fourth quarter and call the array A2. We apply this technique recursively for A1, and then for A2.

For example: Assume A={a1,a2,b1,a2}. The four quarters are {a1},{a2},{b1},{b2}. We swap the second quarter with the third quarter and we get {a1},{b1},{a1},{b2}. We are done. Assume A={a1,a2,a3,a4,b1,a2,b3,b4}. We swap the second quarter with the third quarter. We get {a1,a2,b1,b2,a3,a4,b3,b4}. Then A1={a1,a2,b1,b2} and A2={a3,a4,b3,b4}. We apply the algorithm recursively for A1 and A2.

The algorithm takes O(1) memory, but how much time does it take? Let's assume that swapping two individual elements of the array takes O(1) time (actually it takes 3 operations with the in place swapping using xor and no extra memory). Then, assume n=|A| the length of A, we need n/4 swaps and need to solve two other problems half as long: we have T(n)=n/4+2T(n/2). By the master theorem, we get T(n)=O(n*log(n)). This is not O(n).

Can we do better using the exact same technique? Maybe we can improve the time it takes to swap things around. Clearly, if we want to swap two elements, it takes O(1), nothing we can do about that. But we can take advantage of the fact that an array is represented in memory in continuous locations. Thus swapping an entire second quarter with an entire third quarter can be done in O(1) if we have some operator like XOR(memory_start_address1, memory_start_address2, length_in_bytes), where the result is put always at memory_start_address1. Then the equation above becomes T(n)=1+2T(n/2). By the master theorem T(n)=O(n).

The question is: do we have such an operator XOR(memory_start_address1, memory_start_address2, length_in_bytes) ?