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

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']