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: 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:
<http://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
    

