不重复的随机配对

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

• 循环0.5*n*(n-1)个可能的配对
  • 检查此配对是否为历史记录
  • 增加“找到号码”计数器
  • 将配对另存为“结果”,概率为1/“找到个数”(即始终为找到的第一个未使用的配对)

它将在O(n2)+O(历史大小)中运行,并在所有概率用尽时很好地检测到这种情况。

根据您的需求,我认为您真正需要的是准随机数,最终使您的数据得到统一的覆盖(即每个人一次与其他人配对)。与简单随机配对相比,准随机配对给你的“聚集”结果要少得多,其附加好处是,你对结果数据的控制要大得多,因此你可以控制唯一配对规则,而不必检测新随机配对是否重复历史随机配对。

http://en.wikipedia.org/wiki/Low-discrepancy_sequence

更好的阅读:

http://www.google.com/url?sa=t&source=web&cd=10&ved=0CEQQFjAJ&url=http%3A%2F%2Fwww.johndcook.com%2Fblog%2F2009%2F03%2F16%2Fquasi-random-sequences-in-art-and-integration%2F&ei=6KQXTMSuDoG0lQfVwPmbCw&usg=AFQjCNGQga_MKXJgfEQnQXy1qrHcwfOr4Q&sig2=ox7FB0mnToQbrOCYm9-OpA

我试图找到一个C库,它可以帮助你生成你想要的那种准随机排列,但是我能找到的库只有C/C++。但我还是建议下载源代码,因为它的全部逻辑是准随机算法(查找 准蒙特卡罗 )是否有:

http://www.gnu.org/software/gsl/

在启动时,建立所有可能配对的列表。

在添加个人时将所有可能的新配对添加到此列表中,并在从池中移除个人时删除任何过期的配对。

从列表中随机选择新配对,并在选择配对后将其从列表中删除。

  Individual   A   B  C  D
           A   * 
           B   *   *
           C   *   *  *
           D   *   *  *  *

如果已形成对,则每个空白元素将包含True,否则将包含False。

每个配对会话包括循环每行的列,直到找到一个False,形成对并将矩阵元素设置为true。

删除个人时,请删除行和列。

添加个人时,添加最后一行和列。

你最好的选择可能是:

2. 随机地将相邻的两个个体随机分成一对
4. 如果找不到配对,则根据需要有一个全新的配对集,否则转到2

请注意,如果您需要高效地创建大量新的唯一对,则步骤1可以一次性完成,并在创建新对时进行更新。

我把它看作是一个图问题,其中个体是节点,顶点连接个体还没有关联。通过这种重新定义,创建新的对只是为了找到一组独立的顶点(没有任何公共节点)。

这还不是一个答案,但有可能这是一个常见的图问题,有众所周知的解决方案。

在这一点上,我们可以说,在某些情况下,可能没有解决方案(您将不得不重做一些以前的对)。

考虑对偶图也可能更简单(顶点和节点的交换角色:节点是成对的,并且是成对顶点之间的公共个体)。

然后我要做的是:

pair_everyone (pool, pairs, history):
  if pool is empty:
    all done, update global history, return pairs

  repeat for pool_size/2:
    pick element1 (randomly from pool)
    pick element2 (randomly from pool)
    set pair=pair(e1, e2)
    until pair not in history or all possible pairs tried:
      pick element1 (randomly from pool)
      pick element2 (randomly from pool)
      set pair=pair(e1, e2)

    if pair is not in history:
      result=pair_everyone(pool-e1-e2, pairs+pair, history+pair)
      if result != failure:
        return result
    else:
      return failure

怎么样:

• 创建所有当前个人的集合CI

然后:

• 随机选择一个A并从CI中移除
• 通过复制CI并删除
• 如果PP为空,则扫描找到的对列表,并将A替换为单个C,该C与不在A历史上的人配对,并且该C在CI中仍然有可能的伙伴。重新计算A=C的PP。
• 从CI中删除B
• 重复上述步骤,直到找不到新的配对