以多种方式合并两个列表 - Python

Question

我已经尝试了许多技术，但我相信有一种比较顺畅的方法可以完成这个任务。

假设我有两个列表，它们中每个列表都有相同数量的项目（每个列表各有4个）：

a = ['a', 'b', 'c', 'd']    
b = [1, 2, 3, 4]

我想要将这些列表以所有可能的方式合并，并保留顺序。以下是示例输出：

a, b, c, d, 1, 2, 3, 4    
1, 2, 3, 4, a, b, c, d    
a, b, 1, 2, c, 3, 4, d

重点是每个列表都必须保持其顺序，因此一个项目在输出中不能在列表中的位置考虑时先于另一个项目。因此，例如输出不能为：

a, b, **d**, c, 1...   > d precedes c whereas c is before d in the original list
1, **4**, a, b, 3....  > 4 precedes 3 whereas 3 is before 4 in the original list

我想这个想法是将第二个列表以所有可能的方式合并到第一个列表中。一个完整的示例是：

a = [a, b]    
b = [1, 2]

期望的输出：

ab12                                                                      
a1b2                                                                             
a12b                                                                         
1ab2                                                                             
1a2b                                                                          
12ab

我应该如何进行这个操作？itertools有没有相应的功能可以实现？或者还有其他方法可以完成此操作吗？请帮忙！

- SkyBlue

Answer 1

在2x4的情况下，您希望获取所有8个元素，而不会破坏每个四元组内部的顺序。以下是示例：

a, b, c, d, 1, 2, 3, 4    
1, 2, 3, 4, a, b, c, d    
a, b, 1, 2, c, 3, 4, d

可以将其转换为“指令”序列，这是要从中获取的列表，0或1：

0 0 0 0 1 1 1 1
1 1 1 1 0 0 0 0
0 0 1 1 0 1 1 0

一旦你意识到这一点，你可能会注意到我们需要生成的序列都是四个零和四个一的排列组合。有了这个认识，我们可以使用 itertools：

itertools.permutations([0,0,0,0,1,1,1,1])

对于2x4的情况，这将给出40320个结果，但只有70个唯一的结果（因为itertools.permutations认为1,1,1与1,1,1不同，如果重新排序数字）。您可以在此处获取唯一的排列：https://dev59.com/lW015IYBdhLWcg3w_Aug#6285330或仅使用set()。

将所有内容放在一起，这里是完整的解决方案：

import itertools

def combos(*seqs):
    counts = map(len, seqs)
    base = []
    for ii, count in enumerate(counts):
        base.extend([ii]*count)
    for take in set(itertools.permutations(base)):
        result = []
        where = [0] * len(seqs)
        for elem in take:
            result.append(seqs[elem][where[elem]])
            where[elem] += 1
        yield result

您可以通过以下方式进行测试（会返回70条结果）：

a = ['a', 'b', 'c', 'd']
b = [1, 2, 3, 4]

for res in combos(a, b):
    print res

- John Zwinck

---

很好的见解，你打算开始实现了吗？ - Jared Goguen

我已经添加了一个，我喜欢这种方法比递归更好，因为它很容易推广。 - Jared Goguen

@SiHa：谢谢，我刚刚在我的回答中加入了一条关于此的注释，并说明如何修复它。 - John Zwinck

谢谢！这个很好用。逻辑很优雅。你，约翰..太棒了！ - SkyBlue

Answer 2

一种使用Python的递归方法：

def f( s , l1 , l2 ):
        if( l1 == [] and l2 == [] ):
                print s
                return
        if( l1 != [] ):
                f( s + l1[0] , l1[1:] , l2 )
        if( l2 != [] ):
                f( s + str(l2[0]) , l1 , l2[1:] )

- Esref

Answer 3

一种选择是使用计数器，其中设置的位对应于a上的项目，未设置的位对应于b上的项目。对于计数器中的每个值，检查是否设置了len(a)位，并生成排列：

def ordered_permutations(l1, l2):
    length = len(l1) + len(l2)
    fmt = '{{0:0{0}b}}'.format(length)

    for i in xrange(2 ** length):
        seq = fmt.format(i)

        if seq.count('1') == len(l1):
            iters = [iter(l1), iter(l2)]
            yield [iters[int(c)].next() for c in seq]

使用方法：

for p in ordered_permutations(['a','b'], [1,2]):
    print p

输出：

['a', 'b', 1, 2]
['a', 1, 'b', 2]
['a', 1, 2, 'b']
[1, 'a', 'b', 2]
[1, 'a', 2, 'b']
[1, 2, 'a', 'b']

该实现可以通过使用HAKMEM 175生成下一个序列来改进，而不是使用计数器并检查正确数量的位是否设置。

- niemmi

Answer 4

另一个选择是使用递归。

伪代码：

result[] SortedMergePermutations(listA,listB)
{
  result.append([FirstElementOfListA, 
    SortedMergePermutations(listAWithoutFirstElement,listB))]
  result.append([FirstElementOfListB,
    SortedMergePermutations(listA,listBWithoutFirstElement))]
  ])
  return result
}

- user5226582

Answer 5

我已经找到一个解决方案，它只适用于两个序列，但使用 itertools.combinations() 来查找可以放置第一个序列元素的位置序列(顺序...)的可能组合

from __future__ import print_function

def print_merged(a, b):
    from itertools import combinations, cycle

    l = len(a) + len(b)
    ab = [cycle(a), cycle(b)]
    rng = range(l)
    print([a, b])

    for index in combinations(rng, len(a)):
        li = []
        for i in rng:
            n = 0 if i in index else 1
            li.append(next(ab[n]))
        print(li)

# testing

print_merged([1,2,3], [4,5,6])
print('-'*72)
print_merged([1,2], [4,5,6])
print('-'*72)
print_merged([1,2,3], [5,6])

我模糊地了解到，可以通过将第三个列表与从第一个和第二个列表生成的每个列表合并来处理更多的列表，这个想法指向了递归实现的方向，但我很高兴把这样的成就留给别人...

编辑1

我已经删除了计数器机制，因为itertools.cycle()对象正是所需。

测试输出

[[1, 2, 3], [4, 5, 6]]
[1, 2, 3, 4, 5, 6]
[1, 2, 4, 3, 5, 6]
[1, 2, 4, 5, 3, 6]
[1, 2, 4, 5, 6, 3]
[1, 4, 2, 3, 5, 6]
[1, 4, 2, 5, 3, 6]
[1, 4, 2, 5, 6, 3]
[1, 4, 5, 2, 3, 6]
[1, 4, 5, 2, 6, 3]
[1, 4, 5, 6, 2, 3]
[4, 1, 2, 3, 5, 6]
[4, 1, 2, 5, 3, 6]
[4, 1, 2, 5, 6, 3]
[4, 1, 5, 2, 3, 6]
[4, 1, 5, 2, 6, 3]
[4, 1, 5, 6, 2, 3]
[4, 5, 1, 2, 3, 6]
[4, 5, 1, 2, 6, 3]
[4, 5, 1, 6, 2, 3]
[4, 5, 6, 1, 2, 3]
------------------------------------------------------------------------
[[1, 2], [4, 5, 6]]
[1, 2, 4, 5, 6]
[1, 4, 2, 5, 6]
[1, 4, 5, 2, 6]
[1, 4, 5, 6, 2]
[4, 1, 2, 5, 6]
[4, 1, 5, 2, 6]
[4, 1, 5, 6, 2]
[4, 5, 1, 2, 6]
[4, 5, 1, 6, 2]
[4, 5, 6, 1, 2]
------------------------------------------------------------------------
[[1, 2, 3], [5, 6]]
[1, 2, 3, 5, 6]
[1, 2, 5, 3, 6]
[1, 2, 5, 6, 3]
[1, 5, 2, 3, 6]
[1, 5, 2, 6, 3]
[1, 5, 6, 2, 3]
[5, 1, 2, 3, 6]
[5, 1, 2, 6, 3]
[5, 1, 6, 2, 3]
[5, 6, 1, 2, 3]

- gboffi