Сортировка списков с несколькими ограничениями

Question

Есть 6 игроков, участвующих в дуэт-системном спорте, я пытаюсь найти алгоритм для соответствия лучшим парам.

Ограничения следующие: Игрок не может воспроизводить плеер, который находится в его списке «Невозможно воспроизвести», и ему необходимо сыграть лучший матч в соответствии с списком «Лучший фильм». Таким образом, лучший матч 1-го игрока для следующего раунда - игрок 3, а худший - игрок 4.

Я нахожусь в разумной форме, чтобы иметь оптимальную систему сопряжения.

 
Player 1: Cannot Play(1,2,6) ; Best Play(3,5,4) 
Player 2: Cannot Play(2,1,5) ; Best Play(4,3,6) 
Player 3: Cannot Play(3,2,4) ; Best Play(1,5,6) 
Player 4: Cannot Play(4,3,6) ; Best Play(2,6,1) 
Player 5: Cannot Play(5,3,6) ; Best Play(3,4,1) 
Player 6: Cannot Play(6,4,5) ; Best Play(2,1,3) 

Примечание В этом примере вы можете быстро назначить между P1 до P3, а затем P2 до P4, а затем вы застряли, потому что P5 не может играть P6.

РЕДАКТИРОВАТЬ: Я пробовал до сих пор. Однако я пытаюсь понять общий подход к проблеме, а не решение для моего кода. Моя проблема в коде является то, что иногда последняя пара не может играть против друг друга, и я получаю не назначая для них:

swissPair=[] 
cannot_play_against=[] 
DB = psycopg2.connect("dbname=tournament") 
c = DB.cursor() 

standings = playerStandings() 

# Assigning pairs 
for player in standings: 

    # Building a list of players player[0] won't be playing: 
    # 1. Players already played 2. Players that are already assigned 

    c.execute("SELECT loser from matches where winner=" + str(player[0])) 
    lost_against = list(c.fetchall()) 
    c.execute("SELECT winner from matches where loser=" + str(player[0])) 
    won_against = list(c.fetchall()) 
    already_assigned = [(i[0],) for i in swissPair] + [(i[2],) for i in swissPair] 
    cannot_play_against = set(won_against + lost_against + already_assigned) 

    # Making sure the player is not already assigned 
    if (player[0],) not in already_assigned: 

     # Creating a table sorted by (absolute winnings-player winnings) 
     # By doing it we find opponents at the player's level 
     c.execute("SELECT id, name, wins, abs(wins-" + str(player[2]) + ") from standings order by abs") 
     list_by_distance = list(c.fetchall()) 
     # Removing those who can't play the player and the player himself 
     can_play_against = [z for z in list_by_distance if z[:1] not in cannot_play_against and z[0]<>player[0]] 

     if len(can_play_against)>0: swissPair.append((player[0],player[1],can_play_against[0][0],can_play_against[0][1])) 

     # In case all the pairs has been assigned: break 
     if len(swissPair) == len(standings)/2: break 

DB.close() 
return swissPair 

Answer 1

Игнорирование код и просто говорить процесс:
Вы можете попробовать вручную разбивая ранее спариваний, если в дальнейшем нет выбора; то есть:

1. P1 соответствует P3, назначает.
2. P2 соответствует P4, назначает.
3. (P3 уже назначена.)
4. (P4 уже назначена.)
5. P5 имеет ни один из кандидатов не остались - лучший кандидат P3. Разрыв P1/P3, новая пара - P5/P3. P1 снова не назначен.
6. P6 соответствует P1, назначает.

Я не уверен, что этот процесс гарантированно завершить во всех возможных сценариев, вы могут должны продлить его, чтобы следить за предыдущими парами, которые получили из и предотвратить их от того, чтобы создать заново, чтобы остановить циклы от происходящего.