V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
yazinnnn
V2EX  ›  程序员

如何实现一个欧冠 16 强抽签模拟器?

  •  
  •   yazinnnn · 2019-12-13 08:01:19 +08:00 · 3217 次点击
    这是一个创建于 1793 天前的主题,其中的信息可能已经有所发展或是发生改变。

    今年欧冠小组赛结束了,自己想做一个抽签模拟器,发现水平不够做不出来,有没有大佬帮忙提供一个实现思路

    需求是这样的:

    • 先抽小组第二,然后抽小组第一的对手
    • 同小组回避
    • 同联赛回避
    • 不能让抽剩下的队伍无法比赛

    前三个都好办,写个 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 切尔西 英超
    
    
    10 条回复    2019-12-13 13:53:18 +08:00
    kickcandy
        1
    kickcandy  
       2019-12-13 09:28:39 +08:00
    这是欧足联派人来了?
    Muniesa
        2
    Muniesa  
       2019-12-13 09:31:50 +08:00   ❤️ 1
    yazinnnn
        3
    yazinnnn  
    OP
       2019-12-13 09:38:27 +08:00
    @kickcandy
    欧足联直接黑箱了需要派我来?

    只是自己想写个程序测试一下各种对阵情况的概率,然后发现基础薄弱,半路出家的码农连这么简单的算法问题都解决不了,再不深造怕是只能当一辈子 crud boy 了
    Defined
        4
    Defined  
       2019-12-13 10:23:59 +08:00
    @yazinnnn 要测概率不用那么复杂,先只考虑小组第一对小组第二这一个限制,一共就只有 8*7*6...*2*1 种,把这些都枚举出来,然后判断下符不符合同组、同联赛回避的规则就好了
    yazinnnn
        5
    yazinnnn  
    OP
       2019-12-13 10:44:09 +08:00
    @Defined

    https://bbs.hupu.com/31222242.html
    https://twitter.com/2010MisterChip/status/1204879583457218564/photo/1

    github 上的概率和 twitter 的概率算得不一样

    我是想算出来所有可能的结果集,然后模拟过程循环 100 万次实际测试一下概率,结果卡在了获得所有的结果集上...

    我想得到这种概率
    每种结果集的概率,无视抽签顺序
    每种结果集的概率,考虑抽签顺序
    各支队伍对阵的概率

    github 的测试只能获得各支队伍对阵概率,我还看不出对错...

    唉,我就是个辣鸡(⊙_⊙)
    CrisTao
        6
    CrisTao  
       2019-12-13 10:47:34 +08:00
    把满足前三种的全部算出来就行了,然后迭代一下,看是否存在不满足第四种条件的,将其移除
    yazinnnn
        7
    yazinnnn  
    OP
       2019-12-13 10:53:40 +08:00
    @CrisTao
    渣渣求一下迭代实现回溯的伪代码(⊙_⊙)
    maichael
        8
    maichael  
       2019-12-13 10:57:04 +08:00
    暴力穷举
    zaima
        9
    zaima  
       2019-12-13 11:09:56 +08:00
    把所有排序都算出来,逐一遍历,再排除错误的分组。按你的用按抽签的逻辑去算的话,感觉情况会比较复杂
    jyyx
        10
    jyyx  
       2019-12-13 13:53:18 +08:00
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2823 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 02:18 · PVG 10:18 · LAX 18:18 · JFK 21:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.