Philip Chia - 1 year ago 56

Python 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",

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 Source

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