1 回答

TA貢獻1777條經(jīng)驗 獲得超3個贊
您所說的“最大化平均分配”是什么意思沒有明確定義。人們可能會考慮給定值的兩個幻影之間的最大對數(shù)。我將留給你展示我在這里給出的方法相對于它是如何執(zhí)行的。
對于 n 個對象,我們有 n*(n-1) 對。在這些(a, b)
對中:
n 具有諸如 b = (a+1) modulo n 之類的索引
n 具有諸如 b = (a+2) modulo n 之類的索引
等等。
我們可以生成前 n 對相差 1,然后生成 n 對相差 2...
對于每個差異,我們通過將差異添加到索引(模 n)來生成索引。當(dāng)我們得到a
已經(jīng)用于這種差異的an 時,我們加 1(再次取模 n)。這樣,我們可以生成具有這種差異的 n 對。當(dāng)我們“滾動”索引時,我們確信每個值都會定期出現(xiàn)。
def pairs(n):
for diff in range(1, n):
starts_seen = set()
index = 0
for i in range(n):
pair = [index]
starts_seen.add(index)
index = (index+diff) % n
pair.append(index)
yield pair
index = (index+diff) % n
if index in starts_seen:
index = (index+1) % n
pairs2 = list(pair for pair in pairs(2))
print(pairs2)
# [[0, 1], [1, 0]]
pairs3 = list(pair for pair in pairs(3))
print(pairs3)
# [[0, 1], [2, 0], [1, 2],
# [0, 2], [1, 0], [2, 1]]
pairs4 = list(pair for pair in pairs(4))
print(pairs4)
# [[0, 1], [2, 3], [1, 2], [3, 0], <- diff = 1
# [0, 2], [1, 3], [2, 0], [3, 1], <- diff = 2
# [0, 3], [2, 1], [1, 0], [3, 2]] <- diff = 3
pairs5 = list(pair for pair in pairs(5))
print(pairs5)
# [[0, 1], [2, 3], [4, 0], [1, 2], [3, 4],
# [0, 2], [4, 1], [3, 0], [2, 4], [1, 3],
# [0, 3], [1, 4], [2, 0], [3, 1], [4, 2],
# [0, 4], [3, 2], [1, 0], [4, 3], [2, 1]]
# A check to verify that we get the right number of different pairs:
for n in range(100):
pairs_n = set([tuple(pair) for pair in pairs(n)])
assert len(pairs_n) == n*(n-1)
print('ok')
# ok
添加回答
舉報