将关系运算符列表优化为最小集

Question

在给定关系运算符的输入列表的情况下，是否可以创建一个算法来查找关系运算符的最小集合？我不确定我是否对这个问题使用了正确的数学命名法。

例如，如果操作员列表：

[x > 1, x > 3], minimal set: [x > 1]
[x < 1, x > 3], minimal set: [x < 1, x > 3]
[x > 1, x < 2], minimal set: undefined

当然，列表的长度是任意的。

[x > 1, x > 3, x > 5], minimal set: [x > 1]

解决方案是只保持当前的最小值和最大值，然后在比较器列表中迭代吗？从编译器理论来看，有没有更优化的方法来解析这些值？

Answer 1

只需迭代比较列表，并为每个变量记住上限和下限。下面是一个非常直接的Python实现。

def find_bounds(lst):
    bounds = {}
    for var, op, val in map(str.split, lst):
        if var not in bounds: bounds[var] = [float("-inf"), float("+inf")]
        if op == ">":
            bounds[var][0] = max(bounds[var][0], float(val))
        if op == "<":
            bounds[var][1] = min(bounds[var][1], float(val))
    return bounds

示例：

>>> find_bounds(["x > 3", "x < 6", "x > 4", "x < 9"])
{'x': [4.0, 6.0]}
>>> find_bounds(["x > 5", "x < 1", "x < 10"])
{'x': [5.0, 1.0]}
>>> find_bounds(["x > 3", "x < 9", "y > 3"])
{'x': [3.0, 9.0], 'y': [3.0, inf]}

接下来，您可以用一个函数来补充这一点，该函数将这些边界重新转换为比较：

def bounds_to_comparisons(bounds):
    result = []
    for var in bounds:
        lower, upper = bounds[var]
        if lower < upper:
            if lower != float("-inf"):
                result.append("%s > %f" % (var, lower))
            if upper != float("+inf"):
                result.append("%s < %f" % (var, upper))
        else:
            result.append("%s undefined" % var)
    return result

示例：

>>> bounds_to_comparisons({'x': [4.0, 6.0]})
['x > 4.00', 'x < 6.00']
>>> bounds_to_comparisons({'x': [5.0, 1.0]})
['x undefined']
>>> bounds_to_comparisons({'y': [3.0, inf], 'x': [3.0, 9.0]})
['y > 3.00', 'x > 3.00', 'x < 9.00']

Answer 2

Other一旦发现未定义的结果，就会提前中止，无法进行优化。必须处理所有条目，并且每个条目只处理一次。