我有一个HashMap<String, HashSet>
。String
存储该人的姓名,HashSet
存储与该人是朋友的人的列表。
KEY<STRING> VALUE<HASHSET>
Dave Steve
Steve Dave
Bob Dalton
Dalton Bob, Sue
Anne Sue
Sue Dalton, Anne
在上述数据中,Dave与Steve是朋友(第1行和第2行)。在第四行,道尔顿是鲍勃和苏的朋友。然而,鲍勃和苏不一定是朋友。程序需要将Bob和Sue输入为好友。换句话说,Bob应该添加到Sue的朋友列表中,Sue应该添加到Bob的朋友列表。然而,道尔顿的朋友列表可能有无限多的人。我也不被允许将朋友列表数据存储到CCD_ 4或CCD_。
我正在考虑(但尚未尝试)的一个解决方案是编辑我的read(String name1, String name2)
方法(注意:在我的runner类中,每当调用此方法时,它都被称为read(name1, name2)
和read(name2, name1)
)简而言之,此方法读取两个友谊并将友谊添加到映射中。在else
块中(如果name1
已经是HashMap
中的key
),我想添加代码来获取name1
的现有友好列表(它将只有一个值),然后再次调用read
。
如果你需要的话,这是read
方法
private Map<String, Set> friends;
// Adds two friends, name1 and name2, to the HashMap of friendships
public void read(String name1, String name2)
{
// Temporary HashSet in case a person has more than one friend
Set<String> strSet = new HashSet<String>();
if (!friends.containsKey(name1))
{
strSet.add(name2);
friends.put(name1, strSet);
}
else
{
strSet.clear();
// Set strSet to the current friendlist of name1
strSet = friends.get(name1);
strSet.add(name2);
// Make a new entry in the HashMap with name1 and the updated friend list
friends.put(name1, strSet);
}
}
另一个解决方案(脱离本线程的标题)是找到友好列表的所有可能组合。例如,如果道尔顿的朋友列表中有Bob、Sue和Dave,我可以找到一种方法,找到所有可能的双向友谊组合(记住,顺序无关紧要):
Bob Sue
Bob Dave
Sue Dave
但是,我不知道如何对其进行编码。有什么建议吗?
您描述的第二个解决方案等效于一个不相交的集合数据结构。你的朋友最终是在片场,每个片场的每个人都是该片场其他人的朋友,而不是其他人。
实现这种数据结构的棘手部分是,当您发现不同集合中的两个人是朋友时,合并两个集合。
这是一个幼稚的实现:
public class DisjointFriendSet {
private final Map<String, Set<String>> personToFriends = new HashMap<>();
/**
* Includes the person themselves in their group of friends.
*
* If no friendships have been registered for this person, then returns a set
* containing just themselves.
*
* @param person
* @return
*/
public Set<String> getFriends(String person) {
if(personToFriends.containsKey(person)) {
return personToFriends.get(person);
} else {
final Set<String> result = new HashSet<>();
result.add(person);
return result;
}
}
public void addFriendship(String person1, String person2) {
final Set<String> friends1 = getFriends(person1);
final Set<String> friends2 = getFriends(person2);
if(friends1 == friends2) {
return;
} else {
personToFriends.put(person1, friends1);
friends1.addAll(friends2);
for(String person: friends2) {
personToFriends.put(person, friends1);
}
}
}
/**
*
* @return All unique friendship groups
*/
public Collection<Set<String>> getAllFriendshipGroups() {
return new HashSet<>(personToFriends.values());
}
public static void main(String[] args) {
final DisjointFriendSet disjointFriendSet = new DisjointFriendSet();
disjointFriendSet.addFriendship("Alice","Beowulf");
disjointFriendSet.addFriendship("Charity","Donald");
disjointFriendSet.addFriendship("Eduardo","Frank");
disjointFriendSet.addFriendship("Grendel","Harriet");
System.out.println("Friendship groups: "+disjointFriendSet.getAllFriendshipGroups());
System.out.println("Adding friendship between Grendel and Beowulf");
disjointFriendSet.addFriendship("Grendel","Beowulf");
System.out.println("Friendship groups: "+disjointFriendSet.getAllFriendshipGroups());
System.out.println();
for(String person: new String[]{"Alice","Beowulf","Charity","Donald","Eduardo","Frank","Grendel","Harriet","Zod"}) {
System.out.println(person+"'s friends: "+disjointFriendSet.getFriends(person));
}
}
}
这里有一种伪代码方法(我稍后可以查找Java)
假设在每次添加时,朋友的所有朋友都是正确匹配的。
接受这两个新输入,并创建一个他们所有朋友以及输入值的临时集合。
对于临时集合中的每个值,将其他值添加为好友。(一个集合应该只维护唯一的值,但如果需要,您可以显式检查)。
这可能不是最有效的解决方案(在每个步骤中,一半的添加都是重复的),但这应该是一个起点。
Func (friend1, friend2)
tempSet = masterSet(friend1).Hashset
UNION
masterSet(friend2).Hashset
UNION
friend1, friend2
foreach (friend in tempSet)
foreach(otherFriend in tempSet - friend)
friend.AddFriend(otherFriend)
otherFriend.AddFriend(friend)