这是一个创建于 2836 天前的主题，其中的信息可能已经有所发展或是发生改变。
假设有 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 | ?????（无法分配了，找不到合法的数字）
所以这个方法不对。有没有保证能生成合法方案的方法？
现在我要给每个人分配 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 | ?????（无法分配了，找不到合法的数字）
所以这个方法不对。有没有保证能生成合法方案的方法？
第 1 条附言 · 2017-02-17 02:10:48 +08:00
最后我用的是打乱一个数列的方法：
数列内容是 1...人数*每个人数字个数
通过 mod 人数的余数决定分配的数字
用 random.shuffle()方法打乱，然后判断是否合法，不合法就重新 shuffle ，直到成功为止
数列内容是 1...人数*每个人数字个数
通过 mod 人数的余数决定分配的数字
用 random.shuffle()方法打乱，然后判断是否合法，不合法就重新 shuffle ，直到成功为止
 |
1
Kilerd 2017-02-16 13:53:17 +08:00 via iPhone
gcd 算法。群的轮换。膜运算。就可以搞定了
|
Select Language