Suppose we have an array a1, a2,... , an, b1, b2, ..., bn.
The goal is to change this array to a1, b1, a2, b2, ..., an, bn in O(n) time and in O(1) space. In other words, we need a linear-time algorithm to modify the array in place, with no more than a constant amount of extra storage.
How can this be done?
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!).
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.
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.
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.
It's called in-place in-shuffle problem. Here is its implementation in C++ based on here.
void in_place_in_shuffle(int arr[], int length)
{
assert(arr && length>0 && !(length&1));
// shuffle to {5, 0, 6, 1, 7, 2, 8, 3, 9, 4}
int i,startPos=0;
while(startPos<length)
{
i=_LookUp(length-startPos);
_ShiftN(&arr[startPos+(i-1)/2],(length-startPos)/2,(i-1)/2);
_PerfectShuffle(&arr[startPos],i-1);
startPos+=(i-1);
}
// local swap to {0, 5, 1, 6, 2, 7, 3, 8, 4, 9}
for (int i=0; i<length; i+=2)
swap(arr[i], arr[i+1]);
}
// cycle
void _Cycle(int Data[],int Lenth,int Start)
{
int Cur_index,Temp1,Temp2;
Cur_index=(Start*2)%(Lenth+1);
Temp1=Data[Cur_index-1];
Data[Cur_index-1]=Data[Start-1];
while(Cur_index!=Start)
{
Temp2=Data[(Cur_index*2)%(Lenth+1)-1];
Data[(Cur_index*2)%(Lenth+1)-1]=Temp1;
Temp1=Temp2;
Cur_index=(Cur_index*2)%(Lenth+1);
}
}
// loop-move array
void _Reverse(int Data[],int Len)
{
int i,Temp;
for(i=0;i<Len/2;i++)
{
Temp=Data[i];
Data[i]=Data[Len-i-1];
Data[Len-i-1]=Temp;
}
}
void _ShiftN(int Data[],int Len,int N)
{
_Reverse(Data,Len-N);
_Reverse(&Data[Len-N],N);
_Reverse(Data,Len);
}
// perfect shuffle of satisfying [Lenth=3^k-1]
void _PerfectShuffle(int Data[],int Lenth)
{
int i=1;
if(Lenth==2)
{
i=Data[Lenth-1];
Data[Lenth-1]=Data[Lenth-2];
Data[Lenth-2]=i;
return;
}
while(i<Lenth)
{
_Cycle(Data,Lenth,i);
i=i*3;
}
}
// look for 3^k that nearnest to N
int _LookUp(int N)
{
int i=3;
while(i<=N+1) i*=3;
if(i>3) i=i/3;
return i;
}
Test:
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int length = sizeof(arr)/sizeof(int);
in_place_in_shuffle(arr, length);
After this, arr[] will be {0, 5, 1, 6, 2, 7, 3, 8, 4, 9}.
If you can transform the array into a linked-list first, the problem becomes trivial.
