我正在組織一場比賽，12 名玩家將在 10 場棋盤游戲中相遇。我希望每個玩家在 10 場棋盤游戲中至少與其他 11 位玩家一起玩一次。例如 ：
BoardGame1 - Match1 - Player1 Player2 Player3
BoardGame1 - Match2 - Player4 Player5 Player6
BoardGame1 - Match3 - Player7 Player8 Player9
BoardGame1 - Match4 - Player10 Player11 Player12
[...]
BoardGame10 - Match1 - Player1 Player11 Player9
BoardGame10 - Match2 - Player4 Player2 Player12
BoardGame10 - Match3 - Player7 Player5 Player3
BoardGame10 - Match4 - Player10 Player8 Player6
你如何創建一個演算法來平均分配玩家？我想用 TDD 方法來做，所以我需要預測預期的結果（意味著沒有隨機分布）。
uj5u.com熱心網友回復：
如果所有玩家只玩一次，那么最終的物件將是柯克曼三重系統。沒有你想要的引數的KTS，但由于每個玩家有20個對手位置，只有11個潛在對手，應該很容易找到合適的時間表。
下面的代碼為一場比賽生成 (11 選擇 2) × (8 選擇 2) × (5 選擇 2) = 15400 種可能性，并反復貪婪地選擇以最公平的方式傳播配對的那一種。
import collections
import itertools
import pprint
def partitions(players, k):
players = set(players)
assert len(players) % k == 0
if len(players) == 0:
yield []
else:
players = players.copy()
leader = min(players)
players.remove(leader)
for comb in itertools.combinations(sorted(players), k - 1):
group = {leader} | set(comb)
for part in partitions(players - group, k):
yield [group] part
def update_pair_counts(pair_counts, game):
for match in game:
pair_counts.update(itertools.combinations(sorted(match), 2))
def evaluate_game(pair_counts, game):
pair_counts = pair_counts.copy()
update_pair_counts(pair_counts, game)
objective = [0] * max(pair_counts.values())
for count in pair_counts.values():
objective[count - 1] = 1
total = 0
for i in range(len(objective) - 1, -1, -1):
total = objective[i]
objective[i] = total
return objective
def schedule(n_groups, n_players_per_group, n_games):
games = list(partitions(range(n_groups * n_players_per_group), n_players_per_group))
pair_counts = collections.Counter()
for i in range(n_games):
game = max(games, key=lambda game: evaluate_game(pair_counts, game))
yield game
update_pair_counts(pair_counts, game)
def main():
pair_counts = collections.Counter()
for game in schedule(4, 3, 10):
pprint.pprint(game)
update_pair_counts(pair_counts, game)
print()
pprint.pprint(pair_counts)
if __name__ == "__main__":
main()
樣本輸出：
[{0, 1, 2}, {3, 4, 5}, {8, 6, 7}, {9, 10, 11}]
[{0, 3, 6}, {1, 4, 9}, {2, 10, 7}, {8, 11, 5}]
[{0, 4, 7}, {3, 1, 11}, {8, 9, 2}, {10, 5, 6}]
[{0, 1, 5}, {2, 11, 6}, {9, 3, 7}, {8, 10, 4}]
[{0, 8, 3}, {1, 10, 6}, {2, 11, 4}, {9, 5, 7}]
[{0, 10, 11}, {8, 1, 7}, {2, 3, 5}, {9, 4, 6}]
[{0, 9, 2}, {1, 10, 3}, {8, 4, 5}, {11, 6, 7}]
[{0, 4, 6}, {1, 2, 5}, {10, 3, 7}, {8, 9, 11}]
[{0, 5, 7}, {1, 11, 4}, {8, 2, 10}, {9, 3, 6}]
[{0, 3, 11}, {8, 1, 6}, {2, 4, 7}, {9, 10, 5}]
Counter({(0, 3): 3,
(0, 1): 2,
(0, 2): 2,
(1, 2): 2,
(3, 5): 2,
(4, 5): 2,
(6, 7): 2,
(6, 8): 2,
(7, 8): 2,
(9, 10): 2,
(9, 11): 2,
(10, 11): 2,
(0, 6): 2,
(3, 6): 2,
(1, 4): 2,
(4, 9): 2,
(2, 7): 2,
(2, 10): 2,
(7, 10): 2,
(5, 8): 2,
(8, 11): 2,
(0, 4): 2,
(0, 7): 2,
(4, 7): 2,
(1, 3): 2,
(1, 11): 2,
(3, 11): 2,
(2, 8): 2,
(2, 9): 2,
(8, 9): 2,
(5, 10): 2,
(6, 10): 2,
(0, 5): 2,
(1, 5): 2,
(2, 11): 2,
(6, 11): 2,
(3, 7): 2,
(3, 9): 2,
(7, 9): 2,
(4, 8): 2,
(8, 10): 2,
(1, 6): 2,
(1, 10): 2,
(2, 4): 2,
(4, 11): 2,
(5, 7): 2,
(5, 9): 2,
(0, 11): 2,
(1, 8): 2,
(2, 5): 2,
(4, 6): 2,
(6, 9): 2,
(3, 10): 2,
(3, 4): 1,
(1, 9): 1,
(5, 11): 1,
(5, 6): 1,
(2, 6): 1,
(4, 10): 1,
(0, 8): 1,
(3, 8): 1,
(0, 10): 1,
(1, 7): 1,
(2, 3): 1,
(0, 9): 1,
(7, 11): 1})
uj5u.com熱心網友回復：
你如何創建一個演算法來平均分配玩家？我想用 TDD 方法來做，所以我需要預測預期的結果（意味著沒有隨機分布）。
如果您的問題是您知道計算機應該做什么，并且您知道如何使計算機做到這一點，但您不知道撰寫代碼的最佳方式，那么 TDD 往往會成功。
當你不知道如何讓計算機做你想做的事時，TDD 就困難得多。這里采用了兩種典型的方法。
第一個是執行“秒殺”——坐下來破解，直到你明白如何讓計算機做你想做的事。尖峰的關鍵特性是您不會在最后保留代碼更改。取而代之的是，你丟棄了你的尖刺代碼，把你學到的東西記在腦子里，然后通過撰寫你需要的測驗重新開始。
第二種方法是偷偷摸摸——你對你理解的非常簡單的情況進行 TDD，并繼續添加比你已經做過的更難的測驗。有關此方法的示例，請參見 Robert Martin 的Craftsman 系列。
對于這個問題，您可能首先考慮可能用于訪問演算法的介面。例如，您可能會考慮這樣一種設計，它接受多個玩家和多個游戲作為輸入，并回傳一個元組序列，其中每個元組代表一個匹配項。
通常，這個版本的介面看起來像作為輸入的通用資料結構（在這個例子中：數字），作為輸出的通用資料結構（元組串列）。
最常見的是，我們將通過確定給定輸入集的答案應該是什么來驗證每個測驗中的行為，并斷言實際的資料結構與預期的完全匹配。對于元組串列，它看起來像：
assert len(expected) == len(actual)
for x in range(actual):
assert len(expected[x]) == len(actual[x])
for y in range(actual[x]):
assert expected[x][y] == actual[x][y]
當然，您可以將其重構為看起來更好的東西
assert expected == actual
另一種可能性是考慮解決方案應具有的屬性，并驗證實際結果是否與這些屬性一致。在這里，您似乎具有每個解決方案都需要的兩個屬性：
- 每對球員應該在比賽串列中出現一次
- 每個玩家，棋盤游戲對都應該在匹配串列中出現一次
在這種情況下，答案很容易檢查（遍歷所有匹配，計算每一對，斷言計數等于 1）。
我們從我們能想到的最簡單的例子開始介紹測驗本身。在這里，這可能是我們有 2 個玩家和 1 個棋盤的情況，我們的答案應該是
BoardGame1 - Match1 - Player1 Player2
所以我們寫了那個測驗（紅色），硬編碼這個特定的答案（綠色），然后（重構）代碼，這樣讀者就清楚為什么這是這些輸入的正確答案。
當您對該代碼感到滿意時，您會尋找下一個示例 - 當前實作回傳錯誤答案的示例，但您需要進行的更改以使其回傳寫入答案很小/很容易。
通常，我們會使用分支“通過”下一個測驗：
if special_case(inputs):
return answer_for_special_case
else:
# ... real implementation here ...
return answer_for_general_case
然后重構代碼，直到兩個塊相同，最后洗掉 if 子句。
有時會發生新的測驗太大，我們無法弄清楚如何擴展演算法以覆寫新的情況。通常的做法是恢復我們所做的任何更改（保持測驗通過），并使用我們學到的知識來找到可能更容易引入代碼的不同測驗。
并且你不斷迭代這個程序，直到你解決了“所有”問題。
uj5u.com熱心網友回復：
如果我們添加第 11 個游戲（我們總是可以放棄它）并要求每個玩家恰好與其他玩家相遇兩次，我們正在尋找的物件稱為具有引數 (12, 3, 2) 的可決議 2 設計. 這是一個部分答案，它使用 Shmuel Schreiber 的構造（“一些平衡的完整塊設計”，1974 年）給出了具有引數（12、3、2）的 2 設計，但不知道是可解決的。
import collections
import itertools
q = 5
assert q % 6 in {1, 5}
x = q * 2
y = x 1
G = range(0, x, 2)
C2 = range(0, x, q)
H = range(0, x, 1)
arcs = [(a, b) for a in G for b in G if a != 0 and b != 0 and (b 2 * a) % x == 0]
red = []
blue = []
for (a, b) in arcs:
if (a, b) < ((-a) % x, (-b) % x):
red.append((a, b))
else:
blue.append((a, b))
def bar(h):
return (h q) % x
# 1a
triples = [
(a, b, c) for (a, b, c) in itertools.combinations(G, 3) if (a b c) % x == 0
]
# 1b
triples = [
((a i) % x, (b j) % x, (c k) % x)
for (a, b, c) in triples
for i in C2
for j in C2
for k in C2
]
# 1c
triples.extend((a, b, bar(a)) for (a, b) in arcs)
triples.extend((a, bar(b), bar(a)) for (a, b) in arcs)
# 2a
triples.extend((x, a, b) for (a, b) in red)
triples.extend((x, bar(a), bar(b)) for (a, b) in red)
triples.extend((y, a, bar(b)) for (a, b) in red)
triples.extend((y, bar(a), b) for (a, b) in red)
triples.extend((y, a, b) for (a, b) in blue)
triples.extend((y, bar(a), bar(b)) for (a, b) in blue)
triples.extend((x, a, bar(b)) for (a, b) in blue)
triples.extend((x, bar(a), b) for (a, b) in blue)
# 3
triples.extend([(x, y, 0), (x, y, bar(0)), (x, 0, bar(0)), (y, 0, bar(0))])
pair_counts = collections.Counter()
for triple in triples:
pair_counts.update(itertools.combinations(sorted(triple), 2))
print(pair_counts)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/514847.html
標籤：算法单元测试tdd