Merging 2 Lists In Multiple Ways - Python

Question

I've been experimenting with a number of techniques but I'm sure there's smooth-ish way to get this done.

Suppose I have two lists with the same amount of items in them (4 each):

a = ['a', 'b', 'c', 'd']    
b = [1, 2, 3, 4]

I'd like to merge these lists in all possible ways while retaining order. Example outputs:

a, b, c, d, 1, 2, 3, 4    
1, 2, 3, 4, a, b, c, d    
a, b, 1, 2, c, 3, 4, d

The point is each of the lists must retain its order so an item can not precede another item in the output considering its position in the list. so for example the output can not be:

a, b, **d**, c, 1...   > d precedes c whereas c is before d in the original list
1, **4**, a, b, 3....  > 4 precedes 3 whereas 3 is before 4 in the original list

I guess the idea is to merge the second list into the first list in all possible ways. A fully worked example is this:

a = [a, b]    
b = [1, 2]

desired output:

ab12                                                                      
a1b2                                                                             
a12b                                                                         
1ab2                                                                             
1a2b                                                                          
12ab

How do I go about doing this? Does itertools have a capability to do this in some way? Or is there another way to get this done? Please help!

Answer 1

In the 2x4 case, you want to take all 8 elements without disrupting the ordering within each quad. These examples:

a, b, c, d, 1, 2, 3, 4    
1, 2, 3, 4, a, b, c, d    
a, b, 1, 2, c, 3, 4, d

Can be transformed into sequences of "instructions" which are the list to take from, 0 or 1:

0 0 0 0 1 1 1 1
1 1 1 1 0 0 0 0
0 0 1 1 0 1 1 0

Once you have realized this, you may notice that the sequences we need to generate are all the permutations of four zeros and four ones. Having made this leap, we can use itertools:

itertools.permutations([0,0,0,0,1,1,1,1])

For the 2x4 case, this gives 40320 results, but only 70 unique ones (because itertools.permutations thinks 1,1,1 is different from 1,1,1 if the numbers are reordered). You can get the unique permutations from an answer here: https://stackoverflow.com/a/6285330/4323 or just use set().

---

Putting that all together, here is a complete solution:

import itertools

def combos(*seqs):
    counts = map(len, seqs)
    base = []
    for ii, count in enumerate(counts):
        base.extend([ii]*count)
    for take in set(itertools.permutations(base)):
        result = []
        where = [0] * len(seqs)
        for elem in take:
            result.append(seqs[elem][where[elem]])
            where[elem] += 1
        yield result

You can test it this way (gives 70 results):

a = ['a', 'b', 'c', 'd']
b = [1, 2, 3, 4]

for res in combos(a, b):
    print res