图上点间最长公共间隔的求取

Question

我得到以下意见：

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

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

在这里可以以更好的格式化方式看到这一点：

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

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

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

有什么办法能找到这个吗？

直到现在，我试着为这个特定的案例计算它，但没有成功。

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

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)

Answer 2

如果只有整数，您可以使用类似的东西(与任意数量的函数和间隔一起工作)：

def full(bornes):
    return [k for k in range(bornes[0], bornes[1] + 1)]

li = [[[0, 8], [9, 17]], [[1, 8], [10, 20]], [[0, 8], [12, 19]]]
li2 = []
for function in li:
    li2.append([full(domain) for domain in function])

dict = {}
for function in li2:
    for domain in function:
        for number in domain:
            if not number in dict:
                dict[number] = 1
            else:
                dict[number] += 1

dict = {k:v for k,v in dict.iteritems() if v == len(li2)}

x_longuest = None
x_current = None
current = 0
longuest = 0
for key in dict:
    if key+1 in dict:
        if current == 0:
            x_current = key
        current += 1
    else:
        if current > longuest:
            longuest = current
            x_longuest = x_current
        current = 0

if current > longuest:
    longuest = current
    x_longuest = x_current

print(x_longuest, longuest)

其思想是用已定义的域创建一个字典，然后只保留定义所有函数的点，然后在字典中签入Lon来宾链。

Answer 3

让我勾勒出一个想法。

首先，获取所有可能的组合的列表。

listOfCombinations = list(itertools.product(function1, function2, function3))

其次，循环遍历该列表，取下界的最大值和上界的最小值。然后检查一下这是否是你迄今发现的最大的不同之处。

for item in listOfCombinations:
    val1 = max(item[0][0], item[1][0], item[2][0])
    val2 = min(item[0][1], item[1][1], item[2][1])
    range = val2 - val1
    if range > maxRange:
        maxRange = range