Verdoppelung in arrays vermeiden

[bjoernh]

Ich möchte einen Turnierplanmanager erstellen. Dazu hab ich folgenden Ansatz:

Code: Alles auswählen

teams = ["a","b","c", "d", "e"]
matches =[]
for x in range(len(teams)):
    for y in range(x+1,len(teams)):
        matches.append(teams[x]+teams[y])
print(matches)

Das "print(matches" liefert dann:

Code: Alles auswählen

['ab', 'ac', 'ad', 'ae', 'bc', 'bd', 'be', 'cd', 'ce', 'de']

Dies sind alle Mögliche Paarungen. Allerdings ist per Algorithmus gegeben, dass zuerst alle a-Spiele kommen, dann die übrigen b-Spiele, usw.) Ich möchte vermeiden, dass jedes einzelne Team direkt aufeinanderfolgend spielt. Ich weiß, dass man für gerade Anzahl von Teams per Färbungsalgorithmus (z.B. bei https://inf-schule.de/algorithmen/grund ... lgorithmen) einen Spielplan ohne Dopplungen erhält. Allerdings funktioniert dies nur für gerade len(teams). Kennt jemand hier ein konkretes Vorgehen?

[__blackjack__]

@bjoernh: Das wird nicht gehen. Schau Dir doch einfach mal das Beispiel mit drei Paarungen an und versuch die manuell so anzuordnen, dass Deine Bedingung erfüllt ist.

[imonbln]

Man iteriert in Python nicht über die Indizes! Stattdessen sollte man in Python die For-schleife direkt den nächsten wert vom iterable ausgeben lassen. Allerdings ist das hier gar nicht so leicht, denn die innere Schleife startet immer bei einer Mannschaft weiter in der Zukunft. Ich glaube, ich würde das daher so implementieren:

Code: Alles auswählen

for cnt, red_team in enumerate(teams, 1):
      for blue_team in teams[cnt:]:
            matches.append( f"{red_team}{blue_team}")
print(matches)

Noch besser ist es aber, es nicht zu implementieren, sondern stattdessen aus den itertools die combinations zu nehmen, dann kann man die Match-Paarung mit einem Einzeiler erzeugen.

Code: Alles auswählen

matches = [''.join(x) for x in itertools.combinations(teams, 2)]

[imonbln]

Ein wenig fairer könntest du es machen, wenn du die Paarungen, welche die Combination anspuckt, durch einen Roundrobin verteilen lässt, auch dann müssen immer noch ein paar Teams gleich hintereinander spielen, aber wenigstens muss a nicht ohne Unterbrechung Spielen während die anderen Regenerieren.

Das geht dann ungefähr so, denn Round robin habe ich aus den itertools Rezepten.

Code: Alles auswählen

import collections
import itertools

def roundrobin(*iterables):
    "Visit input iterables in a cycle until each is exhausted."
    # roundrobin('ABC', 'D', 'EF') → A D E B F C
    # Algorithm credited to George Sakkis
    iterators = map(iter, iterables)
    for num_active in range(len(iterables), 0, -1):
        iterators = itertools.cycle(itertools.islice(iterators, num_active))
        yield from map(next, iterators)


def tournament(teams):
    matches = collections.defaultdict(list)
    for red_team, blue_team in itertools.combinations(teams, 2): 
        matches[red_team].append( (red_team, blue_team))
    yield from roundrobin(*matches.values())


def main():
    teams = ["a","b","c", "d", "e"]
    for red_team, blue_team in tournament(teams):
        print(red_team, blue_team)


if __name__ == '__main__':
    main()

[__blackjack__]

Wenn es in den Rezepten steht, dann ist es normalerweise schon fertig als Code in `more_itertools`.