查找所有可能在结束和开始时重叠的组合 [英] Find all possible combinations that overlap by end and start

问题描述

在帖子找到所有具有非重叠区域的组合(粘贴在下面的代码中)，该函数将获得一组元组，并以递归方式查找具有不重叠值的每个可能的元组集合.在元组列表上 T = [(0.0，2.0)，(0.0，4.0)，(2.5，4.5)，(2.0，5.75)，(2.0，4.0)，(6.0，7.25)] ，例如，我们得到

In the post find all combinations with non-overlapped regions (code pasted below), the function is given a set of tuples and it recursively finds every possible collection of tuples with non-overlapping values. On the list of tuples T = [(0.0, 2.0), (0.0, 4.0), (2.5, 4.5), (2.0, 5.75), (2.0, 4.0), (6.0, 7.25)], for example, we get

def nonovl(l, idx, right, ll):
    if idx == len(l):
        if ll:
            print(ll)
        return

    next = idx + 1  
    while next < len(l) and right >= l[next][0]:
        next += 1
    nonovl(l, next, right, ll)

    next = idx + 1
    right = l[idx][1]
    while next < len(l) and right >= l[next][0]:
        next += 1
    nonovl(l, next, right, ll + str(l[idx]))

>>> T = [(0.0, 2.0), (0.0, 4.0), (2.5, 4.5), (2.0, 5.75), (2.0, 4.0), (6.0, 7.25)]
>>> l.sort()
>>> nonovl(l, 0, -1, "")
(6.0, 7.25)
(2.5, 4.5)
(2.5, 4.5)(6.0, 7.25)
(2.0, 5.75)
(2.0, 5.75)(6.0, 7.25)
(2.0, 4.0)
(2.0, 4.0)(6.0, 7.25)
(0.0, 4.0)
(0.0, 4.0)(6.0, 7.25)
(0.0, 2.0)
(0.0, 2.0)(6.0, 7.25)
(0.0, 2.0)(2.5, 4.5)
(0.0, 2.0)(2.5, 4.5)(6.0, 7.25)

我们如何修改 nonovl()函数，使其也允许两个元组的起始值和结束值重叠的组合?例如，在同一列表上运行它，我们将也获取:

How might we modify the nonovl() function so that it also allows for combinations that overlap by the start and end values of two tuples? Running it on the same list, for example, we would also get:

(0.0, 2.0)(2.0, 4.0)(6.0, 7.25)

推荐答案

将> = 更改为> .现在，如果下一个"元组的左索引值小于" 或等于 "的右索引值，则代码会跳过下一个"元组当前的"元组.它会找到第一个元组，其左索引值严格大于当前元组的右索引值.

Change >= to >. Right now, the code skips over the "next" tuple if the left index value of the "next" tuple is less than or equal to the right index value of the "current" tuple. It finds the first tuple that has a left index value that is strictly greater than the current tuple's right index value.

def nonovl(l, idx, right, ll):
    if idx == len(l):
        if ll:
            print(ll)
        return

    next = idx + 1  
    while next < len(l) and right > l[next][0]:
        next += 1
    nonovl(l, next, right, ll)

    next = idx + 1
    right = l[idx][1]
    while next < len(l) and right > l[next][0]:
        next += 1
    nonovl(l, next, right, ll + str(l[idx]))

输出:

(6.0, 7.25)
(2.5, 4.5)
(2.5, 4.5)(6.0, 7.25)
(2.0, 5.75)
(2.0, 5.75)(6.0, 7.25)
(2.0, 4.0)
(2.0, 4.0)(6.0, 7.25)
(0.0, 4.0)
(0.0, 4.0)(6.0, 7.25)
(0.0, 2.0)
(0.0, 2.0)(6.0, 7.25)
(0.0, 2.0)(2.5, 4.5)
(0.0, 2.0)(2.5, 4.5)(6.0, 7.25)
(0.0, 2.0)(2.0, 5.75)
(0.0, 2.0)(2.0, 5.75)(6.0, 7.25)
(0.0, 2.0)(2.0, 4.0)
(0.0, 2.0)(2.0, 4.0)(6.0, 7.25)

这篇关于查找所有可能在结束和开始时重叠的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！