这是一个创建于 1833 天前的主题，其中的信息可能已经有所发展或是发生改变。
今年欧冠小组赛结束了,自己想做一个抽签模拟器,发现水平不够做不出来,有没有大佬帮忙提供一个实现思路
需求是这样的:
- 先抽小组第二,然后抽小组第一的对手
- 同小组回避
- 同联赛回避
- 不能让抽剩下的队伍无法比赛
前三个都好办,写个 filter 就行,但是第四个条件要用回溯算法来判断抽签剩下的队伍是否能比赛,举个例子:
最后还剩 4 支队伍
1 支 西甲 小组第二
1 支 英超 小组第二
1 支 德甲 小组第一
1 支 英超 小组第一
抽出西甲小组第二后,就只能抽英超小组第一
因为如果抽德甲小组第一会造成剩下两只队伍都是英超球队
附今年欧冠小组赛战绩
A
1 巴黎 法甲
2 皇马 西甲
B
1 拜仁 德甲
2 热刺 英超
C
1 曼城 英超
2 亚特兰大 意甲
D
1 尤文 意甲
2 马竞 西甲
E
1 利物浦 英超
2 那不勒斯 意甲
F
1 巴萨 西甲
2 多特 德甲
G
1 莱比锡 德甲
2 里昂 法甲
H
1 瓦伦西亚 西甲
2 切尔西 英超
 |
1
kickcandy 2019-12-13 09:28:39 +08:00
这是欧足联派人来了？
|
 |
2
Muniesa 2019-12-13 09:31:50 +08:00  1
遇事不决 GitHub https://github.com/eminga/cldraw
|
 |
3
yazinnnn OP @kickcandy
欧足联直接黑箱了需要派我来? 只是自己想写个程序测试一下各种对阵情况的概率,然后发现基础薄弱,半路出家的码农连这么简单的算法问题都解决不了,再不深造怕是只能当一辈子 crud boy 了 |
 |
4
Defined 2019-12-13 10:23:59 +08:00
@yazinnnn 要测概率不用那么复杂，先只考虑小组第一对小组第二这一个限制，一共就只有 8*7*6...*2*1 种，把这些都枚举出来，然后判断下符不符合同组、同联赛回避的规则就好了
|
|
5
yazinnnn OP @Defined
https://bbs.hupu.com/31222242.html https://twitter.com/2010MisterChip/status/1204879583457218564/photo/1 github 上的概率和 twitter 的概率算得不一样 我是想算出来所有可能的结果集,然后模拟过程循环 100 万次实际测试一下概率,结果卡在了获得所有的结果集上... 我想得到这种概率 每种结果集的概率,无视抽签顺序 每种结果集的概率,考虑抽签顺序 各支队伍对阵的概率 github 的测试只能获得各支队伍对阵概率,我还看不出对错... 唉,我就是个辣鸡(⊙_⊙) |
 |
6
CrisTao 2019-12-13 10:47:34 +08:00
把满足前三种的全部算出来就行了，然后迭代一下，看是否存在不满足第四种条件的，将其移除
|
 |
8
maichael 2019-12-13 10:57:04 +08:00
暴力穷举
|
 |
9
zaima 2019-12-13 11:09:56 +08:00
把所有排序都算出来，逐一遍历，再排除错误的分组。按你的用按抽签的逻辑去算的话，感觉情况会比较复杂
|
 |
10
jyyx 2019-12-13 13:53:18 +08:00
|
Select Language