Seite 1 von 1
Verdoppelung in arrays vermeiden
Verfasst: Sonntag 7. Juli 2024, 11:23
von 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?
Re: Verdoppelung in arrays vermeiden
Verfasst: Sonntag 7. Juli 2024, 13:23
von __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.
Re: Verdoppelung in arrays vermeiden
Verfasst: Sonntag 7. Juli 2024, 23:03
von 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)]
Re: Verdoppelung in arrays vermeiden
Verfasst: Dienstag 9. Juli 2024, 14:51
von 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()
Re: Verdoppelung in arrays vermeiden
Verfasst: Dienstag 9. Juli 2024, 15:50
von __blackjack__
Wenn es in den Rezepten steht, dann ist es normalerweise schon fertig als Code in `more_itertools`.