This is a solution to the rearrange array puzzle posted earlier.
A brief description:
Suppose you are given an array of $2n$ objects
$$[a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n] $$
You need to reorder the array to be
$$[b_1, a_1, b_2, a_2, \dots, b_k, a_k, \dots, b_n, a_n] $$
Hard version: Do this in-place (preferably $O(1)$ space in WORD RAM model), and O(n) time.
(Medium version: Do it in $O(n\log n)$ time, and in-place).
Solution
This puzzle is surprisingly difficult (the $O(n)$ time, in-place version). It seems that we should easily be able to do it, but most first approaches fail. The in-place constraint is what makes it difficult (otherwise we can just make a new array and copy the elements easily).
This puzzle was given to me when I was at Microsoft, the problem apparently being open at the time (at least within the set of people at Microsoft who came across the puzzle).
I was able to solve it, and I was encouraged (by someone on an online forum) to write a paper on it. It only took me 4 years to write, but I finally managed to write it, and it is on arxiv now.
This is the paper: A Simple In-Place Algorithm for In-Shuffle. It is only 3 pages long, and should serve as a solution :-) [ok, I am feeling a bit lazy to write it here too.]
The $\Theta(n\log n)$ version also falls out from the paper.
Please feel free to comment if you have any questions regarding the solution in the paper.
A brief description:
Suppose you are given an array of $2n$ objects
$$[a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_n] $$
You need to reorder the array to be
$$[b_1, a_1, b_2, a_2, \dots, b_k, a_k, \dots, b_n, a_n] $$
Hard version: Do this in-place (preferably $O(1)$ space in WORD RAM model), and O(n) time.
(Medium version: Do it in $O(n\log n)$ time, and in-place).
Solution
This puzzle is surprisingly difficult (the $O(n)$ time, in-place version). It seems that we should easily be able to do it, but most first approaches fail. The in-place constraint is what makes it difficult (otherwise we can just make a new array and copy the elements easily).
This puzzle was given to me when I was at Microsoft, the problem apparently being open at the time (at least within the set of people at Microsoft who came across the puzzle).
I was able to solve it, and I was encouraged (by someone on an online forum) to write a paper on it. It only took me 4 years to write, but I finally managed to write it, and it is on arxiv now.
This is the paper: A Simple In-Place Algorithm for In-Shuffle. It is only 3 pages long, and should serve as a solution :-) [ok, I am feeling a bit lazy to write it here too.]
The $\Theta(n\log n)$ version also falls out from the paper.
Please feel free to comment if you have any questions regarding the solution in the paper.
No comments:
Post a Comment