不重复的随机配对 [英] Random Pairings that don't Repeat
问题描述
这个小项目/问题对我来说是左领域的.希望有人可以在这里帮助我.我有一些粗略的想法，但我确信(或至少希望)有一个简单，相当有效的解决方案.
预先感谢....伪代码很好.如果对您的解决方案没有帮助，我通常会在.NET/C#中工作.
给出:
由n个人组成的池，这些池将定期开会.我需要形成以前没有见过的对.随着时间的流逝，个人群体将逐渐变化.为了配对，(A& B)和(B& A)构成同一对.先前配对的历史记录得以保留.出于问题的目的，假定人数为偶数.对于每次会议(成对收集)，每个人只能配对一次.
有没有一种算法可以让我们形成这些对?理想情况下，比以随机顺序对对进行排序，生成配对然后对照先前配对的历史进行检查要好.通常，配对内的随机性是可以的.
更多:
我可以想出多种方法来创建一个随机池，从中抽取成对的个体.根据历史记录检查这些记录，然后将它们放回池中或将其删除并将它们添加到配对的个人列表中.我无法理解的是，在某个时候，我将留下无法配对的个人列表.但是...其中一些人可能会与配对列表中的成员配对.我可以将其中一个合作伙伴扔回成对的成员中，但这似乎导致了一个循环，该循环将很难测试，并且可能永远持续下去.
根据您的要求，我认为您真正需要的是准随机数，该数最终将导致数据的统一覆盖(即，每个人都与每个人配对一次).与简单的随机配对相比，准随机配对给您带来的聚集"结果要少得多，而且还具有更大的控制权，可以更好地控制结果数据，因此您可以控制唯一配对规则，而不必检测新的配对规则.随机配对重复了历史随机配对.
检查此维基百科条目:
http://en.wikipedia.org/wiki/Low-discrepancy_sequence
更多好书:
http://www.gnu.org/software/gsl/
This little project / problem came out of left field for me. Hoping someone can help me here. I have some rough ideas but I am sure (or at least I hope) a simple, fairly efficient solution exists.
Thanks in advance.... pseudo code is fine. I generally work in .NET / C# if that sheds any light on your solution.
Given:
A pool of n individuals that will be meeting on a regular basis. I need to form pairs that have not previously meet. The pool of individuals will slowly change over time. For the purposes of pairing, (A & B) and (B & A) constitute the same pair. The history of previous pairings is maintained. For the purpose of the problem, assume an even number of individuals. For each meeting (collection of pairs) and individual will only pair up once.
Is there an algorithm that will allow us to form these pairs? Ideally something better than just ordering the pairs in a random order, generating pairings and then checking against the history of previous pairings. In general, randomness within the pairing is ok.
A bit more:
I can figure a number of ways to create a randomized pool from which to pull pairs of individuals. Check those against the history and either throw them back in the pool or remove them and add them to the list of paired individuals. What I can't get my head around is that at some point I will be left with a list of individuals that cannot be paired up. But... some of those individuals could possibly be paired with members that are in the paired list. I could throw one of those partners back in the pool of unpaired members but this seems to lead to a loop that would be difficult to test and that could run on forever.
Based on your requirements, I think what you really need is quasi-random numbers that ultimately result in uniform coverage of your data (i.e., everyone pairs up with everyone else one time). Quasi-random pairings give you a much less "clumped" result than simple random pairings, with the added benefit that you have a much much greater control of the resulting data, hence you can control the unique pairings rule without having to detect whether the newly randomized pairings duplicate the historically randomized pairings.
Check this wikipedia entry:
http://en.wikipedia.org/wiki/Low-discrepancy_sequence
More good reading:
I tried to find a C# library that would help you generate the sort of quasi-random spreads you're looking for, but the only libs I could find were in c/c++. But I still recommend downloading the source since the full logic of the quasi-random algorithms (look for quasi-Monte Carlo) is there:
http://www.gnu.org/software/gsl/
这篇关于不重复的随机配对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
