algorithm - 如何对具有固定行/列总和的数组进行洗牌？

Question

我需要将随机论文分配给类(class)的学生，但我有以下限制:

1. 每个学生应该分配两篇论文。
2. 每篇论文应分配给(大约)相同数量的学生。

有没有一种优雅的方法来生成具有此属性的矩阵？即它被打乱但行和列的总和是恒定的？例如:

Student A   1  0  0  1  1  0 |  3
Student B   1  0  1  0  0  1 |  3
Student C   0  1  1  0  1  0 |  3
Student D   0  1  0  1  0  1 |  3
            ---------------- 
            2  2  2  2  2  2

我想先用正确的行/列总和构建一个“初始矩阵”，然后先随机排列行，然后是列，但我如何生成这个初始矩阵？这里的问题是我会在(例如)以下备选方案之间进行选择，并且有两个学生分配了同一对论文(在左侧设置中)这一事实不会通过行/列改组而改变:

INITIAL (MA):            OR (MB):
A   1  1  1  0  0  0  ||  1  1  1  0  0  0  
B   1  1  1  0  0  0  ||  0  1  1  1  0  0
C   0  0  0  1  1  1  ||  0  0  0  1  1  1
D   0  0  0  1  1  1  ||  1  0  0  0  1  1

我知道我可以想出一些快速/肮脏的东西，并在必要时进行调整，但这似乎是一个有趣的练习。

Answer 1

如果你想进行排列，那么:

• 随机选择一个学生，比如学生 1

• 对于这个学生，选择他有的随机试卷，比如试卷 A

• 随机选择另一个学生

• 对于这个学生，选择他有的随机论文，比如论文 B(不同于 A)

• 将试卷 B 交给学生 1，将试卷 A 交给学生 2。

这样一来，您既可以保留不同论文的数量，也可以保留每个学生的论文数量。事实上，两个学生都给出了一篇论文并收到了一篇论文。此外，没有创建或删除任何论文。

用表来说，就是找到两对索引(i1,i2)和(j1,j2)使得A(i1,j1) = 1, A(i2,j2)=1, A(i1, j2)=0 和 A(i2,j1)=0 并更改 0 为 1 和 1 为 0 => 行和列的总和不变。

备注 1:如果您不想按排列进行，您可以简单地将所有纸张放入一个向量中(放置 2 倍纸张 A，2 倍纸张 B，...)。然后，随机打乱向量并将第 k 个归因于第一个学生，接下来的 k 个归因于学生 2，...但是，您可以以一个学生有多次相同的论文结束。在这种情况下，从附加论文开始进行一些排列。