Wie erstellt man eine gleichmäßige Verteilung über mehrere Sets?

Question

Dies ist für ein Hobby-Projekt und wird mit Python implementiert werden, aber das ist nicht wirklich wichtig. Ich suche hauptsächlich nach einem guten Algorithmus.

Ich möchte eine Rennveranstaltung mit 2 bis 30 Fahrern veranstalten (num_drivers). Die Veranstaltung hat 2 bis etwa 12 Rennen (num_races), und ich möchte, dass jeder Fahrer eine faire Chance hat, entsprechend seiner Position am Start mit etwas zufälligen Positionierung. Das Problem ist, welche Startpositionen kann ich jedem Fahrer für jedes Rennen zuweisen?

Ein Beispiel: für eine Veranstaltung mit num_races=3 und num_drivers=4 ("A" benannt "D") eine ziemlich gute Konfiguration würde

Race 1: A B C D 
Race 2: C D B A 
Race 3: D B A C 

die Pole Position einen Wert von 1 würde sein, die zweite Position, 2 und so weiter. So gibt diese Einstellung ziemlich gleiche Werte für jeden Fahrer:

A: 1+4+3 = 8 
B: 2+3+2 = 7 
C: 3+1+4 = 8 
D: 4+2+1 = 7 

Am Ende der Summe der Positionen jeden Fahrers im Idealfall die gleichen wie für jeden anderen Fahrer sein sollte. Was wäre ein guter generischer Algorithmus (in Pseudocode) für mein Problem, wenn die Anzahl der Fahrer und die Anzahl der Rennen variieren können? Gibt es überhaupt schon einen Algorithmus?

Answer 1

Ich fand ein gut funktionierendes PHP-Skript auf Github, das das Problem für mich löst. Also, wenn jemand in der Antwort auf mein Problem interessiert ist: https://github.com/FriendlyBaron/GridCreator

Answer 2

Ich würde beginnen mit:

Race 1: A B C D 
Race 2: A B C D 
Race 3: A B C D 

und jede Reihe drehen, indem die Startnummer,

Race 1: A B C D 
Race 2: D A B C 
Race 3: C D A B 

Giving:

A = 1 + 2 + 3 = 6 
B = 2 + 3 + 4 = 8 
C = 3 + 4 + 1 = 8 
D = 4 + 1 + 2 = 7 

, die eine ordentliche Verteilung ist, und über so gut wie du es bekommen wirst (denke ich!) mit dieser Größe eines Pools.

Random wird funktionieren, wenn Sie eine Menge Treiber haben.

Sie könnten dies immer tun, finden Sie Ihre Tiefen und Höhen, und korrigieren Sie Closed-Loop. Also, im obigen Beispiel würde ich bemerken, dass A < < B und C ist, so dass ich das hohe C (4) mit dem nächsten hohen A (3) tauschen und mit 7,8,7,7 enden könnte.

Trivial für diese Größe eines Satzes, aber wahrscheinlich nicht so sehr mit größeren Gittern.

Wenn Sie 4 Rennen hatten, würden Sie DC (10 Punkte für jeden Fahrer) bekommen, aber ich bezweifle, dass Sie 64 Rennen für 64 Fahrer haben wollen (zum Beispiel).

Ein anderer Ansatz wäre, den gewünschten Score für jeden Treiber zu ermitteln und dann rückwärts zu arbeiten, um das Gitter zu generieren. Verwende eine gewichtete Queue - höchste Priorität für den Fahrer mit der niedrigsten Punktzahl - und nimm beim Bestücken des Rasters einfach den Fahrer mit der niedrigsten Punktzahl in die höchste Position. Es ist ein bisschen wie das Müllbeutelproblem, sollte aber einigermaßen gut funktionieren.