Algorytm do grupy obiektów

Question

Mam następujących klas:

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

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

Moje wejście znajduje się lista obiektów sportowych, dla prostoty rozważyć poniższe przykłady:

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

muszę tworzyć a List<List<>>, tak że lista wewnętrzna to wszystkie dyscypliny sportowe, które mają co najmniej 1 wspólnego gracza (tutaj obowiązuje funkcja przechodnia). W powyższym przykładzie dane wyjściowe powinny być:

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

Jakieś sugestie dotyczące rozwiązania tego i/lub pseudokodu?

Answer 1

Brzmi jak problem z wykresem dla mnie. Co chciałbym zrobić, to następujące elementy:

1. Tworzenie wykresu (undirected), gdzie ludzie są węzły, jak dotąd bez krawędzi
2. pójdę poprzez sport i za każdym sporcie zrobiłbym krawędź między ludźmi, jeśli grać w ten sam sport (na przykład przy przetwarzaniu sportu 1 tworzyłby krawędź pomiędzy Samem i Dylanem, gdy przetwarzałby sport 3, robiłby przewagę między Dylanem a Carterem)
3. Jako ostatni krok brałem komponenty końcowego wykresu (w twój przykład Sam-Dylan-Carter-Frank, Kane-Michael, Tyler-John) i "zastosuj do nich sport" - oznacza to, że dla każdego chłopca/dziewczyny w komponencie dodaję wszystkie sporty, które on/ona robi th e "wewnętrzna" lista (wolałbym ustawić tak, aby każdy sport był tam raz).

Więc wykres wzrośnie w ten sposób:

1. tworzenie nożnej: Sam-Dylan
2. tworzenie Koszykówka: Sam-Dylan Tyler-John
3. Processing Baseball: Sam -Dylan- Carter, Tyler-John
4. Przetwarzanie w hokeja: Sam-Dylan-Carter, Tyler-Joh n, Kane-Michael
5. tworzenie Piłka nożna: Sam-Dylan-Carter- Frank, Tyler-Jan-Michael Kane

i "sport": zastosowanie

1. Sam (Piłka nożna), Dylan (piłka nożna, baseball), Carter (baseball, piłka nożna), Frank (piłka nożna) => (piłka nożna, baseball, piłka nożna)
2. Tyler (koszykówka), John (koszykówka) => (koszykówka)
3. Kane (na lodzie), Michael (Hokej) => (na lodzie)

==> (piłka nożna, baseball, piłka nożna), (koszykówka), (Hokej)

Edit: Opcjonalnie ty może zoptymalizować algorytm, który dla każdego komponentu będzie pamiętał, jakie sporty są z nim powiązane. Innymi słowy, tworząc krawędź, dodasz sport do kolekcji sportowej tego komponentu. Wtedy krok "zastosuj sport" nie będzie już potrzebny. Jedna prosta zasada, kiedy dwa komponenty zostaną połączone, przed dodaniem nowego sportu połączycie kolekcje sportowe. Algorytm potem pójdzie:

1. tworzenie nożna: Sam-Dylan (Piłka nożna)
2. tworzenie Koszykówka: Sam-Dylan (piłka nożna), Tyler-John (Koszykówka)
3. tworzenie Baseball: Sam-Dylan- Carter (piłka nożna, Baseball), Tyler-John (koszykówka)
4. tworzenie Hokej: Sam-Dylan-Carter (piłka nożna, baseball), Tyler-John (koszykówka), -Michael Kane (na lodzie)
5. tworzenie Piłka nożna: Sam-Dylan-Carter- Frank (piłka nożna, baseball, piłka nożna ), Tyler-John (koszykówka), Kane-Michael (Hokej)

Należy pamiętać, że użycie wykresu nie jest konieczne. Wciąż można odejść z prostymi kolekcjami, ale wykres wydawał się najczystszym sposobem i optymalnym algorytmem do zrobienia tego. Pozwala to również na dalszą rozbudowę, ponieważ modeluje dane w naturalny sposób - na przykład możesz dowiedzieć się, dlaczego Sam jest w grupie z Carterem (ponieważ ich wspólny przyjaciel Dylan gra z nimi obaj).

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

Zrobiłem pracę z podobnym podejściem, jak stwierdził @Somabrata.

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

Zaimplementowałem kod dla ciebie. Jeśli zobaczysz metodę "grupa", zrozumiesz. Więc nie będzie potrzeby pseudokodu. wyjście będzie:

[[piłka nożna, baseball, piłka nożna], [Koszykówka], [Hockey]]

Dodałem też nowy wpis:

sport6 ​​- Piłka ręczna, < Tyler, Reza>

Aby przetestować algorytm dla więcej niż jednej wspólnej listy. Wyjście będzie:

[[piłka nożna, baseball, piłka nożna], [koszykówka, piłka ręczna], [Hockey]]

Oto kod:

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

zauważyć również, że Użyłem API Java-8 Streams w moim kodzie. Więc jeśli nie korzystasz z Java-8, zmień tę linię.

Powodzenia!