[PHP] Algorytm - przechodniość Opcje

[Miszczklawiatury]

Witam,

Od paru dobrych godzin zmagam się z napisaniem w PHP następującego logarytmu:

Mam bazę w MySQL, w której jest tabela z dwoma kolumnami. W pierwszej kolumnie jest zapisany zwycięzca danego meczu, w drugiej przegrany.

Przykładowo, mam w niej trzy rekordy:

1 2
2 3
3 7

Algorytm ma dodać do tej tabeli wszystkie rekordy, które wynikają z przechodniości. To znaczy, kontynuując powyższy przykład, tabela ma na końcu wyglądać tak:

1 2
2 3
3 7
1 3
1 7
2 7

Oczywiście rekordy nie mogą się powtarzać i nie może w niej być jednocześnie rekordów np. 1 2 i 2 1

Ktoś ma pomysł? Kilka moich ostatnich prób kończyło się na nieskończonych pętlach, powtórzeniach albo innych błędach.

Być może ktoś będzie potrzebował tych informacji:
1. Liczba drużyn jest znana przed wykonaniem algorytmu. Niech będzie x.
2. Oczywiście algorytm będzie wykonywany tylko wtedy, gdy w tabeli z wynikami są co najmniej 2 rekordy.
3. Ten algorytm będzie rdzeniem projektu, który buduje. Fajnie by więc było, gdyby był na tyle wydajny, żeby obsłużyć kilkunastu użytkowników i
zliczanie wyników kilkudziesięciu drużyn.

Wystarczy mi ogólny opis algorytmu.

Z góry dzięki.

Ten post edytował Miszczklawiatury 2.06.2013, 19:03:36

[Miszczklawiatury]

Dobre pytanie.

Taka sytuacja nie zajdzie - program wybiera zawsze taki mecz, żeby niemożliwie było istnienie więcej niż jednego mistrza. Tzn. w sytuacji

1 2

nie może być meczu 2 vs 1 - bo przecież był.

Natomiast w sytuacji

1 2
2 3

algorytm ma dodać mecz 1 3 do tabeli przed wybraniem następnego meczu. Wtedy też nie może być meczu 1 vs 3 albo 3 vs 1 bo jego wynik jest w tabeli.

Tak czy inaczej, chyba wreszcie mi się udało napisać coś co działa (IMG:style_emoticons/default/smile.gif) Dziękuję wszystkim za chęć pomocy.