4

Given a list of size 2n -1 elements and the list looks like this:

x1, x2, x3, ....., xn, y1, y2, y3, ....y(n-1)

Convert it to:

x1, y1, x2, y2, x3, y3, ........., y(n-1), xn

I can use two iterators for each of the lists and get the solution in O(n) time complexity and O(n) space complexity. But if my n was very large, is there a way to do this in lesser space complexity?

tanvi
  • 927
  • 5
  • 17
  • 32
  • 1
    you really have to explicitly merge the two lists? you could easily said what is the `k-th` element from the resulting list without really performing the merge. – sve Apr 29 '16 at 07:58
  • http://stackoverflow.com/questions/12338654/move-all-odd-positioned-element-to-left-half-and-even-positioned-to-right-half-i – MBo Apr 29 '16 at 08:04
  • @svs I do have to merge the lists and queue them up for some other program to use. – tanvi Apr 29 '16 at 08:06
  • 2
    For the more general problem of efficiently applying an arbitrary permutation in place, see https://cstheory.stackexchange.com/questions/6711/complexity-of-applying-a-permutation-in-place – augurar Apr 29 '16 at 08:26
  • @MBo I think that's the inverse of this problem. – augurar Apr 29 '16 at 08:33
  • Possible duplicate: https://stackoverflow.com/questions/15996288/in-place-interleaving-of-the-two-halves-of-a-string – augurar Apr 29 '16 at 08:36
  • 1
    Also: https://cs.stackexchange.com/questions/332/, https://cstheory.stackexchange.com/questions/13943 – augurar Apr 29 '16 at 08:38
  • @MBo I don't think I can use the Cycle Leader Iteration Algorithm here. – tanvi Apr 29 '16 at 08:59
  • 1
    @augurar Yes, but the same approach - transpose 2xN matrix inplace – MBo Apr 29 '16 at 09:13
  • @tanvi This is one specific method of transposition. Of course, you may use another. – MBo Apr 29 '16 at 09:15

2 Answers2

1

It feels like this can be done with O(1) space and O(n) time but the algorithm is far from trivial. Basically take an element that is out of place, say x2, look where it needs to be in the final arrangement take out the element that is there (i.e. x3) and put in x2. Now look where x3 needs to go and so on.

When the cycle is closed, take the next element that is out of place (if there is any).

Lets do an example:

x1 x2 x3 y1 y2      x2 is out of place so take it into temp storage
x1 -- x3 y1 y2      temp: x2       needs to go where x3 currently is
x1 -- x2 y1 y2      temp: x3       needs to go where y2 currently is
x1 -- x2 y1 x3      temp: y2       needs to go where y1 currently is
x1 -- x2 y2 x3      temp: y1       needs to go into the empty slot
x1 y1 x2 y2 x3      all elements in place -> finished

If the array indices start at 0, the final position of the element at k is given by

2k            if k < n
2(k-n) + 1    if k >= n

The difficulty is to find out an element of a cycle that is not yet handled. For example if n = 4 there are 3 cycles:

0 -> 0
1 -> 2 -> 4 -> 1
3 -> 6 -> 5 -> 3

I do not have an easy solution for that at the moment.

If you have one bit of storage available per array element it is trivial but then we are back to O(n) storage.

Henry
  • 42,982
  • 7
  • 68
  • 84
-1

In Python:

lst = 'x1 x2 x3 x4 x5 y1 y2 y3 y4 y5'.split()

lst
Out[9]: ['x1', 'x2', 'x3', 'x4', 'x5', 'y1', 'y2', 'y3', 'y4', 'y5']

out = sum((list(xy) for xy in zip(lst[:len(lst)//2], lst[len(lst)//2:])), [])

out
Out[11]: ['x1', 'y1', 'x2', 'y2', 'x3', 'y3', 'x4', 'y4', 'x5', 'y5']
Paddy3118
  • 4,704
  • 27
  • 38