26 May 2004

Nice problem via some Microsoft blog (can't remember which): You are given an array with an even number N of integers. Suffle the array according to the rule A[i] = a[(i%2)(N/2) + i/2], where a[i] and A[i] are the values of the i-th location before and after the shuffle (zero-based index). Do it in O(N logN) time and O(1) space. Example: [0, 1, 2, 3, 4, 5] becomes [0, 3, 1, 4, 2, 5] NOTE: you do not know anything about the values in the array (i.e. 0, 1, 2,... are specific to this example)

4 comments:

rgrig said...

Solution via venco from topcoder:

The element that is initially in position i must end up in position f(i)=(i%2)*(N/2)+floor(i/2). Now think backward. What element do we need to have in position i at the end? To determine that we need to find g such that g(f(i))=i for all i=0..N-1.

We have:
2*f(i) = if even(i) then i else N+i-1

which, noticing that N-1 is odd, implies:
(2*f(i))%(N-1) = i

so:
g(i) = (2*i)%(N-1)

The functions f and g are in fact permutations of 0, 1,... N-1. Computing g is NOT esential for the solution. But it is helpful.

Each number i generates a (finite) set by repeated applications of f(i). S(i) = {i} union {x | exists y in S(i) such that x = f(i)}, or S(i)={i, f(i), f(f(i)), f(f(f(i))), ...}. The set is completely determined by i. Note that if j is in S(i) then S(i)=S(j) because f is inversable. So we have an equivalence relation and a partition of 0.. N-1.

Now we do this: "for each set of equivalent elements put them in the correct position". The functions f and g give each S a linked list structure: f(j) is the "next" element for j and g(j) is the "previous" element for j. So it is easy to "rotate" the list by one by using either f or g.

Only one problem remains. How do we make sure that we process each set of equivalent elements only once? By choosing a representative element. This can be done by using the usual total order on 0.. N-1: just choose the minimum (or maximum) element.

Venco's solution uses g for "rotation" and minimum element as the representative of the equivalence class. See his post.

Now.. all I need to do is to prove O(N logN) time (space is clearly O(1)).

Anonymous said...

While this solution has the potential to be fast enough, I fail to see how it could be implemented to run in O(NlogN) time using only O(1) space.
In fact, I believe the implementation given in the link has a worst case of O(N^2) when N-1 is a prime number, while it's easy to see that O(N) can be reached using space also proportional to N.

A more direct approach is the following: let's say we want to reorder the array [0,1,2,3,4,5,6,7]. Divide the thing in half and take the first pair in each half ([0,1] and [4,5] in this case). Swap the second element of the first pair with the first element of the second pair ([0,4] and [1,5] in this case). Do the same for the second pairs in each half, third pairs in each half, etc.

Now we're left with the following arrray: [0,4,2,6,1,5,3,7]. Consecutive numbers in the array are already in order, so we could think of this new array as an array of pairs [p0, p1, p2, p3]. Note that to get the final arrangement that we want for the original array of pairs, we need to apply the same procedure to this array of pairs. You can now easily complete the recursive or inductive reasoning to get the final solution.

Since every step involves at most N swaps, and the number of steps is given by logN ('cause we group things in two), the time complexity is what we want.

Anonymous said...

Errata: Where I said "Note that to get the final arrangement that we want for the original array of pairs...", it should be "original array of NUMBERS".

rgrig said...

Thank you!

Your solution is quite nice and it is really easy to see why it is O(nlgn).

I should say that the solution I presented in the earlier comment is something you can do for any permutation and, on average, it is O(nlgn), but not in the worst case. It certainly looks like for the family of permutations considered here there are two big cycles when n−1 is prime so the time would be Ω(n^2) as you say.

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.