python - 找到图上点之间的最长公共(public)间隔

Question

我得到以下输入:

[[['3', '7'], ['9', '17']], [['1', '5'], ['10', '20']], [['0', '6'], ['12', '19']]]

每个子数组由一个或多个元素组成[['3', '7'], ['9', '17']] 表示这个函数1在x = 3 和 x = 7，相同的函数 1 也在 x = 9 和 x = 17 之间增长。 另一个function2在x=1和x=5之间增长，同一个function2在x=10和x=20之间增长。

这可以在这里以更好的格式化方式看到:

[['3', '7'], ['9', '17']]
[['1', '5'], ['10', '20']]
[['0', '6'], ['12', '19']]

我需要找到一种方法来一起计算所有 3 个函数的最大增长间隔。在这种情况下，解是从 x = 12 到 x = 17，因为 17-12 = 5 比任何其他可能的组合都大。

另一个解决方案是 x =3 到 x =5，但由于不是最大的，所以这不是正确的解决方案

是否有 pythonic 方法来找到它？

直到现在我尝试针对这个特定案例计算它，但没有成功。

这是我得到的最简单的案例，而且它只是众多案例中的一个。 我的问题是我找不到比较子列表元素的正确方法，以便获得所有函数在同一时间间隔内增长的位置...

Answer 1

这是我能想到的最简洁的解决方案(有关此处发生的事情的解释，请参见下文):

from itertools import chain, groupby

def get_longest_interval(x):
    longest_interval = max(
        ([v for _, v in grp] for k, grp in groupby(enumerate(
            set.intersection(*(set(chain(*(range(int(start), int(end)+1) for (start, end) in f_intervals))) for f_intervals in x))
        ), lambda (index, num): index-num)), key=len
    )
    return longest_interval[0], longest_interval[-1]

x1 = [[['3', '7'], ['9', '17']],
      [['1', '5'], ['10', '20']],
      [['0', '6'], ['12', '19']]]

x2 = [[[3, 7], [9, 21]],
      [[1, 5], [10, 20]],
      [[0, 6]]]

for x in x1, x2:
    print get_longest_interval(x)

# This prints
(12, 17)
(3, 5)

解释(一旦你创建了一些变量，所有这些都会变得更容易理解):

def get_longest_interval(x):
    # Get available ranges for every function
    function_ranges = [
        set(
            # By chaining and unpacking them so (2 -> 4), (7 -> 9) becomes (2, 3, 4, 7, 8, 9)
            chain(*(range(int(start), int(end)+1) for (start, end) in f_intervals))
        ) for f_intervals in x
    ]
    print "Function ranges", function_ranges

    # Get the intersection of all the ranges:
    #   This is the only place where everyone is increasing
    valid_range = set.intersection(*function_ranges)
    print "Valid range", valid_range

    # Use python recipe to get groups of consecutive numbers using groupby
    # https://docs.python.org/2.6/library/itertools.html#examples
    # (3, 4, 5, 12, 13, 14, 15, 16, 17) -> ([3, 4, 5], [12, 13, 14, 15, 16, 17])
    # Then take the one that contains the most elements (max by length)
    longest_interval = max(
        ([v for _, v in grp] for k, grp in groupby(enumerate(valid_range), lambda (index, num): index-num)), key=len
    )
    return longest_interval[0], longest_interval[-1]

# This prints
Function ranges [set([3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17]), set([1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]), set([0, 1, 2, 3, 4, 5, 6, 12, 13, 14, 15, 16, 17, 18, 19])]
Valid range set([3, 4, 5, 12, 13, 14, 15, 16, 17])
(12, 17)
Function ranges [set([3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21]), set([1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]), set([0, 1, 2, 3, 4, 5, 6])]
Valid range set([3, 4, 5])
(3, 5)