保持顺序的情况下合并两个列表

Question

我想要将两个列表合并，并输出所有可能的组合，其中维护原始两个列表的顺序。例如：

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

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

在列表“combo”中的每个元素中，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

谢谢！

- Philip C

---

您通常应该期望这样的任务包括: "首先, 合并列表，然后, 对合并结果进行排序。在*(非常罕见)* 的情况下，您肯定需要要求每个单独的组件列表都必须进行排序。 - Mike Robinson

你正在使用的方法依赖于一个排序属性，但是列表并没有被排序。它如何适用于[9,1]和[8,2]？在那里它会失败。我会尽快发布一个解决方案。 - Kenny Ostrom

即使你遍历所有排列，逻辑似乎有点复杂。你可以使用 permutation.index(element) 来检查位置并提取一个排列。 - Stanley Kirdey

这个问题等同于交错两个字符串的所有可能方式，只是输入容器不同（整数列表而不是字符串）。可能是重复的吗？ - das-g

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)的解决方案为开头。

递归的基本情况是当没有列表剩余时。 （我们在进行操作时会删除空列表。）

- user94559

---

哇，那真是太快了！感谢您解释如何做到的。 - Philip C

Answer 2

如果输出作为一个列表而不是连接的数字，那么它会更加清晰一些，但这并不重要。以下是Python3中的简单递归解决方案（但是您可以轻松地将其转换为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) ]

这将返回一个列表的列表：

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

以下是如何将其转换为您想要的输出方式：

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

- Patryk Obara

Answer 3

使用递归生成器的解决方案（需要 Python 3 的 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]])

在每一步中，您可以选择 a 的第一个字符或者选择 b 的第一个字符，并递归地构建列表的其余部分。如果其中一个为空，则没有更多的选择点。

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

更新：基于上述解决方案，以下是可以处理任意数量列表的实现：

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

- fferri

---

我发布了递归解决方案，可能更容易理解，但肯定会更慢。我认为你的解决方案在这里是最好的，所以你没有得到点赞是不公平的 ;) 由你决定！ - Patryk Obara

我也想评论一下这个问题。你的解决方案非常清晰，特别是如果有一点Lisp/Haskell/Prolog的知识，就可以立即理解它。另一方面，我喜欢生成器的一件事情是，如果你只需要前k个项目，使用生成器，你将不会浪费任何CPU功率来生成其他你不会使用的n-k个项目。 - fferri

Answer 4

我对Python不是很了解，但我有一个想法可能会有所帮助。这个想法是使用递归：要将两个列表n和m项连接起来，我们有两种情况：

• 连接n-1个项目和m个项目的两个列表，然后将第n个项目放在末尾。
• 连接n个项目和m-1个项目的两个列表，然后将第m个项目放在末尾。

使用这个递归，您只需要处理最简单的情况：将其中一个为空的两个列表连接起来。它比使用排列快。希望这有所帮助。

- thanhdx

Answer 5

长（一点）的单行代码

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

请参考我对类似问题的回答（如何交错两个字符串的所有可能方式），其中有解释。

- das-g