在python中創建認識其他朋友的朋友的字典

Question

在任何一羣人中都有很多朋友。假設兩個朋友分享朋友是朋友自己。 （是的，在現實生活中這是一個不切實際的假設，但我們仍然要這樣做）。換句話說，如果人A和B是朋友，而B是C的朋友，那麼A和C也必須是朋友。只要我們知道團隊中的友誼，就可以使用這條規則將任何一羣人分成友誼圈。

編寫一個函數需要兩個參數的networks（）。第一個參數是組中的人數，第二個參數是定義朋友的元組對象列表。假設人們用數字0到n-1來標識。例如，元組（0,2）表示人0與人2是朋友。該函數應該將人的分區打印成友誼圈。下圖顯示了函數的幾個樣品運行：

>>>networks(5,[(0,1),(1,2),(3,4)])#execute 

社交網絡0 {0,1,2}

社交網絡1 {3,4}

我是誠實很失落關於如何開始這個計劃，任何提示將不勝感激。

Answer 1

def networks(n,lst): 
groups= [] 
for i in range(n) 
    groups.append({i}) 
for pair in lst: 
    union = groups[pair[0]]|groups[pair[1]] 
    for p in union: 
     groups[p]=union 
sets= set() 
for g in groups: 
    sets.add(tuple(g)) 
i=0 
for s in sets: 
    print("network",i,"is",set(s)) 
    i+=1 

這就是我一直在尋找，如果有人問津。

Answer 2

您可以用來解決這個問題的一個有效的數據結構是disjoint set，也被稱爲union-find結構。後來我寫了一個another answer。

這裏的結構：

class UnionFind: 
    def __init__(self): 
     self.rank = {} 
     self.parent = {} 

    def find(self, element): 
     if element not in self.parent: # leader elements are not in `parent` dict 
      return element 
     leader = self.find(self.parent[element]) # search recursively 
     self.parent[element] = leader # compress path by saving leader as parent 
     return leader 

    def union(self, leader1, leader2): 
     rank1 = self.rank.get(leader1,1) 
     rank2 = self.rank.get(leader2,1) 

     if rank1 > rank2: # union by rank 
      self.parent[leader2] = leader1 
     elif rank2 > rank1: 
      self.parent[leader1] = leader2 
     else: # ranks are equal 
      self.parent[leader2] = leader1 # favor leader1 arbitrarily 
      self.rank[leader1] = rank1+1 # increment rank 

這裏是你如何使用它來解決問題：

def networks(num_people, friends): 
    # first process the "friends" list to build disjoint sets 
    network = UnionFind() 
    for a, b in friends: 
     network.union(network.find(a), network.find(b)) 

    # now assemble the groups (indexed by an arbitrarily chosen leader) 
    groups = defaultdict(list) 
    for person in range(num_people): 
     groups[network.find(person)].append(person) 

    # now print out the groups (you can call `set` on `g` if you want brackets) 
    for i, g in enumerate(groups.values()): 
     print("Social network {} is {}".format(i, g)) 

Answer 3

下面是基於connected components in a graph溶液（由@Blckknght建議）：

def make_friends_graph(people, friends): 
    # graph of friends (adjacency lists representation) 
    G = {person: [] for person in people} # person -> direct friends list 
    for a, b in friends: 
     G[a].append(b) # a is friends with b 
     G[b].append(a) # b is friends with a 
    return G 

def networks(num_people, friends): 
    direct_friends = make_friends_graph(range(num_people), friends) 
    seen = set() # already seen people 

    # person's friendship circle is a person themselves 
    # plus friendship circles of all their direct friends 
    # minus already seen people 
    def friendship_circle(person): # connected component 
     seen.add(person) 
     yield person 

     for friend in direct_friends[person]: 
      if friend not in seen: 
       yield from friendship_circle(friend) 
       # on Python <3.3 
       # for indirect_friend in friendship_circle(friend): 
       #  yield indirect_friend 

    # group people into friendship circles 
    circles = (friendship_circle(person) for person in range(num_people) 
       if person not in seen) 

    # print friendship circles 
    for i, circle in enumerate(circles): 
     print("Social network %d is {%s}" % (i, ",".join(map(str, circle)))) 

例如：

networks(5, [(0,1),(1,2),(3,4)]) 
# -> Social network 0 is {0,1,2} 
# -> Social network 1 is {3,4}