3つのリストからスパンのセットが重複する値を見つける方法は?

How to find value where set of spans overlap from 3 lists? [on hold] – StackOverflow

効率はともかくとして,集合を取ればいい.

a = [3,7, 13,17, 21,27]
b = [1,5, 8,11, 14,16, 24,26]
c = [5,7, 9,10, 14,17, 22,25]

a = list(zip(a[::2], a[1::2]))
b = list(zip(b[::2], b[1::2]))
c = list(zip(c[::2], c[1::2]))
li, g, d = sorted(a+b+c), 0, {}
for i, (s, e) in enumerate(li):
    if i == 0:
        d.setdefault(g, []).append(list(range(s, e+1)))
    else:
        if li[i-1][0] <= s <= li[i-1][1]:
            d.setdefault(g, []).append(list(range(s, e+1)))
        else:
            g += 1
            d.setdefault(g, []).append(list(range(s, e+1)))

res = []
for v in d.values():
    if len(v) != 3:  continue
    s = set(v[0])
    for l in v[1:]:
        s = s.intersection(l)
    res.extend(s)
res.sort()
res
[5, 14, 15, 16, 24, 25]

多分,O(n log n)で解ける(と思う).

from functools import reduce
from operator import add
from collections import defaultdict


def make_ranges_lst(*args):
    def _f(a): return list(zip(a[::2], a[1::2]))
    return sorted(reduce(add, map(_f, args)))


def groupby_ranges(lst, g=0):
    dd = defaultdict(list)
    for i, (s, e) in enumerate(li):
        if i != 0 and not (li[i-1][0] <= s <= li[i-1][1]):
            g += 1
        dd[g].append(range(s, e+1))
    return dd


def set_ranges(lst, N=3):
    def _f(lst):
        for v in lst:
            if len(v) != N:  continue
            s = set(v[0])
            for l in v[1:]:
                s = s.intersection(l)
            yield from s
    return sorted(_f(lst))


a = [3,7, 13,17, 21,27]
b = [1,5, 8,11, 14,16, 24,26]
c = [5,7, 9,10, 14,17, 22,25]

li = make_ranges_lst(a, b, c)
dd = groupby_ranges(li)
set_ranges(dd.values())
[5, 14, 15, 16, 24, 25]
from functools import reduce
from operator import add
from itertools import chain


def make_ranges_lst(*args):
    def _f(a): return list(zip(a[::2], a[1::2]))
    return sorted(reduce(add, map(_f, args)))


def set_groupby_ranges(lst, t=3, g=0):
    d, c = {}, 1
    for i, (s, e) in enumerate(li):
        if not (li[i-1][0] <= s <= li[i-1][1]):
            if i!=0 and c < t: d.pop(g)
            g += 1
            d[g] = set(range(s, e+1))
            c = 1
        else:
            d[g] = d[g].intersection(range(s, e+1))
            c += 1
    return d
 

a = [3,7, 13,17, 21,27]
b = [1,5, 8,11, 14,16, 24,26]
c = [5,7, 9,10, 14,17, 22,25]

li = make_ranges_lst(a, b, c)
d = set_groupby_ranges(li)
sorted(chain.from_iterable(d.values()))
[5, 14, 15, 16, 24, 25]

 
 
関連:
数値範囲の交差に関するアルゴリズム問題,範囲集合をコンパクトに表す方法

広告
カテゴリー: 未分類 パーマリンク

3つのリストからスパンのセットが重複する値を見つける方法は? への2件のフィードバック

  1. ピンバック: 2つのリスト内の範囲が交差しない範囲集合を求める | 粉末@それは風のように (日記)

  2. ピンバック: 重畳区間を結合 – 数値範囲の交差 | 粉末@それは風のように (日記)

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください