python - python中所有可能的列表合并

Question

我想获得在 python 中合并 2 个(或理想情况下为 n 个)列表的所有可能方法，同时保持每个列表的内部顺序 - 即我想找到一些函数 all_merges ，其行为如下:

a = all_merges([1,2],[3,4]) 

结果:

a = [
[1,2,3,4],
[1,3,2,4],
[1,3,4,2],
[3,1,2,4],
[3,1,4,2],
[3,4,1,2]   ]

(我希望这是全部)

我找不到简单的“pythonic”方法来执行此操作 - 请帮忙!

=====

注意:

我正在考虑这样的事情(写得相对可读):

from itertools import permutations
def all_merges(list1,list2):
    a = [1]*len(list1)
    b = [2]*len(list2)
    indexes = list(set(list(permutations(a+b))))
    lists = [[]]*3
    res = indexes # just for readability, will be overwriting indexes as we go along
    for perm in indexes:
        lists[1] = copy(list1)
        lists[2] = copy(list2)
        merge = perm
        for i in range(0,len(perm)):
            merge[j] = lists[perm[i]].pop(0)
    return res

不过在阶段

list(set(list(permutations(a+b))

如果列表的总长度达到 15，我会从

中得到大量结果

permutations(a+b)

(准确地说是 15 个!)，而我最多只有 15choose7 (= 6435) 个不同的合并。

我意识到这里提供了对该行的替换，作为一个函数:permutations with unique values但现在这变得越来越困惑，我想看看是否有更清晰的解决方案来解决我原来的问题。

Answer 1

每个可能的合并直接对应于 (len(a) + len(b)) choose len(a) 方式之一来选择 len(a) 位置最终列表中 a 的元素:

import itertools
def all_merges(a, b):
    # object guaranteed not to be in either input list
    sentinel = object()
    merged_length = len(a) + len(b)
    for a_positions in itertools.combinations(xrange(merged_length), len(a)):
        merged = [sentinel] * merged_length

        # Place the elements of a in their chosen positions.
        for pos, a_elem in zip(a_positions, a):
            merged[pos] = a_elem

        # Place the elements of b in the positions not taken.
        b_iter = iter(b)
        for pos in xrange(merged_length):
            if merged[pos] is sentinel:
                merged[pos] = next(b_iter)

        yield merged

这可以通过多种方式扩展到更多列表，例如通过使用某种技术(可能是 Algorithm L )遍历所有方式来为列表元素分配位置，或者重复应用 2-way 合并。