使用Python将字典中列表中的值分组以创建新字典，并为每个值指定组号？

Question

下图是三组相互接触的方块，每个方块都有编号。

我已经能够使用空间库ArcPy构建下面的字典，它使用平方数作为键，并使用它所触及的平方的数字列表作为值。例如，正方形1只接触正方形4，正方形4接触正方形1和6，依此类推。

dict = {1: [4], 2: [3, 5], 3: [2, 5], 4: [1, 6], 5: [2, 3], 6: [4, 8], 7: [9, 10], 8: [6, 11], 9: [7, 10], 10: [7, 9], 11: [8]}

从图中可以清楚地看到，有三组相互接触的正方形，所以我想要的结果是一个新的字典，其中的键是正方形的数字，值是它所属的接触组。我将使用字母命名接触组，但这些名称可以是任何名称，因此一个可能的解决方案是:

newDict = {9:"A",10:"A",7:"A",1:"B",4:"B",6:"B",8:"B",11:"B",5:"C",2:"C",3:"C"}

从dict到newDict，有没有一种Python方式？

我使用Python 2.7.14进行测试。

Answer 1

您可以使用网络库来确定图形的聚类或子组。

鉴于

from string import ascii_uppercase as uppercase

import networkx as nx
import matplotlib.pyplot as plt


%matplotlib inline


d = {
    1: [4], 2: [3, 5], 3: [2, 5], 4: [1, 6], 5: [2, 3], 6: [4, 8], 
    7: [9, 10], 8: [6, 11], 9: [7, 10], 10: [7, 9], 11: [8]
}

代码

G = nx.from_dict_of_lists(d)

# Label sub-groups
sub_graphs = list(nx.connected_component_subgraphs(G))
{val: label for label, sg in zip(uppercase, sub_graphs) for val in sg.nodes()}
# {1: 'A', 2: 'B', 3: 'B', 4: 'A', 5: 'B', 6: 'A', 7: 'C', 8: 'A', 9: 'C', 10: 'C', 11: 'A'}

详细资料

为了便于可视化，下面是标记的子组（另请参阅激励代码）：

# Printed subgroups
for label, sg in zip(uppercase, sub_graphs):
    print("Subgraph {}: contains {}".format(label, sg.nodes()))

# Subgraph A: contains [8, 1, 11, 4, 6]
# Subgraph B: contains [2, 3, 5]
# Subgraph C: contains [9, 10, 7]

尽管我最终会推荐一个最终的列表字典，以更清晰地分组数据：

{label: sg.nodes() for label, sg in zip(uppercase, sub_graphs)}
# {'A': [8, 1, 11, 4, 6], 'B': [2, 3, 5], 'C': [9, 10, 7]}

此外，您还可以选择绘制这些图形：

# Plot graphs in networkx (optional)
nx.draw(G, with_labels=True)

Answer 2

我尝试了递归解决方案，如果你愿意，你可以试试:

dict22 = {1: [4], 2: [3, 5], 3: [2, 5], 4: [1, 6], 5: [2, 3], 6: [4, 8], 7: [9, 10], 8: [6, 11], 9: [7, 10], 10: [7, 9], 11: [8]}



def connected_nodes(dict34):
    final=[]
    for i,j in dict34.items():
        def recursive_approach(dict1, tem, data,check=[], dict_9={}):
            if data!=None:
                dict_9.update({data:dict22[data]})

            dict_9.update({tem: dict1[tem]})


            check.append(tem)
            final.append(dict_9)
            if check.count(tem) > 1:
                return 0

            for i, j in dict1.items():
                if tem in dict1:
                    return recursive_approach(dict1, tem=dict1[tem][-1],data=None)


        recursive_approach(dict22, tem=j[-1],data=i)
    return final


bew=[]
for i in connected_nodes(dict22):
    bew.append(list(i.keys()))


new_bew=bew[:]
final_result=[]
for j,i in enumerate(bew):
    for m in new_bew:

        if set(i).issubset(set(m)) or set(m).issubset(set(i)):
            if len(i)>len(m):
                final_result.append(tuple(i))
                new_bew.remove(m)

            else:
                final_result.append(tuple(m))


        else:
            pass
print(set(final_result))

输出：

{(2, 3, 5), (9, 10, 7), (1, 4, 6, 8, 11)}

Answer 3

仅供你参考...CLRS不交集并的秩算法求解。这是我所知道的最有效的不相交集发现算法。

从本质上讲，只需将问题视为断开连接的图形，使用并集查找找到每个边缘的父级并将它们关联起来。

输出为每个父对象关联不同的集合标识符，而不是统一的A-Z，但是预先生成顶点到字母的映射比之后关联它们更有效。通过这种方式，您可以拥有多达26个不相交的集合。此外，您可能希望转向数字标识符。

复杂度为 O（ | d.键（） | * 对数（| d.值（） |） ）

d = {1: [4], 2: [3, 5], 3: [2, 5], 4: [1, 6], 5: [2, 3], 6: [4, 8], 7: [9, 10], 8: [6, 11], 9: [7, 10], 10: [7, 9], 11: [8]}


class MSet(object):
    def __init__(self, p):
        self.val = p
        self.p = self
        self.rank = 0

def parent_of(x): # recursively find the parents of x
    if x.p == x:
        return x.val
    else:
        return parent_of(x.p)

def make_set(x):
    return MSet(x)

def find_set(x):
    if x != x.p:
        x.p = find_set(x.p)
    return x.p

def link(x,y):
    if x.rank > y.rank:
        y.p = x
    else:
        x.p = y
        if x.rank == y.rank:
            y.rank += 1

def union(x,y):
    link(find_set(x), find_set(y))

vertices = {k: make_set(k) for k in d.keys()}
edges = []

for k,u in vertices.items():
    for v in d[k]:
        edges.append((u,vertices[v]))

# do disjoint set union find similar to kruskal's algorithm
for u,v in edges:
    if find_set(u) != find_set(v):
        union(u,v)

# resolve the root of each disjoint set
parents = {}

# generate set of parents

set_parents = set() 

for u,v in edges:
    set_parents |= {parent_of(u)}
    set_parents |= {parent_of(v)}

# make a mapping from only parents to A-Z, to allow up to 26 disjoint sets
letters = {k : chr(v) for k,v in zip(set_parents, list(range(65,91)))}

for u,v in edges:
    parents[u.val] = letters[parent_of(u)]
    parents[v.val] = letters[parent_of(v)]

print(parents)

输出：

rpg711$ python disjoint_set_union_find 
{1: 'C', 2: 'B', 3: 'B', 4: 'C', 5: 'B', 6: 'C', 7: 'A', 8: 'C', 9: 'A', 10: 'A', 11: 'C'}

我对您期望的字典进行了排序，以便更轻松地关联集合标识符并检查我的工作：

sorted(d.items(), key=lambda k: k[0])
[(1, 'B'), (2, 'C'), (3, 'C'), (4, 'B'), (5, 'C'), (6, 'B'), (7, 'A'), (8, 'B'), (9, 'A'), (10, 'A'), (11, 'B')]

在我建议的解决方案“B”中-

PS：如果存在不接触任何其他顶点（没有边缘）的顶点，则应生成或修改输入字典，以使这些顶点本身具有边缘。