将两个字符串列表合并为一个列表

Question

给定两个包含重复项的字符串列表，除了每个列表中的一个元素外，如何将两个列表合并为一个单一列表，其中按列表顺序包含每个值的一个副本？

例如，在Python中给定以下两个列表：

a = ['Second', 'Third', 'Fourth']
b = ['First', 'Second', 'Third']

或者

a = ['First', 'Third', 'Fourth']
b = ['First', 'Second', 'Third']

你如何将这两个列表合并成一个像这样的列表：

result = ['First', 'Second', 'Third', 'Fourth']

请注意，字符串的确切值不能保证有助于对元素进行排序。 我知道可能存在一些情况，没有明确的方法将列表锁定到特定顺序，并且可能需要为这些情况制定特殊情况，但对于一般情况，我更愿意有一个可遵循的过程。例如：

a = ['First', 'Third', 'Fourth']
b = ['First', 'Second', 'Fourth']

这里有两个列表，分别包含'Third'和'Second'，但它们之间没有任何项目来提供指导，因此可以任意排序。

编辑：我应该更详细地解释一下字符串，因为我看到许多人假设我可以仅对两个列表进行简单合并并排序，但这不会起作用。

我正在获取故事标题，对于每个故事，只列出其他部分而不是链接的故事本身。因此，通过获取两个列表（或可能更多，我不确定），我可以得出完整的部分列表以将它们放在正确的顺序中。

- Raceimaztion

---

只需将这两个列表相加即可。 - James Mills

此外，加一分，为您尝试解决的实际问题添加描述。 - Gustav Bertram

我仍在思考可能的解决方案，但我不确定这个问题是否可以在一般情况下解决。例如['First', 'Second', 'Fourth']和['First', 'Third', 'Fourth']这样的情况怎么办？如果没有其他正确顺序的信息，程序无法确定'Second'或'Third'哪个先出现。 - jpmc26

@jpmc26 如果在列表中取出的分期之间至少有一个分期，那么这些列表就足够了。检查列表是否可以唯一合并将产生正确的列表，或需要更多的代码来处理特殊情况。不幸的是，原帖作者没有明确他的上下文和要求，以显示这是否构成可接受的答案。 - Gustav Bertram

Answer 1

简单算法：

1. 合并列表
2. 去重
3. 排序

代码：

def order_list(lst, order_dict):
     return sorted(list(lst), key = lambda x: order_dict.get(x, -1))

c = list(set(a + b))
ord_dict = {"First": 1, "Second": 2, "Third": 3, "Fourth": 4}
order_list(c, ord_dict)

- Lukasz Madon

---

我认为针对排序键返回默认值“-1”是一个不好的想法。如果出现意外值，我希望我的排序算法能够快速失败，而不是把它放在列表开头。此外，如果出现了两个意外元素，你无法保证会发生什么。 - jpmc26

@jpmc26 这是一个有效的观点，但这是一个“商业”决策。也许他/她只是在编写一个脚本来分析数据集，一些错误数据是可以接受的。您可以添加一个计数器来知道有多少无效数据，然后只需拼接正确的结果即可。 - Lukasz Madon

@jpmc26 顺便说一下，你的代码工作方式相同。dict.get返回None，这是0。 - Lukasz Madon

这个解决方案行不通，因为我不能依赖字符串进行排序。有关详细信息，请参阅更新的描述。 - Raceimaztion

@lukas 抱歉，谢谢你指出来。我的错误，正在修复中。 - jpmc26

Answer 2

您有两个不同的问题：

• 重复消除
• 排序

我会分别处理它们。消除重复很简单。使用 set：

>>> a = ['Second', 'Third', 'Fourth']
>>> b = ['First', 'Second', 'Third']
>>> x = set(a)
>>> x
set(['Second', 'Fourth', 'Third'])
>>> x.update(b)
>>> x
set(['Second', 'Fourth', 'Third', 'First'])

接下来你需要定义一种排序方式。最简单的方法可能是将每个可能的元素映射到一个值：

>>> order_dict = {'First': 1, 'Second': 2, 'Third': 3, 'Fourth': 4}
>>> result = sorted(list(x), key=lambda i: order_dict[i])
>>> result
['First', 'Second', 'Third', 'Fourth']

如果您可以为您的值定义一个比较函数，您还可以使用一些带有sorted的cmp参数的比较函数。

希望这可以帮助到您。

- jpmc26

---

非常好。+1，不用让我开一个新的问题。 - CosminO

这个解决方案不可行，因为我不能依赖于字符串的可排序性。详情请参见更新后的描述。 - Raceimaztion

Answer 3

如果我们假设您的两个列表都是有序的，并且它们各自仅缺少一些元素，则我可以看到一个算法，应该在大多数情况下都有效。

1. 取A中的下一个索引。 2. 遍历B查找匹配项： - 如果有匹配项： - 从B的开头到匹配项（含匹配项）的所有内容删除，并添加到C。 - 如果没有匹配项： - 将A的索引添加到C。 3. 重复执行步骤2。 4. 如果B中还有任何剩余项，请将其添加到C中。

以下是该算法的Python代码：

a1 = ['Second', 'Third', 'Fourth']
b1 = ['First', 'Second', 'Third']

a2 = ['First', 'Third', 'Fourth']
b2 = ['First', 'Second', 'Third']

a3 = ['First', 'Third', 'Fourth']
b3 = ['First', 'Second', 'Fourth']

def merge(a, b):
    c = []
    b_oldindex = 0
    for a_index in range(len(a)):
        match = False
        for b_index in range(b_oldindex, len(b)):
            if a[a_index] == b[b_index]:
                c.extend(b[b_oldindex:b_index+1])
                b_oldindex = b_index + 1
                match = True
                break
        if not match:
            c.append(a[a_index])
    if b_oldindex < len(b):
        c.extend(b[b_oldindex:])
    return c

print(merge(a1,b1))
print(merge(a2,b2))
print(merge(a3,b3))
print(merge(b1,a1))
print(merge(b2,a2))
print(merge(b3,a3))

这将产生以下输出：

['First', 'Second', 'Third', 'Fourth']
['First', 'Second', 'Third', 'Fourth']
['First', 'Third', 'Second', 'Fourth']
['First', 'Second', 'Third', 'Fourth']
['First', 'Second', 'Third', 'Fourth']
['First', 'Second', 'Third', 'Fourth']

在所有测试用例中，唯一无法产生正确顺序的是merge(a3,b3)。

要完全解决这个问题可能需要实现一个正确的合并算法（如在归并排序中使用的算法），这需要能够评估元素应该处于的顺序。您可以在Rosetta code上看到一个 python实现的合并排序。 更新： 考虑到这实际上是对一组书籍的分期付款进行排序，您可以通过考虑其他信息来避免您在第三组数据中描述的情况。即，按版权或出版日期的相反顺序对列表使用merge函数。

例如，在您的情况下：

a3 = ['First', 'Third', 'Fourth']  # Second novel
b3 = ['First', 'Second', 'Fourth'] # Third novel

a3的书应该在b3的书之前出版。如果你能收集到这种元数据，那么你就可以避免这个问题。

同一本书的不同版本在版权日期上不会有区别，但在出版日期上可能会有区别。因此，在查看出版日期之前，请先查看版权日期。

- Gustav Bertram

Answer 4

我遇到了同样的问题，但我已经找到了答案。我发现这篇文章是因为我在寻找更多Python风格的解决方法。

首先，关于特殊情况的说明：

a=['A','C','D','E']
b=['A','B','D','F']
c=joinListsOrdered(a,b)

在我的情况下，我没有任何问题：['A'，'B'，'C'，'D'，'E'，'F']和['A'，'C'，'B'，'D'，'F'，'E']一样好。我想要的唯一验证条件是：c中元素的顺序分别与a和b中的顺序相同，即[el for el in c if el in a]逐个元素等于a（同样等于b）。我认为这是在没有更多关于问题的信息的情况下，对这个问题的唯一合理立场。

换句话说，重点在于共同的元素（['A'，'D']）。如果这些元素按正确顺序排列，其他所有元素都可以轻松地置于中间。因此，该算法：

def joinListsOrdered(a,b):
    # Find ORDERED common elements
    order={}
    for i, e in enumerate(a):
        order[e]=i
    commonElements=sorted(set(a) & set(b), key=lambda i: order[i])
    # Cycle on each common element.
    i=0 #index of a
    j=0 #index of b
    c=[]
    for comEl in commonElements:
       while not a[i]==comEl:
           c.append(a[i])
           i=i+1
       while not b[j]==comEl:
           c.append(b[j])
           j=j+1
       c.append(comEl)
       i=i+1;j=j+1
    # Add the eventual residuals after the last common element.
    c=c+a[i:]+b[j:]
    return c

当然，如果对于一些共同元素的a和b的顺序不同，则它无法遵守验证条件，但在这种情况下，问题没有解决方案。

- Emanuele

Answer 5

set容器的定义是其中没有重复项。您可以将两个列表转换为set类型，然后再将其转换回list类型：

a = ['Second', 'Third', 'Fourth']
b = ['First', 'Second', 'Third']
c= list(set(a+b))
['Second', 'Fourth', 'Third', 'First']
#Note that set will not organize anything, it will just delete the duplicates

- Lazybeem

---

不幸的是，顺序很重要。这段代码将确定相对巨大的文本块将要放在哪里，而手动重新排序将是一个相当大的问题。 - Raceimaztion

Answer 6

在最简单的情况下，只有一个元素不同，并且它位于相同的位置，只需迭代地加入两个字符串即可。

newlist = []
for i in range(len(a)):
  if a[i] == b[i]:
    newlist.append(a)
  else:
    newlist.append(a)
    newlist.append(b)

如果您的列表比较复杂，首先将其中一个转换为字典，然后在合并时与另一个进行比较。

- XapaJIaMnu

---

即使使用我上面提供的测试用例，这也行不通。你假设重复元素将在不同数组中的相同插槽中，但事实并非如此。 - Raceimaztion