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

给定若干个条件,怎么判断这些条件彼此互斥

  •  
  •   murmur · 2021-07-14 11:23:37 +08:00 · 2014 次点击
    这是一个创建于 988 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需求是流程编辑器,想要检查用户设定的分支是否冲突

    比如左边的分支是 A>80 右边的分支理论上应该是 A<=80,但是不要是右边分支是 A>60,或者是 B>80 这种没法做唯一性的解

    见过其他的解决方案,都是设定默认分支,当程序也不知道怎么走的时候,就走默认分支

    类似的可以扩展到多个分支,多个条件

    如果感觉不靠谱,可以限制为单条件,也就是说没有[a, b]这样的左右区间比较

    除了手写 if-else 判断有没有什么优雅方法

    12 条回复    2021-07-15 10:50:21 +08:00
    wutiantong
        1
    wutiantong  
       2021-07-14 11:53:59 +08:00
    给分支附加上优先级(排序),按优先级从高到低依次检查,遇到满足的就 break,全都不满足就走最后的 default 。
    如果按这样做就不存在“冲突”了。

    对于你描述的情况,可以引用集合概念,每个分支的条件相当于对应一个子集,“不冲突”相当于要求所有的子集两两不相交。而默认分支应该代表所有子集之外的补集。
    aguesuka
        2
    aguesuka  
       2021-07-14 12:36:00 +08:00   ❤️ 1
    假设流程是没有环的, 而且分支和流程之间没有依赖关系.

    有规则:
    大写字母记作断言, 小写字母记作流程.

    1. A -> a -> B -> b 记作 "如果 A 为真, 那么执行 a, 然后如果 B 为真, 那么执行 b".
    这个流程可以简化成两个等价的流程 A -> a; A -> B -> b (有序). 也就是"如果 A 成立, 那么执行 a, 然后 如果 A 且 B, 那么执行 b"
    2. A -> (B -> b Else C -> c) 记作 "如果 A 为真, 那么如果 B 那么 b, 如果非 B 且 C 那么 c", 等价于 A -> B -> b; A -> !B -> C -> c
    3. A & B -> c 记作 "如果 A 为真且 B 为真, 那么执行 c" , 等价于 A -> B -> c.
    4. A | B -> c 记作 "如果 A 为真或 B 为真, 那么执行 c " 等价于 A -> c; B ->c.

    根据以上规则, 如果流程没有环, 那么可以将流程的有向无环图化简成它的所有可达路径. 这样只须实现可达路径上的冲突判断即可. 例如问题主干就对应规则 4.

    假如流程之间有依赖关系, 规则比这里的复杂, 但也类似. 而流程是有环的情况, 直觉上应该是不可判定问题, 除非加上一些限制.
    murmur
        3
    murmur  
    OP
       2021-07-14 12:42:30 +08:00
    @aguesuka 感觉是我描述错了么,我这个是编辑器用的,不是流程执行用的

    比如 3 个分支,1.A>50 2.30<=A<=50 3.A<30 属于合理设计,但是如果第三个条件设置成 A<10 或者 B<30 就有瑕疵,因为这 3 个分支没有覆盖所有的可能条件

    简单点说就是要这几个条件的 AB 能覆盖整个数值区间,任何一个数来了都是 3 个条件中唯一确定的,而不是 1 对 2 可能也对
    aguesuka
        4
    aguesuka  
       2021-07-14 12:56:58 +08:00
    一样的
    比如 1. (A > 50 | B > 50) 2. (B <= 50 & A > 50) 3. (A <= 50) 等价于

    A > 50 -> B <= 50 -> A > 50 -> A <= 50
    B > 50-> B <= 50 -> A > 50 -> A <= 50

    可以看见两种情况下 A 都完整覆盖了, 但第一种情况下 B 没有完整覆盖
    aguesuka
        5
    aguesuka  
       2021-07-14 13:34:06 +08:00   ❤️ 1
    我知道你问的啥了, 我把"右边分支是 A>60,或者是 B>80" 理解成"右边分支是 (A>60,或者是 B>80)" 而你的意思是 "右边分支是 A>60,或者右边分支是 B>80 ".

    如果是数字的话就把判断的区间按照区间的下限排序, 然后判断这个数组是不是连续的, 并覆盖了所有数.

    例如: 1.A>50 2.30<=A<=50 3.A<10. 转换成区间 (50, null), [30, 50], (null, 10) 然后按下限排序, 刚好反过来 (null, 10), [30, 50] ,(50, null) 第一个区间的上限是 10, 第二个区间的下限是 30, 所以不连续.
    PonysDad
        6
    PonysDad  
       2021-07-14 13:39:04 +08:00 via iPhone   ❤️ 1
    形式化后进行命题逻辑演算。具体回去翻翻离散数学命题逻辑部分。
    TomatoYuyuko
        7
    TomatoYuyuko  
       2021-07-14 13:41:25 +08:00
    可能我理解有误。咱们能不能这样,咱们不纠结于“条件”设定本身,而是在每次应用这个规则的时候直接取反不就可以了吗
    JerryCha
        8
    JerryCha  
       2021-07-14 13:57:29 +08:00
    按我的理解,可能问后端流程怎么跑更有效,校验时取几个值试算一下。
    kilasuelika
        9
    kilasuelika  
       2021-07-14 14:20:28 +08:00 via Android   ❤️ 1
    有种区间树的数据结构,可以用来查询值是否在区间集合内。
    有现成的就不要自己来搞。
    no1xsyzy
        10
    no1xsyzy  
       2021-07-15 09:32:50 +08:00
    先问几个最难搞的问题
    1. NaN 怎么办?
    NaN > 80 # false
    NaN <= 80 # false

    2. 是否存在非简单判断条件?如何判断已竭?
    isexpression(e)
    isfunction(e)

    3. 存在副作用?
    dice('5d20') > 80
    dice('5d20') <= 80
    WhereverYouGo
        11
    WhereverYouGo  
       2021-07-15 10:01:32 +08:00
    @JerryCha #8 头像 JK 是什么鬼 😳
    murmur
        12
    murmur  
    OP
       2021-07-15 10:50:21 +08:00
    楼上的兄弟就不一一回了
    1 、离散数学不是科班真的看不懂
    2 、说数据排序和区间树的貌似是不错的思路
    3 、因为有多个分支,所以简单设置 A 和!A 不够
    4 、这个只需要部分校验,不需要做到尽善尽美,不过如果纯数字简单大小区间都判定不了就有点弱了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5120 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 09:43 · PVG 17:43 · LAX 02:43 · JFK 05:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.