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.)