10

Given an array 

[a1 a2 a3 ... an b1 b2 b3 ... bn c1 c2 c3 ...cn]

without using extra memory how do you reorder into an array

[a1 b1 c1 a2 b2 c2 a3 b3 c3 ... an bn cn]
Improve this question
4
  • a1 can be some element in the array...not necessary in increasing order. Commented Apr 5, 2011 at 19:26
  • 1
    I think it's misleading to call this "merging". Merging implies taking two smaller arrays and producing a composite array. I'd call this "reordering", personally. By extra memory, do you mean no additional memory at all, absolutely? Or do you mean no extra memory as "n" increases? Commented Apr 5, 2011 at 19:29
  • 1
    I gather you mean by only using a constant amount of extra memory. It will be pretty hard to do this without at least 1 temp variable :) Commented Apr 5, 2011 at 19:33
  • 1
    @Larry: at least for a square matrix, you can use the XOR swap trick and avoid a temporary ;-P. Commented Apr 6, 2011 at 9:56

4 Answers 4

Reset to default
11

Your question can also be rephrased as 'How to do an in-place matrix transposition?'. To see why, imagine adding a newline after each subsequence in both of your arrays. This will turn the first array into an NxM matrix, and the second array into an MxN matrix.

Still, it is not trivial for non-square matrices. Please refer to the Wikipedia page on In-place matrix transposition for a comprehensive description of the problem and its solutions.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I checked out the wiki page, but failed to find an algorithm yielding O(1) space. Can you please tell me which one gives O(1) space?
6

Assuming you mean O(1) memory (or depending on the model O(log n)) rather than no extra memory, a linear time in-place algorithm exists.

This paper: http://arxiv.org/abs/0805.1598 has an algorithm for the case when you have

a1 ... an b1 ... bn and want to convert to

b1 a1 b2 a2 ... bn an.

The paper also mentions that you can generalize this to other k-way shuffles. In your case, k = 3.

The algorithm in the paper will give the following:

Start with a1 a2 ... an b1 b2 ... bn c1 c2 ... cn and convert to

c1 b1 a1 c2 b2 a2 ... cn bn an

Another pass through this, and you can easily get a1 b1 c2 a2 b2 c2 ... an bn cn.

Now to generalize the algorithm in the paper, we need to pick a prime p, such that k is a primitive root of p^2.

For k = 3, p = 5 will do.

Now to apply the algorithm, first you need to find the largest m < n such 3m+1 is a power of 5.

Note: this will only happen when 3m+1 is an even power of 5. Thus you can actually work with powers of 25 when trying to find the m. (5^odd - 1 is not divisible by 3).

Once you find m,

You shuffle the array to be

[a1 a2 ... am b1 b2 ... bm c1 c2 ... cm] [a(m+1) ... an b(m+1) ... bn c(m+1) ... cn]

and then use the follow the cycle method(refer the paper) for the first 3m elements, using the powers of 5 (including 1 = 5^0) as the starting points of the different cycles) and do a tail recursion for the rest.

Now to convert a1 a2 ... an b1 b2 ... bn c1 c2 ... cn

to

[a1 a2 ... am b1 b2 ... bm c1 c2 ... cm] [a(m+1) ... an b(m+1) ... bn c(m+1) ... cn]

you first do a cyclic shift to get

a1 a2 ... am [b1 b2 bm a(m+1) .. an] b(m+1) .. bn c1 c2 ... cn

(the elements in the square brackets are the ones that were shifted)

Then do a cyclic shift to get

a1 a2 ... am b1 b2 bm a(m+1) .. an [c1 c2 ..cm b(m+1) .. bn ] c(m+1) ... cn

And then a final shift to

a1 a2 ... am b1 b2 bm [c1 c2 ..cm a(m+1) .. an ] b(m+1) .. bn c(m+1) ... cn

Note that cyclic shift can be done in O(n) time and O(1) space.

So whole algorithm is O(n) time and O(1) space.

Improve this answer

7 Comments

If someone wants me to elaborate on this further, please let me know.
I do. I see that the paper also uses a CycleSort, but it describes breaking the inputs into blocks whose sizes allow calculating in advance which cycles exist. This avoids the extra space or time complexity added when using bits or backtracking as I proposed. But I'm a little confused about what those ideal block sizes are. 5^k-1 gives 3m = 4,24,124,... Do you round up or down? It does appear that for m=1 or m=2 there is only one cycle starting at index 1, and for m=8 there are 2 cycles at 1 and 5. What about when k is 3? Should m be 41 or 42? Do either one have only cycles at 1,5,25?
@Ashelly: I have elaborated a bit.
@Moron: so, by this logic, the m's allowed are 8,208,5208,... What happens when your n is 15 (45 elements)? After re-ordering, the first 3*8 block can be processed by following the cycles starting at 1 and 5. But now you are left with a block of 3*7 elements.
@Ashelly: Yes, I believe so. If you don't like it, you could pick other primes too. I believe picking powers of 7 also works. As to your question, about the remaining, it is a constant number of elements (less than 3*8), which can be done easily in O(1) space. Think of it as the bases cases in an induction step...
|
2

You can calculate each item's target position based on its index. 

groupSize = N/3
group = i/groupSize
rank = i - group * groupSize
dest = rank * 3 + group

You can use this calculation with a cycle sort to put each element in its proper place in linear time. The only issue is tracking which items are already in place. All you need for that is N bits. With certain types of data, you can "steal" a bit from the data item itself. For instance you can use the high bit of ASCII data, or the low byte of word-aligned pointers.

Alternately, you can do it without any extra bits at the expense going to polynomial time. Reverse the calculation, so you can find the original source index of each item in the final array.

source = i % groupSize + groupSize * (i/groupSize) ;  //integer division

Now walk forward through the array, swapping every item with the one from the source. The trick is that any time the source index is less than the current position (meaning it has already been swapped out), you need to follow the trail until you find its current location

getSource(i):
   s = i % groupSize + groupSize * (i/groupSize)
   while (s<i)
      s = s % groupSize + groupSize * (s/groupSize)
   return s

shuffle:
for i in (0..N-1) 
   swap(a[i],a[getSource(i)]
Improve this answer

Comments

0

You can do this for certain - just take cards ace, 2, ... 5 in 3 suits and put them in order.

First you take out the a2 card and put it aside. Then you move the b1 to the a2 position and shift all the cards up

Then you put back the a2 card and put in the shifted out position.

Then you take out the a3 card and puti taside Move the c1 to the a3 position and shift all the cards up.

Then put back the a3 card in the emptied position.

repeat until done.

The actual calculation of the indices is tricky but I believe a previous poster has done this.

Improve this answer

1 Comment

I think this is on the right track, especially the idea of filling in from the bottom. But once you start shifting items it becomes awfully tricky, if not impossible, to keep track of where they came from unless you use extra storage. See my answer for a way to overcome that problem by swapping instead of shifting.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.