将20人分配到4张桌子上四次，不得重复，每个人只能在每张桌子上呆一次

Question

我想随机分配20个人到4张桌子上，不重复地做4项任务，每个人必须在每张桌子上只呆一次。

每桌有五个人。有四张桌子。每张桌子必须由五个人均匀旋转。

import random
# generate 1 to 20
members_list = [x for x in range(1, 21)]
# assign to 4 groups
chunks = [members_list[x:x + 5] for x in range(0, len(members_list), 5)]
print(chunks)
final_result = []
count = 0
start_assign = 4
# generate a new random list
while start_assign:
new_member_list = [x for x in range(1, 21)]
random.shuffle(new_member_list)
print(f"random List {start_assign}: {new_member_list} n")
for i in chunks:
result = []
count += 1
print(f"The Original List {count}: {i}")
for x in new_member_list:
if x not in i:
result.append(x)
result = result[:5]
new_member_list = [x for x in new_member_list if x not in result]
result.sort()
if len(result) < 5:
result.extend(new_member_list)
print(f"Second List Result {count}: {result}")
result.extend(i)
final_result.append(result)
print(f"combine with the previous list: {count}: {final_result}n")
chunks = []
chunks = final_result
start_assign -= 1
print(f"Final new list: {final_result}")

Answer 1

假设您有一个20x4的二进制矩阵，将人员映射到表。行是人，列是过程的迭代。每一行都包含一些数字[0,3]的排列，以指示每个人遍历表格的顺序。每列恰好包含与每个表对应的五个元素，这意味着在每次迭代中，所有表都被均匀填充。以下是启动配置示例：

np.array([
[0, 1, 2, 3], # Person 0 goes to tables 0, 1, 2, 3, in that order
[0, 1, 2, 3],
[0, 1, 2, 3],
[0, 1, 2, 3],
[0, 1, 2, 3],
[1, 2, 3, 0], # Person 5 goes to tables 1, 2, 3, 0, in that order
[1, 2, 3, 0],
[1, 2, 3, 0],
[1, 2, 3, 0],
[1, 2, 3, 0],
[2, 3, 0, 1],
[2, 3, 0, 1],
[2, 3, 0, 1],
[2, 3, 0, 1],
[2, 3, 0, 1],
[3, 0, 1, 2],
[3, 0, 1, 2],
[3, 0, 1, 2],
[3, 0, 1, 2],
[3, 0, 1, 2],
])

这是一个有效的配置。列中每个元素有5个，每行中有唯一元素的任何配置都是有效的配置。转移到另一个有效配置的一种方法是交换任何一行：两个人将交换时间表，但对行和列的约束不会改变。类似地，您可以交换任意两列：访问顺序将更改，但所有内容都将保持有效。像这样打乱整行整列并不是很有趣：五个人一组最终会在所有的步骤中粘在一起，即使他们的路径会有点随机。

更一般地说，您可以交换给定行或列中的一对元素。这将破坏配置的有效性，因此您必须多次交换其他元素才能恢复它

3, 1, 2, 0

现在，您需要找到另一个以3开头的行，并交换该行中的3和0。这将恢复第一列，但可能会使现在包含3的列无效。因此，您可以在新列的其他位置找到另一个3，并与包含3的行中的0交换。您可以一直这样做，直到3最终出现在某行的最后一列，并且恢复了顺序。

您可以对每一行执行类似Fisher Yates洗牌的操作，并在执行过程中增加解决条件的步骤。下面是一个示例实现。我使用numpy数组是为了方便存储和索引，但您也可以使用列表：

P = 20
M = 4
N = P // M
idx = np.arange(M)
# Start with a valid configuration, same as the array written out above
paths = ((idx + idx[:, None]) % M).repeat(N, axis=0)
for i in range(P):
# Shuffle each row
for j in range(M - 1):
swap = j + np.random.choice(M - j)
if swap == j:
continue
n0 = paths[i, j]     # First number to swap
n1 = paths[i, swap]  # Second number to swap
# fix up the consequences
ix = swap            # Index of the other column
while j != swap:
# Swap the elements in the previous row
paths[i, [j, ix]] = paths[i, [ix, j]]
# Find a new row with n1 at column j
i = np.random.choice(np.flatnonzero(paths[:, j] == n1))
# Find the location of n0 in the new row
ix = j
j = np.flatnonzero(paths[i] == n0)[0]
paths[i, [j, ix]] = paths[i, [ix, j]]
# Check the results:
assert (np.sort(paths, axis=1) == idx).all(None)
assert (np.sum(paths, axis=0) == N * M * (M - 1) // 2).all()

代码中的注释应该有助于您理解。我无法证明这个解决方案是公正的，但从我粗略的测试来看，它似乎很好(而且很快(。最后的断言可以移出循环以检查最终结果，或者如果您对实现有信心，则可以完全删除。

根据您指定的条件，每个人从给定的表(要访问的其他3个表(开始有6条可能的路径。由于每张桌子上都有5个人开始，因此在几乎所有情况下，从某张桌子上开始的一对或多对人最终仍然会走在同一条路上。我不确定这种情况的发生是因为它很可能(对于m=4，N=5，没有先验的情况，约91%[见此处](，还是因为条件中有某种东西有效地需要它。