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

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

谢谢！

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

的解开头

递归的基本情况就是没有列表了。（空列表会随着我们的进行而被删减。）

Answer 2

我对 python 了解不多，但我有一个想法可能会有所帮助。
这个想法是使用递归：
要连接两个列表 n & m 项目，我们有两种情况：

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

使用这个递归，你只需要处理最简单的情况：连接两个列表，其中一个是空的。它会很快然后使用排列。希望对你有帮助。

Answer 3

使用递归生成器的解决方案（yield from ... 需要 Python 3）：

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

Answer 4

长（大概）单行

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

请参阅我对类似问题的回答以获得解释。

Answer 5

如果您的输出是列表的列表而不是串联的数字，那会更清晰一些，但这并不重要。这是 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) ]

这将 return 列表列表：

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

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

Combination of two lists while keeping the order

python

combinations

permutation

itertools