Python 3朋友的朋友

Question

我正在使用这个函数来寻找两个人之间可能的友谊。友谊系统是以传递的方式工作的，也就是说，如果a是B的朋友，B是C的朋友，那么a就是C的朋友。字典存储初始关系(像图一样(，函数参数是字典和你想确定他们是否是朋友的两个人的名字。

def findfriendship(people, X, Y):
if Y in people[X] or X in people[Y]:
return True
if len(people[X]) != 0:
for friend in people[X]:
return findfriendship(people, friend, Y)
if len(people[Y]) != 0:
for friend in people[Y]:
return findfriendship(people, X, friend)
return False

这是我的代码，我成功地确定了两个人之间可能的友谊，只要其中一个人的朋友列表不是空的，就像这样：

friendships = {'Jordan': ['Shaq'], 'Lebron': [], 'Kobe': [], 'Shaq': ['KD'], 'KD': []}
print(findfriendship(friendships, 'KD', 'Jordan')) -> return True

但我无法解决双方都没有直接朋友的问题，比如：

friendships = {'Jordan': ['Shaq'], 'Lebron': [], 'Kobe': ['KD', 'Lebron'], 'Shaq': ['KD'], 'KD': []}
print(findfriendship(friendships, 'Lebron', 'KD')) -> return False

它返回False，但科比是他们两个的朋友，所以他们应该是朋友。

你们能帮我解决这个问题吗？或者你们知道一个类似的问题，这样我就能理解这种概念吗？感谢您的关注。

Answer 1

如果我们能得到两个人的完整朋友列表，那么检查两个人是否是朋友会很容易。让我们为此编写一个助手：

friendships = {
'Jordan': ['Shaq'], 'Lebron': [],
'Kobe': ['KD', 'Lebron'], 'Shaq': ['KD'], 'KD': [],
"foo": ["bar", "baz"], "bar": [], "baz":[],
}
def buildFriendSet (x, people=None, fSet=None):
people = people or friendships;       # default value
fSet = fSet or set([x] + people[x]);  # Friend Set
changeDetected = False;
for kPerson, vPersonList in people.items():
personList = [kPerson] + vPersonList;
if fSet.issuperset(personList):
pass;
elif fSet.intersection(personList):
fSet = fSet.union(personList);
changeDetected = True;
if not changeDetected:
return fSet;
return buildFriendSet(x, people, fSet);
print(buildFriendSet('KD'));
# Output: {'Shaq', 'Kobe', 'KD', 'Lebron', 'Jordan'}
print(buildFriendSet('foo'))
# Output: {'baz', 'bar', 'foo'}

一旦我们可以计算出任何人的朋友集，检查两个人是否是朋友就很容易了：

def checkFriends (x, y, people=None):
people = people or friendships; # default value
return (x in people[y] or y in people[x] or
x in buildFriendSet(y, people)
);
print(checkFriends('KD', 'Jordan')); # -> True
print(checkFriends('Lebron', 'KD')); # -> True
print(checkFriends('KD', 'foo'));    # -> False

buildFriendSet():背后的逻辑

我们对people进行迭代，并检查朋友集fSet是否发生了变化。如果未检测到任何变化，则返回fSet，保持不变。除此之外，我们一直在寻找更多的朋友。

对于给定的亲密朋友组，例如上面的任何personList，如果组中的每个人都已经在fSet中，则无需更改fSet。这对应于.issuperset(.)检查。

否则，如果personList中至少有一个人已经在fSet中，那么通过关联，其他人也必须在其中！我们分别使用.intersection(.)和.union()来检查和实现这一点。

每个人都是自己的朋友吗

上面的实现假设每个人都是自己的朋友。如果不需要这样的行为，那么使用简单的if-guard和/或fSet.remove(.)就足够了。