algorithm - 将不等式合并为一个

Question

假设我有n个不等式如下:

输入:

例子:n=4

f4 > f2 > f3
f4 > f1 > f3
f4 > f2 > f1
f2 > f1 > f3

输出:

我必须合并这些不等式以产生 1 个不等式，从而使上述不等式保持为真。对于上面的例子:

f4 > f2 > f1 > f3

可以有多个不等式作为答案；我需要任何一个是正确的。对于给定的输入，也肯定存在一个解决方案；也就是说，我们可以假设输入始终有效。

关于如何制定算法来实现这个的任何想法？

我一直认为有向图可以用于此，但我不确定。

有什么想法可以实现上述算法吗？ n 的值可以很大。

Answer 1

此解决方案提取所有两项不等式并执行服从它们的排序:

Python 2.7.5 (default, May 15 2013, 22:43:36) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ineq = """f4 > f2 > f3
f4 > f1 > f3
f4 > f2 > f1
f2 > f1 > f3"""
>>> print(ineq)
f4 > f2 > f3
f4 > f1 > f3
f4 > f2 > f1
f2 > f1 > f3
>>> greater_thans, all_f = set(), set()
>>> for line in ineq.split('\n'):
    tokens = line.strip().split()[::2]
    for n, t1 in enumerate(tokens[:-1]):
        for t2 in tokens[n+1:]:
            greater_thans.add((t1, t2))
            all_f.add(t1)
        all_f.add(t2)


>>> sorted(all_f, cmp=lambda t1, t2: 0 if t1==t2 else (1 if (t1, t2) not in greater_thans else -1))
['f4', 'f2', 'f1', 'f3']
>>> 

群里的好心人comp.lang.python指出如果原始关系集不包括 every 小于关系，那么排序可能会失败，因此我需要添加一个函数 expand_transitive_relations:

from __future__ import print_function
from itertools import permutations


def extract_relations(ineq):
    "Turns lines of lists of relations separated by '>' into set of tuples of (x,y) pairs where x > y"
    greater_thans, all_f = set(), set()
    for line in ineq.split('\n'):
        tokens = line.strip().split()[::2]
        for n, t1 in enumerate(tokens[:-1]):
            for t2 in tokens[n+1:]:
                greater_thans.add((t1, t2))
                all_f.add(t1)
            all_f.add(t2)
    expanded = expand_transitive_ralations(greater_thans, all_f)
    return sorted(all_f, cmp=lambda t1, t2: 0 if t1==t2 else 
                                            (1 if (t1, t2) not in expanded else -1))

def expand_transitive_ralations(greater_thans, all_f):
    "if x > y and y > z then x > z"
    start_len = len(greater_thans)
    while True:
        for x, y, z in permutations(all_f, 3):
            if (x, y) in greater_thans and (y, z) in greater_thans:
                greater_thans.add((x, z))
        new_len = len(greater_thans)
        if start_len == new_len:
            break
        else:
            start_len = new_len
    return greater_thans

if __name__ == '__main__':
    for ineq in (
            """\
            f4 > f2 > f3
            f4 > f1 > f3
            f4 > f2 > f1
            f2 > f1 > f3\
            """,
            """\
            f4 > f2 > f3 
            f4 > f1 > f3 
            f4 > f2 > f1 
            f2 > f1 > f3 
            f3 > f5\
            """,
            """\
            f2 > f3 
            f3 > f1\
            """):
        print(ineq)
        print('  Becomes:', ' > '.join(extract_relations(ineq)), '\n')

输出:

            f4 > f2 > f3
            f4 > f1 > f3
            f4 > f2 > f1
            f2 > f1 > f3            
  Becomes: f4 > f2 > f1 > f3 

            f4 > f2 > f3 
            f4 > f1 > f3 
            f4 > f2 > f1 
            f2 > f1 > f3 
            f3 > f5            
  Becomes: f4 > f2 > f1 > f3 > f5 

            f2 > f3 
            f3 > f1            
  Becomes: f2 > f3 > f1