Словарь словарей: печатные словари, которые имеют как минимум два общих ключа

Question

d = {'g1':{'p1':1,'p2':5,'p3':11,'p4':1},
     'g2':{'p1':7,'p3':1,'p4':2,'p5':8,'p9':11},
     'g3':{'p7':7,'p8':7},
     'g4':{'p8':9,'p9':1,'p10':7,'p11':8,'p12':3},
     'g5':{'p1':4,'p13':1},
     'g6':{'p1':4,'p3':1,'p6':2,'p13':1}
    }

Для данного словаря 'd' я хочу вернуть кластеры вложенных словарей, которые имеют по крайней мере два ('n') ключа (присутствующих во всех вложенных словарях данного кластера).Мы не заботимся здесь о значениях этих под-словарей.Другими словами, длина пересечения ключей всех под-словарей в данном кластере должна быть не менее двух (или 'n').

Answer 1

Надеюсь, я правильно понял, что вы хотите. Такой подход неуклюж, и я боюсь, что он крайне неэффективен.

Я добавил словарь g6 к d, чтобы получить более интересный вывод:

#! /usr/bin/env python
# -*- coding: utf-8 -*-

d = {'g1':{'p1':1,'p2':5,'p3':11,'p4':1},
     'g2':{'p1':7,'p3':1,'p4':2,'p5':8,'p9':11},
     'g3':{'p7':7,'p8':7},
     'g4':{'p8':9,'p9':1,'p10':7,'p11':8,'p12':3},
     'g5':{'p1':4,'p13':1},
     'g6':{'p1':1,'p9':2,'p11':12}
    }

clusters = {}

for key, value in d.items ():
    cluster = frozenset (value.keys () )
    if cluster not in clusters: clusters [cluster] = set ()
    clusters [cluster].add (key)


for a in clusters.keys ():
    for b in clusters.keys ():
        if len (a & b) > 1 and a ^ b:
            cluster = frozenset (a & b)
            if cluster not in clusters: clusters [cluster] = set ()
            for x in clusters [a]: clusters [cluster].add (x)
            for x in clusters [b]: clusters [cluster].add (x)

print "Primitive clusters"
for key, value in filter (lambda (x, y): len (y) == 1, clusters.items () ):
    print "The dictionary %s has the keys %s" % (value.pop (), ", ".join (key) )

print "---------------------"
print "Non-primitive clusters:"
for key, value in filter (lambda (x, y): len (y) > 1, clusters.items () ):
    print "The dictionaries %s share the keys %s" % (", ".join (value), ", ".join (key) )

Answer 2

Если вы упростите задачу только для кластеров длиной 2 (т. Е. Пар словарей), она станет немного понятнее: генерация подпоследовательностей фиксированной длины из заданной итерации - это точно работа itertools.combination:

>>> list(itertools.combinations(d, 2))
[('g5', 'g4'), ('g5', 'g3'), ('g5', 'g2'), ('g5', 'g1'), ('g4', 'g3'), ('g4', 'g
2'), ('g4', 'g1'), ('g3', 'g2'), ('g3', 'g1'), ('g2', 'g1')]

Мы можем увидеть количество ключей, общих для всех словарей, поняв, что представление d.keys () ведет себя как набор (в Python 3; в Python 2 это может быть список):

>>> d['g1'].keys() & d['g2'].keys()
{'p3', 'p1', 'p4'}

& - это оператор пересечения множества - он дает нам набор всех элементов, которые имеют эти множества общего.Поэтому мы можем проверить, что существует как минимум два из них, проверив длину этого набора, что дает нам:

>>> common_pairs = [[x,y] for x,y in itertools.combinations(d, 2)
                                   if len(d[x].keys() & d[y].keys()) >= 2]
>>> common_pairs
[['g2', 'g1']]

Решить для неизвестного размера кластера немного сложнее - мы не можем использовать оператор &непосредственно, если мы не жестко это кодируемК счастью, класс set предоставляет нам метод для пересечения множеств n в форме set.intersection.Он не примет экземпляр dict_keys, но вы можете легко исправить это с помощью вызова set:

>>> set.intersection(d['g1'].keys(), d['g2'].keys(), d['g5'].keys())
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: descriptor 'intersection' requires a 'set' object but received a 'dict_keys'
>>> set.intersection(set(d['g1']), set(d['g1']), set(d['g5']))
{'p1'}

Вы должны иметь возможность обобщить это для кластеров размером от 2 до n довольно тривиально.

Answer 3

Я думаю, что вы должны сначала «инвертировать» словарь, а затем легко найти решение:

import collections
inverted = collections.defaultdict(list)

for key, items in d.items():
    for sub_key in items:
        inverted[sub_key].append(key)

for sub_key, keys in inverted.items():
    if len(keys) >= 2:
        print sub_key, keys

Answer 4

Что-то вроде

for keya in d:
    tempd = {}
    keys = set()
    tempset = set(d[keya].keys())

    for keyb in d:
        tempset &= d[keyb].keys()

        if len(tempset) >= 2:
            keys.add(keyb)

    print({key: d[key] for key in keys})

Может работать.

РЕДАКТИРОВАТЬ: Нет, это не совсем работает.Мне нужно подумать об этом.