Algorithm to group objects

Question

I have the following classes:

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

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

My input is a list of sport objects, for simplicity consider the below examples:

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

I have to create a List<List<>>, such that the inner list is all the sports which have at least 1 common player (Transitive property applies here). In the above example, the output should be,

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

Any suggestions on solving this and/or pseudo-code?

Answer 1

Sounds like graph problem to me. What I would do is following:

1. Create a graph (undirected) where people are nodes, so far without edges
2. I would go through sports and for every sport I would do an edge between people if they play the same sport (for example when processing sport 1 it would create edge between Sam and Dylan, when processing sport 3, it would do edge between Dylan and Carter)
3. As last step I would take components of the final graph (in your example Sam-Dylan-Carter-Frank, Kane-Michael, Tyler-John) and "apply the sports to them" - that means that for every boy/girl in the component, I would add all the sports he/she does into the "inner" list (I would prefer Set so every sport is there once).

So the graph would grow this way:

1. Processing Football: Sam-Dylan
2. Processing Basketball: Sam-Dylan, Tyler-John
3. Processing Baseball: Sam-Dylan-Carter, Tyler-John
4. Processing Hockey: Sam-Dylan-Carter, Tyler-John, Kane-Michael
5. Processing Soccer: Sam-Dylan-Carter-Frank, Tyler-John, Kane-Michael

And "applying sports" :

1. Sam (Football), Dylan (Football, Baseball), Carter (Baseball, Soccer), Frank (Soccer) => (Football, Baseball, Soccer)
2. Tyler (Basketball), John (Basketball) => (Basketball)
3. Kane (Hockey), Michael (Hockey) => (Hockey)

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

Edit: Optionally you may optimize the algorithm that for every component, you will remember what sports are tied to it. In other words, when creating an edge, you will add a sport to the component's collection of sports. Then "apply sports" step won't be no longer needed. One simple rule, when two components get connected, you will union sport collections before adding a new sport. The algorithm then would go:

1. Processing Football: Sam-Dylan(Football)
2. Processing Basketball: Sam-Dylan(Football), Tyler-John(Basketball)
3. Processing Baseball: Sam-Dylan-Carter(Football, Baseball), Tyler-John(Basketball)
4. Processing Hockey: Sam-Dylan-Carter(Football,Baseball), Tyler-John(Basketball), Kane-Michael(Hockey)
5. Processing Soccer: Sam-Dylan-Carter-Frank(Football,Baseball,Soccer), Tyler-John(Basketball), Kane-Michael(Hockey)

Please note that usage of graph is not neccessary. You can still go away with simple collections but the graph seemed as the cleanest way and algorithm-optimal way to do so. It also allows further extensibility because it models the data in natural way - for example you can further find out why Sam is in group with Carter (because their common friend Dylan plays a different sport with both of them).

Answer 2

I implemented the code for you. If you see the method "group", you'd understand. So these will be no need for pseudo-code. The Output will be :

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

I also added a new entry :

sport6 - Handball, < Tyler, Reza >

To test algorithm for more than one common list. Output will be:

[[Football, Baseball, Soccer], [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 notice that I have used Java-8 Streams API in my code. So if you are not using Java-8, change that line.

Good Luck!

Answer 3

I've done the work with 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

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