Algoritmo per raggruppare gli oggetti

Question

Ho le seguenti classi:

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

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

mio input è una lista di oggetti sportivi, per semplicità considerare i seguenti esempi:

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

devo creare a List<List<>>, in modo tale che la lista interna sia tutti gli sport che hanno almeno 1 giocatore comune (la proprietà transitiva si applica qui). Nell'esempio sopra, l'output dovrebbe essere,

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

Qualche suggerimento su come risolvere questo e/o pseudo-codice?

Answer 1

Suoni come problema grafico. Quello che vorrei fare è la seguente:

1. Creare un grafico (non orientato) dove le persone sono i nodi, finora senza bordi
2. andrei attraverso lo sport e per tutti gli sport che vorrei fare un bordo tra le persone se giocare lo stesso sport (ad esempio quando si elabora lo sport 1 si creerebbe margine tra Sam e Dylan, quando si tratta dello sport 3, farebbe un vantaggio tra Dylan e Carter)
3. Come ultimo passaggio prenderei i componenti del grafico finale (in il tuo esempio Sam-Dylan-Carter-Frank, Kane-Michael, Tyler-John) e "applica loro gli sport" - questo significa che per ogni ragazzo/ragazza nel componente, aggiungerei tutti gli sport che lui/lei fa esimo e la lista "interiore" (preferirei impostare così ogni sport è lì una volta).

Così il grafico sarebbe cresciuta in questo modo:

1. lavorazione Calcio: Sam-Dylan
2. lavorazione Pallacanestro: Sam-Dylan, Tyler-John
3. lavorazione Baseball: Sam -Dylan- Carter, Tyler-John
4. Elaborazione di hockey: Sam-Dylan-Carter, Tyler-Joh n, Kane-Michael
5. lavorazione Calcio: Sam-Dylan-Carter-Frank, Tyler-John, Kane-Michael

e "si applicano sport":

1. Sam (Calcio), Dylan (Calcio, Baseball), Carter (Baseball, Calcio), Frank (Calcio) => (Calcio, Baseball, Calcio)
2. Tyler (Basket), John (Pallacanestro) => (Pallacanestro)
3. Kane (Hockey), Michael (Hockey) => (Hockey)

==> (Calcio, Baseball, Calcio), (Pallacanestro), (Hockey)

Edit: Opzionalmente è può ottimizzare l'algoritmo che per ogni componente, ti ricorderai a quali sport sono legati. In altre parole, quando si crea un bordo, si aggiunge uno sport alla collezione di sport del componente. Quindi il passaggio "applica sport" non sarà più necessario. Una regola semplice, quando due componenti si connettono, si raccoglieranno le collezioni sportive prima di aggiungere un nuovo sport. L'algoritmo poi sarebbe andato:

1. lavorazione Calcio: Sam-Dylan (Calcio)
2. lavorazione Pallacanestro: Sam-Dylan (Calcio), Tyler-John (Pallacanestro)
3. Processing Baseball: Sam-Dylan- Carter (Calcio, Baseball ), Tyler-John (Pallacanestro)
4. lavorazione Hockey: Sam-Dylan-Carter (Calcio, Baseball), Tyler-John (Pallacanestro), Kane-Michael (Hockey)
5. lavorazione Calcio: Sam-Dylan-Carter-Frank (Calcio, Baseball, Calcio ), Tyler-John (Pallacanestro), Kane-Michael (Hockey)

Si prega di notare che l'uso del grafico non è necessario. Puoi ancora andare via con raccolte semplici ma il grafico sembrava il modo più pulito e il modo migliore per farlo. Inoltre, consente un'ulteriore estensibilità perché modella i dati in modo naturale - ad esempio puoi scoprire perché Sam è in gruppo con Carter (perché il loro amico comune Dylan gioca uno sport diverso con entrambi).

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

Ho svolto il lavoro con un approccio simile a quello dichiarato da @Sababrata.

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

Ho implementato il codice per voi. Se vedi il metodo "gruppo", capiresti. Quindi questi non saranno necessari per lo pseudo-codice. l'uscita sarà:

[[Calcio, Baseball, Calcio], [Pallacanestro], [Hockey]]

Ho anche aggiunto una nuova voce:

sport6 ​​- Pallamano, < Tyler, Reza>

Per testare l'algoritmo per più di una lista comune. Uscita sarà:

[[Calcio, Baseball, Calcio], [Pallacanestro, Pallamano], [Hockey]]

Ecco il codice:

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; 
} 

Si noti inoltre che Ho usato Java-8 Streams API nel mio codice. Quindi, se non stai usando Java-8, cambia quella linea.

Buona fortuna!