algorithm - 不重复的随机配对

这个小项目/问题对我来说是从左边的领域出来的。希望有人能在这里帮助我。我有一些粗略的想法，但我确信(或至少我希望)存在一个简单、相当有效的解决方案。

提前致谢....伪代码很好。如果这对您的解决方案有任何帮助，我通常在 .NET/C# 中工作。

鉴于:

将定期开会的 n 个人池。我需要形成以前没有见过的对。随着时间的推移，个人群体会慢慢发生变化。为了配对，(A&B)和(B&A)构成同一对。保留先前配对的历史记录。为了解决这个问题，假设有偶数个人。对于每次 session (配对集合)，个人只能配对一次。

有没有一种算法可以让我们形成这些对？理想情况下，这比仅以随机顺序排列配对、生成配对然后检查之前配对的历史记录更好。一般来说，配对内的随机性是可以的。

多一点:

我可以想出多种方法来创建一个随机池，从中拉出成对的个体。根据历史检查那些，然后将它们扔回池中或删除它们并将它们添加到配对个体列表中。我无法理解的是，在某些时候，我会得到一个无法配对的个人列表。但是……其中一些人可能会与配对列表中的成员配对。我可以将其中一个伙伴扔回未配对成员池中，但这似乎导致了一个难以测试并且可能永远运行的循环。

最佳答案

将标准搜索转换为概率选择的有趣想法:

使用 O(1) “包含”测试在结构中加载历史记录，例如(A,B) 对的 HashSet。

循环遍历 0.5*n*(n-1) 个可能的配对

检查此配对是否在历史记录中

如果不是则继续循环

的下一次迭代

增加“找到的数量”计数器

将配对保存为“结果”，概率为 1/“找到的数字”(即始终用于找到的第一个未使用的配对)

最后，如果“result”有答案，则使用它，否则所有可能性都已用尽

这将在 O(n^2) + O(历史大小) 中运行，并且很好地检测到所有概率都用尽的情况。

关于algorithm - 不重复的随机配对，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3046482/