最频繁重叠的范围 - Python3.x

Question

我是初学者，正在尝试编写列出范围列表中最频繁重叠范围的代码。

所以，输入是各种范围（示例图中的#1 到#7；https://prntscr.com/kj80xl），我想找到最常见的范围（在示例中，7 个中有 6 个是 3,000-4,000 - 86 %)。实际上，我想找到最常见的前 5 个。

并非所有范围都重叠。范围始终为正，并以具有 1 个距离（标准范围）的整数形式给出。

我现在只有将一个序列与另一个序列进行比较并返回重叠部分的代码，但在那之后我就卡住了。

def range_overlap(range_x,range_y):
    x = (range_x[0], (range_x[-1])+1)
    y = (range_y[0], (range_y[-1])+1)

    overlap = (max(x[0],y[0]),min(x[-1],(y[-1])))
    if overlap[0] <= overlap[1]:
        return range(overlap[0], overlap[1])
    else:
        return "Out of range"

如有任何帮助，我将不胜感激。

Answer 1

您可以先将您的函数更改为 return 两种情况下的有效范围，以便您可以在一组比较中使用它。此外，由于 Python 的 range 对象不是已经创建的可迭代对象，而是仅获取范围的 start、stop 和 step 属性并创建的智能对象范围按需，你也可以对你的功能做一点改变。

def range_overlap(range_x,range_y):
    rng = range(max(range_x.start, range_y.start),
                min(range_x.stop, range_y.stop)+1)
    if rng.start < rng.stop:
        return rng.start, rng.stop

现在，如果您有一组范围并且想要比较所有对，您可以使用 itertools.combinations 获取所有对，然后使用 range_overlap 和 collections.Counter可以找到重叠范围的数量。

from collections import Counter
from itertools import combinations

overlaps = Counter(range_overlap(i,j) for i, j in 
             combinations(list_of_ranges, 2))

Answer 2

更好的解决方案

我想到了一个更简单的解决方案（至少恕我直言）所以这里是：

def get_abs_min(ranges):
    return min([min(r) for r in ranges])


def get_abs_max(ranges):
    return max([max(r) for r in ranges])


def count_appearances(i, ranges):
    return sum([1 for r in ranges if i in r])


def create_histogram(ranges):
    keys = [str(i) for i in range(len(ranges) + 1)]
    histogram = dict.fromkeys(keys)
    results = []
    min = get_abs_min(range_list)
    max = get_abs_max(range_list)

    for i in range(min, max):
        count = str(count_appearances(i, ranges))

        if histogram[count] is None:
            histogram[count] = dict(start=i, end=None)

        elif histogram[count]['end'] is None:
            histogram[count]['end'] = i

        elif histogram[count]['end'] == i - 1:
            histogram[count]['end'] = i

        else:
            start = histogram[count]['start']
            end = histogram[count]['end']
            results.append((range(start, end + 1), count))
            histogram[count]['start'] = i
            histogram[count]['end'] = None

    for count, d in histogram.items():
        if d is not None and d['start'] is not None and d['end'] is not None:
            results.append((range(d['start'], d['end'] + 1), count))

    return results


def main(ranges, top):
    appearances = create_histogram(ranges)
    return sorted(appearances, key=lambda t: t[1], reverse=True)[:top]

这里的想法很简单，就是迭代所有范围的叠加并构建外观直方图（例如，当前 i 出现的原始范围的数量）

之后只需根据选择的结果大小进行排序和切片。

只需调用 main 并提供您想要的范围和最高数字（或者 None 如果您想查看所有结果）。

以下是较早的编辑

我（几乎）同意@Kasramvd 的回答。

这是我的看法：

from collections import Counter
from itertools import combinations

def range_overlap(x, y):
    common_part = list(set(x) & set(y))
    if common_part:
        return range(common_part[0], common_part[-1] +1)
    else:
        return False

def get_most_common(range_list, top_frequent):
    overlaps = Counter(range_overlap(i, j) for i, j in 
         combinations(list_of_ranges, 2))
    return [(r, i) for (r, i) in  overlaps.most_common(top_frequent) if r]

你需要输入range_list和你想要的top_frequent个数。

编辑

之前的答案针对范围列表中所有 2 的组合解决了这个问题。

此编辑已根据您的输入和正确答案的结果进行测试：

from collections import Counter
from itertools import combinations

def range_overlap(*args):
    sets = [set(r) for r in args]
    common_part = list(set(args[0]).intersection(*sets))
    if common_part:
        return range(common_part[0], common_part[-1] +1)
    else:
        return False

def get_all_possible_combinations(range_list):
    all_combos = []
    for i in range(2, len(range_list)):
        all_combos.append(combinations(range_list, i))
    all_combos = [list(combo) for combo in all_combos]
    return all_combos


def get_most_common_for_combo(combo):
    return list(filter(None, [range_overlap(*option) for option in combo]))


def get_most_common(range_list, top_frequent):
    all_overlaps = []
    combos = get_all_possible_combinations(range_list)
    for combo in combos:
        all_overlaps.extend(get_most_common_for_combo(combo))
    return [r for (r, i) in  Counter(all_overlaps).most_common(top_frequent) if r]

并得到结果运行 get_most_common(range_list, top_frequent)

在我的机器上测试（ubunut 16.04，python 3.5.2），输入 range_list 和 top_frequent = 5 结果：

[range(3000, 4000), range(2500, 4000), range(1500, 4000), range(3000, 6000), range(1, 4000)]

最频繁重叠的范围 - Python3.x

Most frequently overlapping range - Python3.x

python

python-3.x

range

overlap

更好的解决方案

以下是较早的编辑

编辑