排序具有多个限制的列表

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匹配，赋值。你知道吗

我不确定这个过程在所有可能的情况下都能保证完成，你可能需要扩展它来跟踪早期的配对，防止它们被重新创建来阻止循环的发生。你知道吗