java - Finding combinations of a HashSet of Strings -
i have hashmap<string, hashset>. string stores name of person, , hashset stores list of people friends person.
key<string> value<hashset> dave steve steve dave bob dalton dalton bob, sue anne sue sue dalton, anne in above data, dave friends steve (line 1 , 2). line 4, dalton friends bob , sue. however, bob , sue not friends. program needs input bob , sue friends. in other words, bob should added sue's friend list , sue should added bob's friends list. however, dalton's friends list may have infinite amount of people. not allowed store friend list data array or arraylist.
one solution considering (but haven't tried) edit read(string name1, string name2) method. (note: in runner class, whenever method called, called read(name1, name2) , read(name2, name1)) in short, method reads in 2 friendships , adds in friendship map. in else block (if name1 key in hashmap), thinking add in code take existing friendlist (which have 1 value) of name1 , call read again.
here's read method, if need
private map<string, set> friends; // adds 2 friends, name1 , name2, hashmap of friendships public void read(string name1, string name2) { // temporary hashset in case person has more 1 friend set<string> strset = new hashset<string>(); if (!friends.containskey(name1)) { strset.add(name2); friends.put(name1, strset); } else { strset.clear(); // set strset current friendlist of name1 strset = friends.get(name1); strset.add(name2); // make new entry in hashmap name1 , updated friend list friends.put(name1, strset); } } another solution (going off of title of thread) find possible combinations of friendlist. e.g. if dalton has bob, sue, , dave in friend list, have method finds possible combinations of 2 way friendships (remember, order doesn't matter):
bob sue bob dave sue dave however, don't know how code this. suggestions?
the second solution described equivalent disjoint-set data structure. friends end being in sets, in each set friends else in set , no 1 else.
the tricky part of implementing data structure merging 2 sets when discover 2 people in different sets friends.
this naive implementation:
public class disjointfriendset { private final map<string, set<string>> persontofriends = new hashmap<>(); /** * includes person in group of friends. * * if no friendships have been registered person, returns set * containing 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 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 , 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)); } } }