bağlantıların bir dict gelen "arkadaş çevreleri" oluşturuluyor [piton]

Question

Şöyle Facebook arkadaş dicti vardır: Bu dict bir kişi ile eşleşen

connections = { 
0: set([3, 4]), 
1: set([5]), 
2: set([]), 
3: set([0, 4, 6]), 
4: set([0, 3]), 
5: set([1]), 
6: set([3])} 

(yani 3) arkadaşlarına (0 4, 6). Şimdi, arkadaş çevredeki HER KİŞİ arkadaş çevresi içinde HER DİĞER KİŞİ ile arkadaş olduğu gibi bir dizi "arkadaş çevresi" oluşturmak istiyorum. Şunun gibi görünmelidir: {{0, 3, 4}, {3, 4}, {0, 4}, {0, 3}, {1, 5}, ...} Bunu başarmanın basit bir yolu var mı?

Answer 1

from itertools import chain, combinations, product 

connections = { 
    0: set([3, 4]), 
    1: set([5]), 
    2: set([]), 
    3: set([0, 4, 6]), 
    4: set([0, 3]), 
    5: set([1]), 
    6: set([3]) 
} 

# Generate initial friend circles a generator that yields (0, 3, 4), (1, 5), (2,) etc. 
# Please keep in mind that this gets exhausted after one run, 
# if you want to reuse friend_circles later just use a list ([] instead of()) 
friend_circles = (tuple(set([k]+list(v))) for (k, v) in connections.iteritems()) 

# Slightly modified version of python powerset recipe 
# https://docs.python.org/2/library/itertools.html#recipes 
# min_size is to specify the minimum number of people required to form a circle (2 friends in your example). 
# The function further filters the resulting powerset by checking that all the members of the circle are friends with each other. 
def get_valid_circles(iterable, min_size): 
    s = list(iterable) 
    return [ 
     combo for combo in chain.from_iterable(combinations(s, r) for r in xrange(min_size, len(s)+1)) 
     if all(p2 in connections.get(p1, set()) for (p1, p2) in filter(lambda c: c[0] != c[1], product(combo, combo))) 
    ] 

# After retrieving all the valid circles you will end up with dupes as well as some empty sets of circles, so 
# Filter the chain of circles and cast it into a set. 
circles = set(
    filter(None, chain(*(get_valid_circles(friend_circle, 2) for friend_circle in friend_circles))) 
) 
print "Final filtered circles" 
print circles 

# If you want the unfiltered results you can just use this: 
# if you come up with an empty result here, see my note above on friend_circles generator 
# print "Final unfiltered circles" 
# print [get_valid_circles(friend_circle, 2) for friend_circle in friend_circles] 

Bu kişi 0 için, arkadaşları setleri Kişi 1

{0,3}, {0,4}, {0,3,4} 

haline böylece ilk tüm arkadaş setleri genişletmek gerekir

Final filtered circles 
set([(0, 3, 4), (1, 5), (3, 6), (0, 4), (0, 3), (3, 4)]) 

Answer 2

yazdırır olur:

{1,5} 

Kişi 3 olur:

{3,0}, {3,4}, {3,6}, {3,0,4}, {3,0.6}, {3,4,6}, {3,0,4,6} 

hepsini genişletilmiş sonra, sonra tekrar her kişi döngü ve genişletilmiş arkadaşı arkadaşlar her kontrol onlar da aynı genişletilmiş arkadaşı seti olduğunu içerip içermediğini belirler . Arkadaş grubundaki her arkadaş bu arkadaş kümesini içeriyorsa, o zaman arkadaş çevresi. Bu arkadaş çevrelerini sakla. İsterseniz, başka çevrelerin alt kümeleri olup olmadığını denetleyerek alt çemberlerini kaldırabilirsiniz. Örneğin {0,3}, {0,3,4}'un bir alt kümesidir, bu nedenle kaldırılabilir.