简单的编程问题求助(随机数生成)

2017-02-16 13:15:32 +08:00
 starvedcat
假设有 20 个人,编号 1-20

现在我要给每个人分配 5 个整数,其值域是“ 1-20 中除了自身编号以外的数”。比如,我给 7 号分配的 5 个数字,要从 1-6 、 8-20 里选 5 个

并且,对于这 20 个人得到的全部 100 个数字, 1-20 中的每个数字恰好出现 5 次

现在,我需要一种随机分配数字的方案,在这个方案中,每一种符合上面描述的、合法的分配方式,都会有等同的概率出现

最 naive 的方式就是,按顺序分配随机数,如果发现生成的数字不符合规则,那就重新生成。但是这个方案有一个问题,就是可能会出现合法的数字都被用完了的情况,比如下面这个例子:
假设有 5 个人,每个人分配 3 个数字
1 | 2 3 4
2 | 1 3 4
3 | 1 2 4
4 | 1 2 3
5 | ?????(无法分配了,找不到合法的数字)
所以这个方法不对。有没有保证能生成合法方案的方法?
2530 次点击
所在节点    编程
1 条回复
Kilerd
2017-02-16 13:53:17 +08:00
gcd 算法。群的轮换。膜运算。就可以搞定了

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/340869

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX