python - 两个列表的组合，同时保持顺序

Question

我正在尝试连接两个列表并输出合并列表的所有可能组合，以保持原始两个列表的顺序。例如:

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

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

在列表“组合”中的每个元素中，2 总是在 1 之前，而 9 总是在 8.

到目前为止，我已经使用 itertools 的排列来循环所有可能的排列，但速度不够快。

这是我得到的:

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

谢谢!

Answer 1

试一试:

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

我对这个问题的看法是，您从第一个序列(在本例中为 ab)开始，然后寻找可以插入第二个序列元素的所有可能位置(在在这种情况下，一个 1 然后是一个 2)。

itertools.combinations 调用为您提供了这些组合。在上面的例子中，它遍历位置 (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)。

对于每一组坐标，我们只需将第二个列表中的元素插入到指定的索引处。

更新

这是一个处理任意数量列表的递归解决方案，基于@Đặng Xuân Thành 在其回答中的建议:

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

基本思想是，从 ab 和 12 开始，您知道所有可能的解决方案都将以 b 或 结尾>2。以b结尾的都会以(a, 12)的解开头。以2结尾的都将以(ab, 1)的解决方案开头。

递归的基本情况就是没有列表了。 (空列表会随着我们的进行而被修剪。)