下图是三组相互接触的方块,每个方块都有编号。
我已经能够使用空间库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进行测试。
您可以使用网络库
来确定图形的聚类或子组。
鉴于
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)
我尝试了递归解决方案,如果你愿意,你可以试试:
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)}
仅供你参考...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:如果存在不接触任何其他顶点(没有边缘)的顶点,则应生成或修改输入字典,以使这些顶点本身具有边缘。
问题内容: 我试图以一种优雅的方式编写一个函数,该函数将字典列表进行分组并汇总(加和)like键的值。 例: 我尝试使用itertools为groupby进行此操作,并对每个相似键值对进行求和,但是这里缺少一些内容。这是我的函数当前的样子: 问题答案: 您可以使用和。 使用dict可以在中完成,而排序则需要时间。 的优点是它将自动将相似键的值相加。 例:
问题内容: 我有以下字典 我想获取字典列表中每个字典值“ KA20”和“ KA23”的键“ tmst”的总和。 您能对此提出建议吗? 问题答案: 您可以使用: 请注意,要正常工作,必须按分组键进行排序:
问题内容: 我正在尝试合并三个具有相同键,值列表或单个值的字典。 我需要将值中的所有项目添加到一个列表中。 我尝试了几种方法,但是大多数方法将值放入嵌套列表中。例如 我尝试通过遍历值来更新它: 但结果完全一样。我试图简单地添加列表,但是由于第三个字典只有一个浮点数,所以我做不到。 因此,我尝试首先以1和2的值添加列表,然后附加3的值。添加列表效果很好,但是当我尝试从第三个字典中添加浮点数时,突然整
我想更改字典的纬度和经度值。 它正在抛出以下错误消息: 对于此它在targetWaypoints内打印一个完整的字典。我想打印纬度值。 提前谢谢。
问题内容: 我需要将列表转换成字典,如下所示。奇数元素具有键,偶数元素具有值。 -> 获得相同结果的更好方法? 添加 似乎在工作 问题答案: dict(x[i:i+2] for i in range(0, len(x), 2))
问题内容: 我想更新一个字典中的值,该值只能由字典中的另一个值来标识。也就是说,鉴于此输入: 我想将伴随格式更改为“ csv”: 我发现这可行: 但这似乎很冗长,所以我想知道是否有一种更优雅的方式来表达这一点。jq似乎缺少某种表达式选择器,等效于xpath。 (当我开始这个问题时,我发现了,所以并没有我想的那么糟。) 问题答案: 您要寻找的是一项复杂的任务: 也许不短,但是根据要求它更优雅。请参阅