合并包含相同元素的子列表

Question

我想编写一个快速的函数，该函数将遍历子列表中的元素，并在它们包含元素时合并子列表。例如，列表[[0, 3], [3, 4], [5, 6]]应该被合并为[[0, 3, 4]，[5, 6]]。子列表的大小可以是任意的，每个子列表的大小都可以不同，因此可能包含许多元素。

我目前的代码（不起作用）如下所示。出现的错误是：slice indices must be integers or None or have an __index__ method

def join_clusters(clusters):
    for cluster in clusters:
        for j in cluster:
            for k in clusters[cluster:]:
                for h in k:
                    if j == h:
                        cluster.append(k)
                        clusters.pop(k)
                        return clusters

- Hello

---

你只想合并相邻的子列表吗？[[1,2,3], [3,4,5], [5,6,7]]会被合并成[[1,2,3,4,5,6,7]]吗？ - PM 2Ring

@PM2Ring 我也这么认为，这是我做的方式。 - Tom Fuller

我认为你正在尝试解决一个集合合并/连通分量/并查集问题——如果是这种情况，那么它就是许多先前问题的重复——但你的示例有点令人困惑，因为它可以被解释为链接相邻的链。[[1,2],[3,1],[1,3]] 应该变成 [[1,2,3]] 吗？ - DSM

是的，这正是我需要的。[[1,2],[3,1],[1,3]] 将变成 [[1,2,3]]。 - Hello

Answer 1

如果子集已排序，我会尝试使用集合进行操作。

from itertools import islice

def merge(T):
  idx = 0
  result = [set(T[0])]
  for sublst in islice(T, 1, len(T)):
    subset = set(sublst)
    if result[idx] & subset:
      result[idx].update(subset)
    else:
      result.append(set(sublst))
      idx += 1
  return [sorted(sub) for sub in result]

- Nf4r

Answer 2

我使用了 while 循环来更容易地引用列表中的下一个群集。

def join_clusters(clusters):
    idx = 0
    while idx < len(clusters) - 1:
        for element in clusters[idx]:
            if element in clusters[idx + 1]:
                clusters[idx].remove(element)
                clusters[idx] = clusters[idx] + clusters[idx + 1]                
                del(clusters[idx + 1])
                break
        idx = idx + 1
    return clusters

希望这可以对你有所帮助 :)

- Tom Fuller

---

我的错误，谢谢指出。 - Tom Fuller

非常感谢。 - Hello

非常感谢，这正是我所需要的！ - Hello

@你好，没问题 :) - Tom Fuller

Answer 3

这里有一个解决方案，适用于任何类型的子列表，无论它是否已排序：

def join_clusters(clusters):
    result = clusters[:1]                          #1
    for cluster in clusters[1:]:
        if cluster[0] == result[-1][-1]:
            result[-1] = result[-1] + cluster[1:]  #2
        else:
            result.append(cluster)                 #3
    return result

例子：

>>> c1 = [[0, 3], [3, 4], [5, 6]]
>>> join_clusters(c1)
[[0, 3, 4], [5, 6]]

>>> c2 = [[3, 1], [1, 2], [1, 3], [2, 1], [1, 3], [3, 1], [1, 2]]
>>> join_clusters(c2)
[[3, 1, 2], [1, 3], [2, 1, 3, 1, 2]]

>>> les_mis = "At the end of the day you're another day older".split()
>>> join_clusters(les_mis)
['Athend', 'of', 'the', "dayou're", 'another', 'day', 'older']

注：

#1：如果您希望输出仅包含输入的副本而不是实际原始子列表，请使用result = clusters[:1][:]。

#2：不使用result[-1] += cluster[1:]，因为这会改变原始列表的元素，这可能是不可取的。

#3：如果您希望输出仅包含输入的副本而不是实际原始子列表，请使用result.append(cluster[:])。

- Zero Piraeus

---

有没有办法删除重复项，使得[2, 1, 3, 1, 2]变成[1,2,3]（顺序不重要）？ - Hello

此外，是否有任何方法可以修改列表集群，而不是创建副本？ - Hello

1. 不得不重新开始——看起来我以为你要问的问题不是你想要答案的那个。
2. 嗯，是的，但鉴于第一点，似乎没有太大的意义；-)

- Zero Piraeus

谢谢你的帮助。 - Hello