根据 Python3 中的共享字典值创建分组列表

Question

我有一个设备字典，其中每个设备都有一个可以与之协作的其他设备的列表。将这些视为与其兼容的设备。

 devices = {0: [], 1: [9, 10, 14], 2: [9, 11, 14], 3: [], 4: [], 5: [9, 14, 15], 6: [], 7: [], 8: [], 9: [1, 2, 5, 11, 14, 15], 10: [1], 11: [2, 9, 14], 12: [], 13: [], 14: [1, 2, 5, 9, 11, 16], 15: [5, 9], 16: [14], 17: [], 18: [], 19: []}

我希望能够将这些聚类成一个列表列表，其中包含可以一起协作的所有可能的聚类。集群只能包含相互兼容的设备。换句话说，如果集群 [1,9,2] 存在，则 1 必须与 9 和 2 协作，并且它们也必须相互协作。在这种情况下，最终结果应如下所示：

[ [1, 9, 14], [2, 9, 14], [5,9,14], [5,15,9] [9,11,14,2], [10,1], [14,16]  ]

我可能在手动计算时犯了一个错误，但我相信这是所有可能的项目集群，同时满足它们的兼容性要求。

但是，我在将其转换为代码时遇到了一些困难。任何帮助将不胜感激。

Answer 1

可能有更简洁的方法来获得结果，但这段代码有效。

请注意，您的结果包括 [2, 9, 14]，它是 [9,11,14,2] 的子集。此代码中删除了子集。

items = {0: [], 1: [9, 10, 14], 2: [9, 11, 14], 3: [], 4: [], 5: [9, 14, 15], 6: [], 7: [], 8: [], 
         9: [1, 2, 5, 11, 14, 15], 10: [1], 11: [2, 9, 14], 12: [], 13: [], 14: [1, 2, 5, 9, 11, 16], 
         15: [5, 9], 16: [14], 17: [], 18: [], 19: []}


grps = []

# create 1-1 groups
for g in items:
   for c in items[g]:
       if g in items[c]:
          grps.append([g,c])

# add other elements to each group
chg = True
while chg: # until no more elements added
    chg = False
    for g in items: # each single element
       for g2 in grps:  # check each existing group
          if g in g2: continue  # if not already in group
          ok = True
          for c in g2: # check each group member
             if not (g in items[c] and c in items[g]): # can we collaborate?
                 ok = False  # no
          if ok: 
             g2.append(g)  # add element to group
             chg = True
      
# check for subsets
for i,x in enumerate(grps):
   for j,y in enumerate(grps):
      if i==j: continue # same group
      if set(x) & set(y) == set(x): # if subset
         x.clear() # remove elements 

grps = [g for g in grps if len(g)]  # remove empty groups

print(grps)

输出

[[10, 1], [14, 5, 9], [14, 9, 1], [14, 11, 2, 9], [15, 9, 5], [16, 14]]

Answer 2

您可以这样做的一种方法：

from itertools import  combinations

colaborate2 = lambda args, dic : all(x in dic[y] and y in dic[x] for x, y in combinations(args,2))

def group (x, dic, n=None):
  if n is None:
    n = len(x)
  for i in combinations(x, n):
    if colaborate2(i, dic):
       return tuple(sorted(i))
  if n > 1:
     return group(x, dic, n - 1)

def groupings(dic):
    m = set([group(val + [key], dic) for key, val in dic.items()])
    return [i for i in m if len(i)>1]

groupings(items)
[(5, 9, 15), (14, 16), (5, 9, 14), (1, 9, 14), (1, 10), (2, 9, 11, 14)]

Answer 3

虽然我花了几个小时，但我对整洁干净的解决方案感到满意。在编码时理解需求占用了我 90% 的时间。经验教训 - 先用铅笔和纸。

代码：

devices = {0: [], 1: [9, 10, 14], 2: [9, 11, 14], 3: [], 4: [], 5: [9, 14, 15], 6: [], 7: [], 8: [], 9: [1, 2, 5, 11, 14, 15], 10: [1], 11: [2, 9, 14], 12: [], 13: [], 14: [1, 2, 5, 9, 11, 16], 15: [5, 9], 16: [14], 17: [], 18: [], 19: []}
# manually calculated expected result [ [1, 9, 14], [2, 9, 14], [5,9,14], [5,15,9] [9,11,14,2], [10,1], [14,16]  ]
# true result [[1, 9, 14], [2, 9, 11, 14], [5, 9, 14], [10, 1], [15, 5, 9], [16, 14]]

def is_compatible(k,v):
    if v in devices[k]:
        return True
    return False
   
clusters = []
for k,v_list in devices.items():
    if v_list:
        cluster = []       
        cluster.append(k)
        cluster.append(v_list[0])
        for v_ele in v_list[1:]:
            v_ele_further_check = True
            for cluster_member in cluster[1:]: # check v_ele compatible with existing cluster members
                if not is_compatible(v_ele, cluster_member):
                    v_ele_further_check = False
                    break
            if v_ele_further_check:
                cluster.append(v_ele)
        clusters.append(cluster)

print(clusters)

unique_clusters = []
for cluster in clusters: # eliminate_duplicates
    if not sorted(cluster) in unique_clusters:
        unique_clusters.append(cluster)

print(unique_clusters)

输出：

[[1, 9, 14], [2, 9, 11, 14], [5, 9, 14], [9, 1, 14], [10, 1], [11, 2, 9, 14], [14, 1, 9], [15, 5, 9], [16, 14]]
[[1, 9, 14], [2, 9, 11, 14], [5, 9, 14], [10, 1], [15, 5, 9], [16, 14]]

评论：

你可以看到我可以很容易地去掉函数 is_compatible 但它增加了可读性。如果重要的话，集群中的集群顺序会得到正确维护。

根据 Python3 中的共享字典值创建分组列表

Creating grouped lists based on shared dictionary values in Python3

python

grouping

dictionary

list

python-3.x