6

Given two lists, I want to merge them so that all elements from the first list are even-indexed (preserving their order) and all elements from second list are odd-indexed (also preserving their order). Example below:

x = [0,1,2]
y = [3,4]

result = [0,3,1,4,2]

I can do it using for loop. But I guess there could be a fancy pythonic way of doing this (using a less-known function or something like that). Is there any better solution that writing a for-loop?

edit: I was thinking about list comprehensions, but didn't come up with any solution so far.

ducin
  • 25,621
  • 41
  • 157
  • 256
  • What do you want done for `x=[0,1,2,3,4,5,6]` but `y=[20,21]`, or the other way around? (I.e., what if one list is far longer or shorter than the other?) – torek Aug 04 '13 at 10:18
  • assume the easier scenario: len(x) == len(y) OR len(x) == len(y) + 1, so don't worry about that. It's gonna be a sequence of moves for a game. – ducin Aug 04 '13 at 10:20
  • In that case, go with `roundrobin` as below, or a simplified version. – torek Aug 04 '13 at 10:21
  • @nio why did you remove your answer? I liked it the most so far (the shortest and the simplest) – ducin Aug 04 '13 at 10:21
  • @torek, the approach suggested in the answer below works if the lists are longer or shorter... – Saullo G. P. Castro Aug 04 '13 at 10:39
  • @SaulloCastro: "works" only if that's what's desired. For instance, if one is *supposed* to stop as soon as *either* list runs out, both our answers would be wrong. That's why I asked "what if...". – torek Aug 04 '13 at 10:43
  • @torek but `insert()` assumes the last index in case you pass a higher one, avoiding the IndexError – Saullo G. P. Castro Aug 04 '13 at 10:44

7 Answers7

8

Here's something you can use. (Use list(izip_longest(...)) for Py2x)

>>> from itertools import chain
>>> from itertools import zip_longest
>>> list(filter(lambda x: x != '', chain.from_iterable(zip_longest(x, y, fillvalue = ''))))
[0, 3, 1, 4, 2]

This works for arbitrary length lists like follows -

>>> x = [0, 1, 2, 3, 4]
>>> y = [5, 6]
>>> list(filter(lambda x: x != '', chain.from_iterable(zip_longest(x, y, fillvalue = ''))))
[0, 5, 1, 6, 2, 3, 4]

Explanation on it's working -

  1. zip_longest(...) with a fill value zips the lists and fills in the given fill value for iterables of unequal length. So, for your original example, it evaluates to something like [(0, 3), (1, 4), (2, '')]
  2. We need to flatten the result because this method gives us a list of tuples. For that we use chain.from_iterable(...) giving us something like [0, 3, 1, 4, 2, ''].
  3. We now use filter(...) to remove all occurences of '' and we get the required answer.
Sukrit Kalra
  • 33,167
  • 7
  • 69
  • 71
7

You can simply do:

for i,v in enumerate(y):
    x.insert(2*i+1,v)

this takes the advantage that insert will use the last index when it is overpassed.

One example:

x = [0,1,2,3,4,5]
y = [100, 11,22,33,44,55,66,77]
print x
# [0, 100, 1, 11, 2, 22, 3, 33, 4, 44, 5, 55, 66, 77]
Saullo G. P. Castro
  • 56,802
  • 26
  • 179
  • 234
  • 2
    I like this one because of its simplicity - only thing to fix is not to modify x. `import copy`/`res = copy.copy(x)`/`for i,v in enumerate(y):`/`res.insert(2*i+1,v)` – ducin Aug 04 '13 at 10:32
  • 3
    @tkoomzaaskz `list.insert` is an O(N) operation. – Ashwini Chaudhary Aug 04 '13 at 10:34
  • @AshwiniChaudhary you mean the complexity? So what? (sorry if I didn't understand your point) – ducin Aug 04 '13 at 10:43
  • @tkoomzaaskz yes complexity, for inserting each item into `x` it is going to perform an `O(N)` step. so, overall complexity of this solution is `O(len(y) * len(x))`, while other solutions are just `O(len(x) + len(y))`. For large lists this is going to be very slow. – Ashwini Chaudhary Aug 04 '13 at 10:51
  • 2
    @tkoomzaaskz : Just some `timeit` results. (Setup - Two lists, one of length 100, one of 50, iterations = 5000, **Py2x**) Saullo's solution - `44.59869242355262`, Ashwini's solution - `0.36575645629210385`, My Solution - `0.5685753073638011`. Nio's Solution - `0.21236540710697227`. – Sukrit Kalra Aug 04 '13 at 11:01
6

Use the roundrobin recipe from itertools:

from itertools import cycle, islice
def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    # Recipe credited to George Sakkis
    pending = len(iterables)
    nexts = cycle(iter(it).next for it in iterables)
    while pending:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            pending -= 1
            nexts = cycle(islice(nexts, pending))
>>> list(roundrobin(x,y))
[0, 3, 1, 4, 2]
Ashwini Chaudhary
  • 244,495
  • 58
  • 464
  • 504
5

Try this:

x = [0,1,2,10,11]
y = [3,4]

n =  2*max([len(x),len(y)])
res = n *[None]
res[:2*len(x):2] = x
res[1:2*len(y):2] = y
res = [x for x in res if x!=None]
print res

It should work for unevenly long lists.

nio
  • 5,141
  • 2
  • 24
  • 35
5

If you have same length lists, you can use this:

result = [ item for tup in zip(x,y) for item in tup ]
Sepero
  • 4,489
  • 1
  • 28
  • 23
2

This is simple enough although not nearly as flexible as roundrobin:

def paired(it1, it2):
    it2 = iter(it2)
    for item in it1:
        yield item
        yield next(it2)

tested in 2.7.5:

>>> x = [0, 1, 2]
>>> y = [3, 4]
>>> print list(paired(x, y))
[0, 3, 1, 4, 2]

Note that it stops as soon as the list y runs out (because next(it2) raises StopIteration).

torek
  • 448,244
  • 59
  • 642
  • 775
  • yep, but - as I wrote in the question - I can do it using just a for-loop. I was thinking about something syntax-based (like list slicing or list comprehensions). Anyway, thanks – ducin Aug 04 '13 at 10:29
  • This will miss some items : `paired(y,x)`. – Ashwini Chaudhary Aug 04 '13 at 10:32
  • @AshwiniChaudhary: that's why I asked above about what to do when one list is longer than another. – torek Aug 04 '13 at 10:33
2

It can be done with slicing. Do count and slice in terminal:

>>> list1=['Apple','Mango','Orange']
>>> list2=['One','Two','Three']
>>> list = [None]*(len(list1)+len(list2))
>>> list[::2] = list1
>>> list[1::2] = list2
>>> list

Output:

 ['Apple', 'One', 'Mango', 'Two', 'Orange', 'Three']
Opal
  • 81,889
  • 28
  • 189
  • 210