0

这不是家庭作业（请参阅我的个人资料）。我没有计算机科学背景，这个问题出现在一个应用机器学习问题中。我很确定我不是第一个遇到这个问题的人，因此我正在寻找一个优雅的解决方案。与原始实现相比，我更喜欢使用 python 库的解决方案。

假设我们有一个连接字母和数字的字典作为输入

connected = {
    'A': [1, 2, 3],
    'B': [3, 4],
    'C': [5, 6],
}

每个字母可以连接到多个数字。一个数字可以连接多个字母。但是每个字母只能与一个数字连接一次。

如果我们查看字典，我们会意识到，数字3与字母'A'和字母相连，'B'因此我们可以将'A'和'B'放入一个簇中。该字母的数字'C'不存在于其他字母中。因此，我们不能'C'进一步对字母进行聚类。预期的输出应该是

cluster = {
    '1': {
        'letters': ['A', 'B'],
        'numbers': [1, 2, 3, 4], 
    },
    '2': {
        'letters': ['C'],
        'numbers': [5, 6],
    }
}

我认为这应该与图算法和连接子图有关，但我不知道从哪里开始。

4

1 回答 1

1

使用联合查找结构，您可以在O(num letters + num numbers). 关键思想是您可以将字母连接到他们的数字列表。一旦你对所有字母都这样做了，你就会自动拥有所需属性的联合（即集群）。

class UnionFind:
    def __init__(self):
        self.id = {}
        self.size = {}

    def find(self, a):
        cur = a
        path = []
        while self.id[cur] != cur:
            path.append(cur)
            cur = self.id[cur]
        for x in path:
            self.id[x] = cur
        return cur

    def union(self, a, b):
        if a not in self.id:
            self.id[a] = a
            self.size[a] = 1
        if b not in self.id:
            self.id[b] = b
            self.size[b] = 1

        roota, rootb = self.find(a), self.find(b)
        if roota != rootb:
            if self.size[roota] > self.size[rootb]:
                roota, rootb = rootb, roota
            self.id[roota] = rootb
            self.size[rootb] += self.size[roota]

if __name__ == "__main__":
    from collections import defaultdict

    uf = UnionFind()
    connected = {
        'A': [1, 2, 3],
        'B': [3, 4],
        'C': [5, 6],
    }
    for letter, numbers in connected.items():
        for number in numbers:
            uf.union(letter, number)
    
    clusters = defaultdict(list)
    for key, cluster_id in uf.id.items():
        clusters[cluster_id].append(key)
    
    formatted_clusters = {}
    for i, cluster_elements in enumerate(clusters.values()):
        letters = [e for e in cluster_elements if isinstance(e, str)]
        numbers = [e for e in cluster_elements if not isinstance(e, str)]
        key = str(i+1)
        formatted_clusters[key] = {
            "letters": letters,
            "numbers": numbers
        }
    print(formatted_clusters)

输出：

{'1': {'letters': ['A', 'B'], 'numbers': [1, 2, 3, 4]}, '2': {'letters': ['C'], 'numbers': [5, 6]}}
于 2021-02-20T09:21:47.267 回答