Object Grouping Algorithm

Question

I have the following classes:

class Sport { private String sportsName; private List<People> peopleWhoPlayThisSport; //... } 

 class People { private String name; private long uniqueId; // ... } 

My entry is a list of sports facilities, for simplicity, consider the following examples:

 sport1 - Football, <Sam, Dylan> sport2 - Basketball, <Tyler, John> sport3 - Baseball, <Carter, Dylan> sport4 - Hockey, <Kane, Michael> sport5 - Soccer, <Carter, Frank> 

I need to create a List<List<>> , so the internal list is all sports that have at least one common player (the Transitive property is used here). In the above example, the output should be

 <<sport1,sport3,sport5> , <sport2> , <sport4>> 

Any suggestions for solving this and / or pseudo code?

Answer 1

It seems to me that the problem is a graph. I would do the following:

• Create a graph (non-oriented), where people are nodes, still without borders
• I would go in for sports, and for each sport I could make an advantage between people if they play in the same sport (for example, when processing sport 1, this will create an advantage between Sam and Dylan when he does sport 3, between Dylan and Carter)
• As a last step, I would take the components of the final graph (in your example Sam-Dylan-Carter-Frank, Kane-Michael, Tyler-John) and “apply sports to them” - this means that for each boy / girl in the component, I would add all the sports that he / she makes to the "internal" list (I would prefer that this be so, each sport was once).

So, the graph will grow as follows:

• Soccer Handling: Sam-Dylan
• Basketball Handling: Sam Dylan, Tyler John
• Baseball Handling: Sam Dylan - Carter , Tyler John
• Hockey Hockey: Sam Dylan Carter, Tyler John, Kane Michael
• Soccer Handling: Sam Dylan Carter - Frank , Tyler John, Kane Michael

And the "application of sports":

• Sam (soccer), Dylan (soccer, baseball), Carter (Baseball, soccer), Frank (Soccer) => (soccer, baseball, soccer)
• Tyler (Basketball), John (Basketball) => (Basketball)
• Kane (Hockey), Michael (Hockey) => (Hockey)

==> (Football, Baseball, Football), (Basketball), (Hockey)

Edit: If you wish, you can optimize the algorithm, which for each component, you will remember which sports are associated with it. In other words, when creating an edge, you add sports to the collection of sports components. Then the step “apply sport” is no longer needed. One simple rule, when two components are connected, you combine sports collections before adding a new sport. Then the algorithm will go:

• Soccer Handling: Sam Dylan (Soccer)
• Basketball Handling: Sam Dylan (Soccer), Tyler-John (Basketball)
• Baseball Handling: Sam Dylan - Carter (Soccer, Baseball ), Tyler-John (Basketball)
• Ball hockey: Sam-Dylan-Carter (football, baseball), Tyler-John (Basketball), Kane-Michael (Hockey)
• Soccer Handling: Sam Dylan Carter - Frank (soccer, baseball, soccer ), Tyler-John (Basketball), Kane Michael (Hockey)

Please note that using a schedule is optional. You can still get away with simple collections, but the schedule seemed the cleanest way and the optimal algorithm for this. It also allows you to use additional extensibility because it models the data in a natural way - for example, you can find out why Sam is in a group with Carter (because their mutual friend Dylan plays with them in different sports).

Answer 2

 Create HashMap<People, List<Sport>> pList for each Sport s in sportList for each People p in peopleWhoPlayThisSport if p present in pList, pList.get(p).add(s) else, pList.put(p,s) Iterate on pList If list size of Sport Objects for a People > 1 Add to Set of Sport Objects which have at least 1 common Create another Set from first sportList Do a Set minus to get Sports without any common player 

Answer 3

I did a similar approach, as @Somabrata stated.

 Map<People, Set<Sport>> mapping = new HashMap<>(); for (Sport s : sports) { for (People p : s.getPeopleWhoPlayThisSport()) { Set<Sport> sportByPeople = mapping.get(p); if (sportByPeople == null) { sportByPeople = new HashSet<>(); mapping.put(p, sportByPeople); } sportByPeople.add(s); } } List<Set<Sport>> groupings = new ArrayList<>(); outer: for (Set<Sport> sportSet : mapping.values()) { for (Set<Sport> group : groupings) { for (Sport s : sportSet) { if (group.contains(s)) { group.addAll(sportSet); continue outer; } } } groupings.add(sportSet); } System.out.println(groupings); 

Answer 4

I have implemented the code for you. If you see the "group" method, you will understand. Thus, this will not be necessary for pseudocode. The output will be:

[[Football, Baseball, Football], [Basketball], [Hockey]]

I also added a new entry:

sport6 ​​- Handball, Tyler, Resa>

To check the algorithm for more than one common list. The output will be:

[[Football, Baseball, Football], [Basketball, Handball], [Hockey]]

Here is the code:

 public class GroupObjects { int uniqueIdCounter = 1; People p1 = new People("Sam",uniqueIdCounter++); People p2 = new People("Dylan",uniqueIdCounter++); People p3 = new People("Tyler",uniqueIdCounter++); People p4 = new People("John",uniqueIdCounter++); People p5 = new People("Carter",uniqueIdCounter++); People p6 = new People("Kane",uniqueIdCounter++); People p7 = new People("Michael",uniqueIdCounter++); People p8 = new People("Frank",uniqueIdCounter++); People p9 = new People("Reza",uniqueIdCounter++); Sport s1 = new Sport("Football", Arrays.asList(p1,p2)); Sport s2 = new Sport("Basketball", Arrays.asList(p3,p4)); Sport s3 = new Sport("Baseball", Arrays.asList(p5,p2)); Sport s4 = new Sport("Hockey", Arrays.asList(p6,p7)); Sport s5 = new Sport("Soccer", Arrays.asList(p5,p8)); Sport s6 = new Sport("Handball", Arrays.asList(p3,p9)); List<Sport> sports = Arrays.asList(s1,s2,s3,s4,s5,s6); public List<List<Sport>> group(List<Sport> sports){ List<List<Sport>> answerList = new ArrayList<>(); while (!sports.isEmpty()) { List<Sport> common = new ArrayList<>(); List<Sport> toBeRemoved = new ArrayList<>(); List<People> people = new ArrayList<>(); people.addAll(sports.get(0).getPeopleWhoPlayThisSport()); common.add(sports.get(0)); toBeRemoved.add(sports.get(0)); for (int i = 1; i < sports.size(); i++) { for (People p : sports.get(i).getPeopleWhoPlayThisSport()) { if (people.contains(p)) { people.addAll(sports.get(i).getPeopleWhoPlayThisSport()); common.add(sports.get(i)); toBeRemoved.add(sports.get(i)); break; } } } sports = sports.stream().filter(sp->!toBeRemoved.contains(sp)).collect(Collectors.toList()); answerList.add(common); } return answerList; } public static void main(String[] args) { GroupObjects groupObjects = new GroupObjects(); List<List<Sport>> answer = groupObjects.group(groupObjects.sports); System.out.println(answer); } class Sport { ... @Override public String toString() { return sportsName; } 

Also note that I used the Java-8 Streams API in my code. Therefore, if you are not using Java-8, change this line.

Good luck