Parowanie zawodników bez ponownego trafienia na przeciwnika

Cześć,
pracuję nad systemem parowania zawodników z wykluczeniem możliwości trafienia na tego samego przeciwnika podczas tych samych zawodów w kolejnych rundach.
Każdy zawodnik w uproszczeniu wygląda tak:

[sn:Ania, pn:9, op:(8,),

sn - nazwa zawodnika,
pn - pairing number, numer zawodnika podczas zawodów,
op - lista przeciwników na których trafił zawodnik w poprzednich rundach.
Zawodnik to klasa dzięki czemu możemy wywołać np zawodnik.can_play([p1]) gdzie p1 to inny zawodnik, zwraca True jeżeli mogą grać i False jeżeli już wcześniej grali

Stworzyłem testowych zawodników i napisałem wstępne parowanie. Teraz muszę sprawdzić czy wszystkie pary mogą ze sobą grać. Wstępne parowanie wygląda tak:

[sn:Ania, pn:9, op:(8,), sn:Błażej, pn:7, op:(99,), ch:(-1,)]
[sn:Andrzej, pn:8, op:(9,), sn:Borys, pn:6, op:(88,), ch:(1,)]
[sn:Artur, pn:1, op:(2,), sn:Bożena, pn:3, op:(4,), ch:(1,)]
[sn:Alicja, pn:2, op:(1, 3, 4, 5, 7, 8, 9), sn:Brajan, pn:5, op:(0,),]

W ostatniej parze jest zawodnik Alicja, zrobiłem u niej taką listę przeciwników żeby jedynym możliwym przeciwnikiem był Borys pn=6.

Walczę z tym od kilku dni, powstało kilka wersji a teraz mam coś takiego:

Dla czytelności skróciłem i poprzestawiałem kolejność:

	def pairGroup(self):
        self.players.sort(key=lambda Player: Player.rating, reverse=True)
        self.firstPairing()
        bracketPaired = True
        for index, item in enumerate(self.pairs):
            if(item[0].can_play([item[1]])==False):
                result1 = self.searchS2(index,  item[0])
                if(result1==False):
                    result2 = self.searchS1(index, item[0])
                    if(result2==False):
                        bracketPaired = False
                        break


    def searchS1(self, index, p1):
        found = False
        players = self.getPlayersFrom(index, 0) //Bierzemy liste zawodników w odpowiedniej kolejnosci z S1
        player.remove(p1)
        for p2 in players:
            if p1.can_play([p2]):
                p2index = self.playerIndex(p2)
                tmp = self.pairs[index][1]
                self.pairs[index][1] = self.pairs[p2index][0]
                self.pairs[p2index][0] = tmp
                found = True
				
    def searchS2(self, index, p1):
        found = False
        players = self.getPlayersFrom(index, 1) //Bierzemy liste zawodników w odpowiedniej kolejnosci z S2
        for p2 in players:
            if p1.can_play([p2]):
                p2index = self.playerIndex(p2)
                tmp = self.pairs[index][1]
                self.pairs[index][1] = self.pairs[p2index][1]
                self.pairs[p2index][1] = tmp
                found = True

w pairGroup najpierw tworzymy pierwsze parowanie, któe znajduje się w self.pairs. Następnie sprawdzamy przeciwników w każdej parze. Jeżeli grali już ze sobą to szukamy odpowiedniego przeciwnika.
Każda para wygląda tak (S1, S2). Najpierw wywołujemy searchS2 a jeżeli tam nie znaleziono przeciwnika to searchS1. SearchS2 wyszukuje najpierw po zawodnikachS2 a potem searchS1 sprawdza po zawodnikach S1. Utrudniłem to sobie trochę bo sprawdzanie musi być w odpowiedniej kolejności dlatego self.getPlayersFrom zwraca zawodników odpowiedniej strony we właściwej kolejności a self.playerIndex zwraca index pary znalezionego przeciwnika żeby poprawnie dokonać zamiany.
Sprawdzanie powinno odbywać się w takiej kolejności:

Najpierw od przeciwnika, który nie pasuje w dół, potem w górę a jeżeli nie ma to po stronie zawodnika dla którego szukamy oczywiście z pominięciem jego samego.

I w sumie w końcu zadziałało bo otrzymalem parowanie z jedyną możliwą parą dla Alicji:

[sn:Ania, pn:9, op:(8,), sn:Błażej, pn:7, op:(99,)]
[sn:Andrzej, pn:8, op:(9,), sn:Brajan, pn:5, op:(0,)]
[sn:Artur, pn:1, op:(2,), sn:Bożena, pn:3, op:(4,)]
[sn:Alicja, pn:2, op:(1, 3, 4, 5, 7, 8, 9), sn:Borys, pn:6, op:(88,)]

Czuję, że na bank nie jest to optymalne rozwiązanie i jest o wiele łatwiejsze i coś mi umknęło (chyba sprawdzanie czy druga para może ze sobą grać po zamianie miejsc). Proszę Was więc o pomoc. Jak w najprostszy sposób sparować zawodników tak żeby pary zawierały przeciwników, którzy się wcześniej nie spotkali?

Umknęło Ci itertools.combinations ;)

https://docs.python.org/3.8/library/itertools.html#itertools.combinations

Nie umknęło ;) Przy tym rozwiązaniu musiałbym wygenerować wszystkie możliwe kombinacje i brute forcem sprawdzać po kolei, która pasuje ;) Zakładając, że będzie np 150 zawodników to liczba kombinacji robi się dosyć spora. Poza tym chciałbym zachować chociaż troszeczkę reguł przy parowaniu graczy.
No chyba, że znowu coś pominąłem ;)

Teraz to chyba mi coś umknęło, przejrzałem posta i odniosłem wrażenie, że problem sprowadza się do samego uzyskania tych niepowtarzalnych par ;)

Jakie ogólnie masz założenia?

• czy cokolwiek innego niż fakt, że dwaj zawodnicy już się zmierzyli w poprzednich rundach może całkowicie wykluczyć dobranie ich w parę?
• w którym momencie jesteś w stanie określić, że danym dwóm zawodnikom wolno będzie zagrać w bieżącej rundzie?
• wszyscy zawodnicy grają do końca / jest możliwość eliminacji?
• ile jest rund w stosunku do zawodników? to jakoś zależy od ich liczby?
• istnieje jakiś 'preferowany' sposób dobierania w pary i preferowana kolejność tworzenia par, na przykład na podstawie zbliżonych wyników?

Może zamiast dzielić na dwie pod-grupy (od razu mówię - nie wiem czemu dwie i na jakiej zasadzie :P ) i koniec, mógłbyś każdorazowo rozdzielać pary do dwóch podgrup (np. zwycięzcy i przegrani). W każdej podgrupie miałbyś zawsze zawodników, którzy ze sobą jeszcze nie grali. Nadal mógłbyś szukać im par w innych podgrupach, dość łatwo sprawdzać czy w danej innej podgrupie jest w ogóle co szukać, same podgrupy jakoś szeregować i np. zaczynać od sąsiednich podgrup, czy coś.