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:

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!

score 6 · Accepted Answer · edited May 23 '17 at 12:08

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

Nice insight, are you planning to cook up an implementation? — Jared Goguen, May 11 '16 at 11:55
I've added one, I like this approach better than the recursive one because it's trivial to generalize it. — Jared Goguen, May 11 '16 at 12:13
@SiHa: Thanks, I was just editing into my answer a note about that, and how to fix it. — John Zwinck, May 11 '16 at 12:14
Thanks! this worked nicely. The logic is elegant. You, John.. are the man! — SkyBlue, May 13 '16 at 09:41

score 1 · Answer 2 · answered May 11 '16 at 12:10

A recursive approach with python:

def f( s , l1 , l2 ):
        if( l1 == [] and l2 == [] ):
                print s
                return
        if( l1 != [] ):
                f( s + l1[0] , l1[1:] , l2 )
        if( l2 != [] ):
                f( s + str(l2[0]) , l1 , l2[1:] )

niemmi · Answer 3 · 2016-05-11T13:34:30.163

One option is to use a counter where set bits corresponds to item on a and unset to item on b. For every value in counter check if there's len(a) bits set and generate a permutation:

def ordered_permutations(l1, l2):
    length = len(l1) + len(l2)
    fmt = '{{0:0{0}b}}'.format(length)

    for i in xrange(2 ** length):
        seq = fmt.format(i)

        if seq.count('1') == len(l1):
            iters = [iter(l1), iter(l2)]
            yield [iters[int(c)].next() for c in seq]

Usage:

for p in ordered_permutations(['a','b'], [1,2]):
    print p

Output:

['a', 'b', 1, 2]
['a', 1, 'b', 2]
['a', 1, 2, 'b']
[1, 'a', 'b', 2]
[1, 'a', 2, 'b']
[1, 2, 'a', 'b']

The implementation could be improved by using HAKMEM 175 to generate the next sequence instead of using a counter and checking that right amount of bits are set.

score 0 · Answer 4 · answered May 11 '16 at 12:01

Alternative option is to use recursion.

Pseudocode:

result[] SortedMergePermutations(listA,listB)
{
  result.append([FirstElementOfListA, 
    SortedMergePermutations(listAWithoutFirstElement,listB))]
  result.append([FirstElementOfListB,
    SortedMergePermutations(listA,listBWithoutFirstElement))]
  ])
  return result
}

gboffi · Answer 5 · 2016-05-11T16:33:35.110

I have found a solution that works only for two sequences, but uses itertools.combinations() to find just the possible sequences of positions in which to place (in order...) the elements of the first sequence

from __future__ import print_function

def print_merged(a, b):
    from itertools import combinations, cycle

    l = len(a) + len(b)
    ab = [cycle(a), cycle(b)]
    rng = range(l)
    print([a, b])

    for index in combinations(rng, len(a)):
        li = []
        for i in rng:
            n = 0 if i in index else 1
            li.append(next(ab[n]))
        print(li)

# testing

print_merged([1,2,3], [4,5,6])
print('-'*72)
print_merged([1,2], [4,5,6])
print('-'*72)
print_merged([1,2,3], [5,6])

I vaguely understand that it's possible to deal with a larger number of lists merging the 3rd list with each one of the lists generated from the first and second one, etc, an idea that points in the direction of a recursive implementation but I'm glad to leave such an accomplishment to someone else...

Edit 1

I've removed the counter machinery, as itertools.cycle() objects are exactly what is needed.

Test output

[[1, 2, 3], [4, 5, 6]]
[1, 2, 3, 4, 5, 6]
[1, 2, 4, 3, 5, 6]
[1, 2, 4, 5, 3, 6]
[1, 2, 4, 5, 6, 3]
[1, 4, 2, 3, 5, 6]
[1, 4, 2, 5, 3, 6]
[1, 4, 2, 5, 6, 3]
[1, 4, 5, 2, 3, 6]
[1, 4, 5, 2, 6, 3]
[1, 4, 5, 6, 2, 3]
[4, 1, 2, 3, 5, 6]
[4, 1, 2, 5, 3, 6]
[4, 1, 2, 5, 6, 3]
[4, 1, 5, 2, 3, 6]
[4, 1, 5, 2, 6, 3]
[4, 1, 5, 6, 2, 3]
[4, 5, 1, 2, 3, 6]
[4, 5, 1, 2, 6, 3]
[4, 5, 1, 6, 2, 3]
[4, 5, 6, 1, 2, 3]
------------------------------------------------------------------------
[[1, 2], [4, 5, 6]]
[1, 2, 4, 5, 6]
[1, 4, 2, 5, 6]
[1, 4, 5, 2, 6]
[1, 4, 5, 6, 2]
[4, 1, 2, 5, 6]
[4, 1, 5, 2, 6]
[4, 1, 5, 6, 2]
[4, 5, 1, 2, 6]
[4, 5, 1, 6, 2]
[4, 5, 6, 1, 2]
------------------------------------------------------------------------
[[1, 2, 3], [5, 6]]
[1, 2, 3, 5, 6]
[1, 2, 5, 3, 6]
[1, 2, 5, 6, 3]
[1, 5, 2, 3, 6]
[1, 5, 2, 6, 3]
[1, 5, 6, 2, 3]
[5, 1, 2, 3, 6]
[5, 1, 2, 6, 3]
[5, 1, 6, 2, 3]
[5, 6, 1, 2, 3]

Merging 2 Lists In Multiple Ways - Python

5 Answers5

Edit 1

Test output