我们如何生成一定数量的随机数并将它们相互链接,而不会将数字链接到自身?

Usu*_*woa 1 c++ random algorithm

我正在编写一个程序,我需要在其中随机播放人员列表并将它们链接到列表中的另一个人。但问题在于奇数,因为 1 个人可以链接到他们自己。(我让那不可能,所以什么也没发生。)

例如,如果有 3 个名为“Bill”、“John”和“Jonas”的人。如果“Bill”得到“Jonas”而“Jonas”得到“Bill”,那么“John”就会与“John”联系起来,但我使这变得不可能(为了得到他们自己),所以什么也没有发生。

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

cig*_*ien 6

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

  1. 随机洗牌人员名单。
  2. 对于每个人(最后一个除外),将他们链接到列表中的下一个人。
  3. 将最后一个人链接到第一个。

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

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