All possible merges of lists in python

Question

I would like to get all the possible ways to merge 2 (or ideally n) lists in python, while maintaining each list's internal order - i.e. I would like to find some function all_merges that would behave like this:

a = all_merges([1,2],[3,4])

results in:

a = [
[1,2,3,4],
[1,3,2,4],
[1,3,4,2],
[3,1,2,4],
[3,1,4,2],
[3,4,1,2]   ]

(I hope this is all of them)

I cannot find simple, 'pythonic' way to do this - please help!

=====

Note:

I am considering something like this (written to be relatively readable):

from itertools import permutations
def all_merges(list1,list2):
    a = [1]*len(list1)
    b = [2]*len(list2)
    indexes = list(set(list(permutations(a+b))))
    lists = [[]]*3
    res = indexes # just for readability, will be overwriting indexes as we go along
    for perm in indexes:
        lists[1] = copy(list1)
        lists[2] = copy(list2)
        merge = perm
        for i in range(0,len(perm)):
            merge[j] = lists[perm[i]].pop(0)
    return res

however at the stage

list(set(list(permutations(a+b))

if the combined length of the lists is so much as 15 I get a huge amount of results from

permutations(a+b)

(15!, to be precise), whereas at most I will only really have 15choose7 (= 6435) different merges.

I realise a replacement to that line is provided here, as a function: permutations with unique values but by now this is getting messy and I want to see if there is a cleaner solution to my original problem.

user2357112 · Accepted Answer · 2015-11-19T18:43:39.193

Each possible merge corresponds directly to one of (len(a) + len(b)) choose len(a) ways to pick len(a) positions for the elements of a in the final list:

import itertools
def all_merges(a, b):
    # object guaranteed not to be in either input list
    sentinel = object()
    merged_length = len(a) + len(b)
    for a_positions in itertools.combinations(xrange(merged_length), len(a)):
        merged = [sentinel] * merged_length

        # Place the elements of a in their chosen positions.
        for pos, a_elem in zip(a_positions, a):
            merged[pos] = a_elem

        # Place the elements of b in the positions not taken.
        b_iter = iter(b)
        for pos in xrange(merged_length):
            if merged[pos] is sentinel:
                merged[pos] = next(b_iter)

        yield merged

This can be extended to more lists in several ways, such as by using some technique (perhaps Algorithm L) to go through all ways to assign positions to list elements, or by applying the 2-way merge repeatedly.

This is great, thank you! For posterity, I'll note that I had to change xrange to range, and I got the desired result using list(all_merges(a,b)) — gail, Nov 19 '15 at 18:48

All possible merges of lists in python

1 Answers1