Combination of two lists while keeping the order

Question

I'm trying to join two lists and output all possible combinations of the merged list that maintains the ordering of the original two lists. For example:

list_1 = [9,8]
list_2 = [2,1]

#output
combo= [9821,9281,2981,2918,2198,9218]

where in each element in the list "combo", 2 always comes before 1 and 9 always comes before 8.

so far I've used permutations from itertools to do loop all possible permutations, but it is not fast enough.

Here's what I got:

from itertools import permutations
seq = [5, 9, 8, 2, 1]
plist = []
root = seq[0]
left = filter(lambda x: x > root, seq)
right =  filter(lambda x: x < root, seq)  

for pseq in permutations(seq[1:]):
    pseq = (root,) + pseq
    if list(filter(lambda x: x > root, pseq)) == left and list(filter(lambda x: x < root, pseq)) == right:
        plist.append(pseq)
print plist

Thanks!

Answer 1

Give this a try:

import itertools

lst1 = ['a', 'b']
lst2 = [1, 2]

for locations in itertools.combinations(range(len(lst1) + len(lst2)), len(lst2)):
    result = lst1[:]
    for location, element in zip(locations, lst2):
        result.insert(location, element)
    print(''.join(map(str, result)))

# Output:
# 12ab
# 1a2b
# 1ab2
# a12b
# a1b2
# ab12

The way I think of the problem, you start with the first sequence (ab in this case), and then look for all the possible places you can insert the elements of the second sequence (in this case, a 1 and then a 2).

The itertools.combinations call gives you those combinations. In the above example, it iterates through the positions (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3).

For each of those sets of coordinates, we just insert the elements from the second list at the specified indexes.

UPDATE

Here's a recursive solution that handles any number of lists, based on @Đặng Xuân Thành's suggestion in his answer:

import itertools

def in_order_combinations(*lists):
    lists = list(filter(len, lists))

    if len(lists) == 0:
        yield []

    for lst in lists:
        element = lst.pop()
        for combination in in_order_combinations(*lists):
            yield combination + [element]
        lst.append(element)

for combo in in_order_combinations(['a', 'b'], [1, 2]):
    print(''.join(map(str, combo)))

The basic idea is that, starting with ab and 12, you know that all possible solutions will either end with b or 2. The ones that end with b will all start with a solution for (a, 12). The ones that end with 2 will all start with a solution for (ab, 1).

The base case for the recursion is simply when there are no lists left. (Empty lists are pruned as we go.)

Answer 2

It would be a bit cleaner if your output was a list of lists instead of concatenated digits, but it doesn't matter. Here's a simple recursive solution in python3 (but you can trivially convert it to python2).

def combine(xs, ys):
    if xs == []: return [ys]
    if ys == []: return [xs]
    x, *xs_tail = xs
    y, *ys_tail = ys
    return [ [x] + l for l in combine(xs_tail, ys) ] + \
           [ [y] + l for l in combine(ys_tail, xs) ]

This will return a list of lists:

>>> combine([9, 8], [2, 1])
[[9, 8, 2, 1], [9, 2, 1, 8], [9, 2, 8, 1], [2, 1, 9, 8], [2, 9, 8, 1], [2, 9, 1, 8]]

Here's how to convert it to your desired output:

def list_to_int(digits):
    return int(''.join(map(str, digits)))

def combine_flat(xs, ys):
    return [list_to_int(l) for l in combine(xs, ys)]

Answer 3

A solution using a recursive generator (requires Python 3 for yield from ...):

def f(a,b,p=[]):
    if len(a)==0 or len(b)==0:
        yield p+a+b
    else:
        yield from f(a[1:],b,p+[a[0]])
        yield from f(a,b[1:],p+[b[0]])

at each step, you can pick the first character of a or the first character of b, and recursively build the rest of the list(s). if one of the two becomes empty, there are no more choice points.

>>> list(f([9,8],[2,1]))
[[9, 8, 2, 1], [9, 2, 8, 1], [9, 2, 1, 8], [2, 9, 8, 1], [2, 9, 1, 8], [2, 1, 9, 8]]

Update: starting from the above solution, here's an implementation that handles any number of lists:

def f(*args,p=[]):
    if any(len(arg)==0 for arg in args):
        yield p+[el for arg in args for el in arg]
    else:
        for i,arg in enumerate(args):
            args1=list(args)
            args1[i]=arg[1:]
            yield from f(*args1,p=p+[arg[0]])

Answer 4

I don't know more about python but I have an idea may help.
The idea is using the recursive:
To join two lists n & m items, we have two cases:

• Join two lists n-1 & m items, then put the n-th items at the end.
• Join two lists n & m-1 items, then put the m-th items at the end.

Use this recursive, you just need to handle the simplest case: join two lists with one of them is empty. It will fast then using permutation. Hope it helps.

Answer 5

Long(ish) one-liner

from itertools import *
from copy import deepcopy

list({''.join(str(l.pop(0)) for l in deepcopy(p)) for p in permutations(chain(repeat(list_1, len(list_1)), repeat(list_2, len(list_2))))})

See my answer to the similar problem All possible ways to interleave two strings for an explanation.