python - 当键与共享值关联时，将字典键分组

给定s1，s2，s3，s4和s5：

s1 = {0: (0,), 1: (0,), 2: (1,)}
s2 = {0: (1,), 1: (0,), 2: (2,)}
s3 = {0: (1, 0), 1: (0,), 2: (2,)}
s4 = {0: (0, 1), 1: (1, 2), 2: (2, 3), 4: (4,)}
s5 = {0: (0, 1), 1: (1, 2), 2: (2, 3), 4: (4, 1)}

我可以使用什么函数分别将它们分别转换为r1，r2，r3，r4或r5：

r1 = {(0, 1): {0}, (2,): {1}}
r2 = {(2,): {2}, (0,): {1}, (1,): {0}}
r3 = {(0, 1): {0, 1}, (2,): {2}}
r4 = {(0, 1, 2): {0, 1, 2, 3}, (4,): {4}}
r5 = {(0, 1, 2, 4): {0, 1, 2, 3, 4}}

进行键分组以使sum(len(k) for k in r) == len(set.union(*r))为True，其中r为r1至r5。

这是一个蛮力解决方案，但我想看看其他方法：

def combinations(segment):
  if len(segment) == 1:
    yield (segment,)
  else:
    for x, j in enumerate(combinations(segment[1:])):
      yield ((segment[0],),)+j
      for k in range(len(j)):
         yield (((segment[0],)+j[k]),) + (j[:k]) +(j[k+1:])

def sub_combinations(segment):
    yield from filterfalse(lambda x: x == (segment,), combinations(segment))

def no_common_elements(sets):
  return sum(len(s) for s in sets) == len(set.union(*sets))

def get_mutually_exclusive_groups(d):
  for i in sub_combinations(tuple(d.keys())):
    r = dict(((j, set.union(*[set(d[k]) for k in j])) for j in i) )
    if no_common_elements(r.values()):
      return r
  return { tuple(set([ k for k in d])): set.union(*([ set(d[k]) for k in d])) }

inputs = [
    {0: (0,), 1: (0,), 2: (1,)},
    {0: (1,), 1: (0,), 2: (2,)},
    {0: (1,0), 1: (0,), 2: (2,)},
    {0:(0,1), 1:(1,2), 2: (2,3), 4: (4,)},
    {0:(0,1), 1:(1,2), 2: (2,3), 4: (4,1)}
]

for input in inputs:
  print(input)
  print(get_mutually_exclusive_groups(input))
  print()

最佳答案

不是我编写过的最漂亮的代码，但我认为它可以满足您的要求。

首先，将键和值转换为集合，并将它们组合为（key_set，value_set）元组的列表集合。创建一个空列表rsets。
遍历两个列表中的元组；如果sset和rsets元组的value_sets相交，则用key_sets和value_sets的并集更新rset元组。如果找不到匹配项，则将ssets tuple添加到rsets。最后，将rsets转换为dict。

s1 = {0: (0,), 1: (0,), 2: (1,)}
s2 = {0: (1,), 1: (0,), 2: (2,)}
s3 = {0: (1,0), 1: (0,), 2: (2,)}

for s in (s1, s2, s3):
    ssets = [(set([k]),set(v)) for k,v in s.items()]
    rsets = []
    for (skey_set, svalue_set) in ssets:
        for i, (rkey_set, rvalue_set) in enumerate(rsets):
            if svalue_set & rvalue_set:
                rsets[i] = (skey_set|rkey_set, svalue_set|rvalue_set)
                break
        else:
            rsets.append((skey_set,svalue_set))
    r = dict((tuple(k),tuple(v)) if len(k) > 1 else (tuple(k)[0],tuple(v))
             for k,v in rsets)
    print(r)

输出：

{(0, 1): (0,), 2: (1,)}
{0: (1,), 1: (0,), 2: (2,)}
{(0, 1): (0, 1), 2: (2,)}

关于python - 当键与共享值关联时，将字典键分组，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53792332/