交错不同的长度列表,删除重复项并保留顺序

Question

我有两个清单,让我们说:

keys1 = ['A', 'B', 'C', 'D', 'E',           'H', 'I']
keys2 = ['A', 'B',           'E', 'F', 'G', 'H',      'J', 'K']

如何创建没有重复项的合并列表,以保留两个列表的顺序,将缺少的元素插入它们所属的位置？像这样:

merged = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']

请注意,可以将元素与相等进行比较,但不进行排序(它们是复杂的字符串).这些元素不能通过比较来排序,但它们的顺序基于它们在原始列表中的出现次数.

如果出现矛盾(两个输入列表中的顺序不同),则包含所有元素的任何输出都是有效的.当然,如果解决方案在保留大部分订单时显示"常识",则可获得奖励积分.

再次(正如一些评论仍然争论它),列表通常不会在共同元素的顺序上相互矛盾.如果他们这样做,算法需要优雅地处理该错误.

我开始使用.next()遍历列表的版本,以推进包含不匹配元素的列表,但.next()只是不知道何时停止.

merged = []
L = iter(keys1)
H = iter(keys2)
l = L.next()
h = H.next()

for i in range(max(len(keys1, keys2))):
  if l == h:
    if l not in merged:
      merged.append(l)
    l = L.next()
    h = H.next()

  elif l not in keys2:
    if l not in merged:
      merged.append(l)
    l = L.next()

  elif h not in keys1:
    if h not in merged:
      merged.append(h)
    h = H.next()

  else: # just in case the input is badly ordered
    if l not in merged:
      merged.append(l)
    l = L.next()
    if h not in merged:
      merged.append(h)
    h = H.next()   

print merged

这显然不起作用,因为.next()将导致最短列表的异常.现在我可以更新我的代码以在每次调用.next()时捕获该异常.但是代码已经完全不同于pythonic,这显然会破坏泡沫.

有没有人更好地了解如何迭代这些列表来组合元素？

如果我可以一次性完成三个列表的奖励积分.

Answer 1

您需要的基本上是任何合并实用程序所做的:它尝试合并两个序列,同时保持每个序列的相对顺序.您可以使用Python的difflib模块来区分两个序列,并合并它们:

from difflib import SequenceMatcher

def merge_sequences(seq1,seq2):
    sm=SequenceMatcher(a=seq1,b=seq2)
    res = []
    for (op, start1, end1, start2, end2) in sm.get_opcodes():
        if op == 'equal' or op=='delete':
            #This range appears in both sequences, or only in the first one.
            res += seq1[start1:end1]
        elif op == 'insert':
            #This range appears in only the second sequence.
            res += seq2[start2:end2]
        elif op == 'replace':
            #There are different ranges in each sequence - add both.
            res += seq1[start1:end1]
            res += seq2[start2:end2]
    return res

例:

>>> keys1 = ['A', 'B', 'C', 'D', 'E',           'H', 'I']
>>> keys2 = ['A', 'B',           'E', 'F', 'G', 'H',      'J', 'K']
>>> merge_sequences(keys1, keys2)
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K']

请注意,您期望的答案不一定是唯一可能的答案.例如,如果我们在这里改变序列的顺序,我们得到另一个同样有效的答案:

>>> merge_sequences(keys2, keys1)
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K', 'I']