列出我无法解决的Python中的问题

Question

我有10个不同的列表，它们的数字从0到10。这10个列表中的每个列表都是“person”，它们包含的数字是“friend”。数字是它们的ID。所以我有一些类似的东西：

person = 0   friend = 5
person = 1   friend = 2
person = 1   friend = 3
person = 1   friend = 4
person = 1   friend = 6
person = 1   friend = 8
person = 2   friend = 1
person = 2   friend = 4
person = 2   friend = 6
person = 2   friend = 7
person = 2   friend = 9
person = 3   friend = 1
person = 3   friend = 6
person = 3   friend = 8
person = 4   friend = 1
person = 4   friend = 2
person = 4   friend = 6
person = 4   friend = 7
person = 4   friend = 9
person = 5   friend = 0
person = 6   friend = 1
person = 6   friend = 2
person = 6   friend = 3
person = 6   friend = 4
person = 6   friend = 8
person = 7   friend = 2
person = 7   friend = 4
person = 7   friend = 9
person = 8   friend = 1
person = 8   friend = 3
person = 8   friend = 6
person = 9   friend = 2
person = 9   friend = 4
person = 9   friend = 7

现在我想找一个人的朋友的朋友。我的意思是我想要这样的输出。

人员0与5相关

人1与2、3、4、6、8以及这些朋友的朋友有关。所以输出必须是这样的：

人1与2(4，6，7，9)，3(6，8)，4(2，6，7，9)，6(2，3，4，8)，8(3，6)相关。朋友的朋友的朋友也喜欢这样：

人1与2(4(2,6,7,9)，6(1，3，4，8).

然后我将从列表中删除重复的数字，这样我就有了类似的东西：

人1与，2，3，4，6，7，8，9相关。因为人1与所有人都有关系，即使是间接的关系。我不确定我是否能解释清楚，但你可以问我不清楚的地方。耽误您时间，实在对不起。

Answer 1

假设每个人的好友列表是这样存储的：

friends = {
    0: [5],
    1: [2, 3, 4, 6, 8],
    # and so on as in your question
    9: [2, 4, 7]
}

然后，您可以使用breadth-first search或depth-first search算法的变体在这个有向图中找到person的连接部分。

def related_persons(person):
    visited = {person}
    to_be_investigated = {person}
    while to_be_investigated:
        current_person = to_be_investigated.pop()
        for friend in friends[current_person]:
            if friend not in visited:
                visited.add(friend)
                to_be_investigated.add(friend)
    return visited

这段代码比the code you linked to更短、更容易。

编辑：要获得一个非常好的python图形库，请查看NetworkX。它也有the functionality you want。如果你只需要这一个函数，我不建议使用它，但它可能有助于对你的友谊图进行更深入的分析。

Answer 2

提示:您正在尝试做的事情就像是一个人际网络上的breadth-first search。为了更好地表示这个网络，您可以尝试创建一个字典映射person -> set_of_friends。

让我们首先将数据放到两个列表中：persons和friends

>>> persons = [0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
>>> friends = [5, 2, 3, 4, 6, 8, 1, 4, 6, 7, 9, 1, 6, 8, 1, 2, 6, 7, 9, 0, 1, 2, 3, 4, 8, 2, 4, 9, 1, 3, 6, 2, 4, 7]

现在，让我们构建从每个人到他们的朋友的映射。

>>> friend_dict = {key:{v for i,v in enumerate(friends) if persons[i] == key} for key in set(persons)}
>>> friend_dict
{0: {5},
 1: {2, 3, 4, 6, 8},
 2: {1, 4, 6, 7, 9},
 3: {1, 6, 8},
 4: {1, 2, 6, 7, 9},
 5: {0},
 6: {1, 2, 3, 4, 8},
 7: {2, 4, 9},
 8: {1, 3, 6},
 9: {2, 4, 7}}

有关如何使用NumPy加速的小技巧，请参阅this question (不知羞耻的插件)。或者，如果你使用pandas，你可以通过groupby()获取这些信息。不管怎样，现在我们要浏览字典两次(一次是为了找到你的朋友，另一次是为了找到他们的朋友)。

>>> for person in friend_dict: 
...     friends_of_friends = set()
...     for friend in friend_dict[person]:                 # For each of my friends,
...         friends_of_friends.update(friend_dict[friend]) # look up their friends.
...     print(person, friends_of_friends)
...
0 {0}
1 {1, 2, 3, 4, 6, 7, 8, 9}
2 {1, 2, 3, 4, 6, 7, 8, 9}
3 {1, 2, 3, 4, 6, 8}
4 {1, 2, 3, 4, 6, 7, 8, 9}
5 {5}
6 {1, 2, 3, 4, 6, 7, 8, 9}
7 {1, 2, 4, 6, 7, 9}
8 {1, 2, 3, 4, 6, 8}
9 {1, 2, 4, 6, 7, 9}

现在您了解了每个人的朋友(friend_dict)，并且您刚刚找到了每个人的朋友的朋友。

请注意，0和5相互连接，但没有其他人连接。看起来其他每个人最终都会与其他人联系在一起。您现在看到了递归可能派上用场的地方了吗？您希望不断重复遍历字典，直到某人所连接的每一组人开始发生变化。让我们把它们放在一起。

>>> def step_through(friend_dict): 
...     new_friend_dict = friend_dict.copy() 
...     for person in friend_dict: 
...         for friend in friend_dict[person].copy():  
...             new_friend_dict[person].update(friend_dict[friend])  
...     if new_friend_dict != friend_dict: 
...         return step_through(friend_dict) 
...     else: 
...         return new_friend_dict 
...
>>> step_through(friend_dict)
{0: {0, 5},
 1: {1, 2, 3, 4, 6, 7, 8, 9},
 2: {1, 2, 3, 4, 6, 7, 8, 9},
 3: {1, 2, 3, 4, 6, 7, 8, 9},
 4: {1, 2, 3, 4, 6, 7, 8, 9},
 5: {0, 5},
 6: {1, 2, 3, 4, 6, 7, 8, 9},
 7: {1, 2, 3, 4, 6, 7, 8, 9},
 8: {1, 2, 3, 4, 6, 7, 8, 9},
 9: {1, 2, 3, 4, 6, 7, 8, 9}}

再说一次，你真正想要的是一个breadth-first search，这样你就不会在相同的路径上爬行(参见@BurningKarl的答案)。您还可以通过跟踪每次遍历的路径来改进这一点(1是9的朋友，因为它是x的朋友，x是x的朋友，x是...)。

最后，正如@BurningKarl提到的，使用networkx很容易完成整个过程(您可能必须使用pip install networkx)。

>>> import networkx as nx

>>> persons = [0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 6, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
>>> friends = [5, 2, 3, 4, 6, 8, 1, 4, 6, 7, 9, 1, 6, 8, 1, 2, 6, 7, 9, 0, 1, 2, 3, 4, 8, 2, 4, 9, 1, 3, 6, 2, 4, 7]
>>> friend_dict = {key:{v for i,v in enumerate(friends) if persons[i] == key} for key in set(persons)}

>>> graph = nx.Graph(friend_dict)
>>> list(nx.connected_components(graph))
[{0, 5}, {1, 2, 3, 4, 6, 7, 8, 9}]

Answer 3

Karl和SMcQ的解决方案都很好。我用这个解决了我的问题。https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/。我还尝试了其他方法，所有这些方法都工作得很好。