算法每n-1天輸入n和輸出對

Question

劃分和算法問題：每個玩家必須對n-1個對手中的每一個玩對戰一次，每天最多隻有一場比賽顯示如果n是2，那麼有可能設計一個比賽需要n-1天。通過給出一個算法，輸入n並輸出每個n-1天的玩家配對列表，到目前爲止，我知道如果n必須大於2，並且我們使用類似於合併分類算法

Answer 1

在d天（其中d範圍從1至n-1），玩家k（其中k範圍從0至n-1）中扮演球員k xor d。

這個算法有些簡單的事實：

• 如果n是2，1 <= d <= n-1和0 <= k <= n-1電源然後0 <= k xor d <= n-1所以函數k, d -> k xor d是從球員和天給玩家一個有效的功能。
• 沒有玩家曾經玩過自己，因爲k xor d = k意味着d = 0。
• 在任何給定的一天，這會產生一個配對，因爲k xor d xor d = k。
• 任何給定的玩家都不會兩次玩同一個對手，因爲k xor d = x xor d'意味着d = d'。

因此每個玩家每天玩1個對手，並且超過n-1天，每個對手恰好與每個對手匹配一次。

在代碼：

def matchings(n): 
    for day in xrange(1, n): 
     print 'Day', day 
     for k in xrange(n): 
      print 'Player', k, 'plays Player', k^day 
     print 

matchings(4)