c++ - 我们如何生成一定数量的随机数并将它们相互链接，而无需将数字链接到自身？

Question

我正在编写一个程序，我需要对人员列表进行洗牌并将他们链接到列表中的另一个人。但问题在于奇数，因为可以将 1 个人与他们自己联系起来。（我让这不可能，所以什么也没有发生。）

例如，如果有 3 个人分别称为“Bill”、“John”和“Jonas”。如果'Bill' 得到'Jonas' 而'Jonas' 得到'Bill'，那么'John' 与'John' 相关联，但我使这成为不可能（为了得到他们自己）所以什么都没有发生。

有谁知道我该如何解决这个问题？

标签： c++algorithmrandom

Answer 1

这本质上是一个“秘密圣诞老人”问题。有一个简单的算法：

1. 随机洗牌人员名单。
2. 对于每个人（最后一个人除外），将他们链接到列表中的下一个人。
3. 将最后一个人与第一个人联系起来。

这保证是随机链接，并保证没有人链接到他们自己。

请注意，这并不是真正随机的，因为没有相互关联的子群体。从任何人开始，您都可以关注链接并联系其他所有人。如果我没记错的话，我认为在随机链接中有三分之一的时间会存在彼此无法访问的子组。但是，这种形式的改组和链接应该足以满足您的目的。