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

なんて云えば良いかよく分からないので,タイトルもよく分からないけど.

Best way to return minimum number of ranges from a collection of ranges – StackOverflow

これは非常に簡単.[[下限, 上限],[下限, 上限]…]な形で,
全体をカバーする範囲を求めるだけなので,

[[下限], [上限]]とそれぞれのグループを作って,minとmaxを求めれば良い.

a = [[14,17], [4,7], [2,5], [10,12] , [15,16], [4,9], [11,13]]
a_ = list(zip(*a))
min(a_[0]), max(a_[1])

(2, 17)

min, maxは結局ソートと一緒なので対数時間.
list(zip(*a))の計算量はよく分からないけど,多分O(n)(実測に基づく).

なので,全体としてはO(n)な解法.
 
 
 

これをもうちょっと複雑にした問題が,

Algorithm for Intersection (or Merge) of Numerical Ranges – StackOverflow

図でみると分かり易いが,

FireShot Capture 271 - JupyterLab Alpha Preview - http___localhost_8888_lab

3つのクラスタに分かれる様にみえる.

方法は色々あると思うけど,ここでは端点が含まれるか否かでグルーピングを考える.

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

{0: [[0, 3], [1, 4]], 1: [[6, 7]], 2: [[9, 14], [14, 16], [15, 15]]}

3つにグルーピングできる事が分かる.後は,それぞれの下限,上限を求めれば良い.

for k, v in res.items():
    res_ = list(zip(*v))
    print(f'---group{k}---')
    print(f'ranges: [{min(res_[0])}, {max(res_[1])}]')

—group0—
ranges: [0, 4]
—group1—
ranges: [6, 7]
—group2—
ranges: [9, 16]
 
 
 
一つ目の問題をこれと同様に考えればどうなるか.

改めて,グラフにしてみると,

a = [[14,17], [4,7], [2,5], [10,12] , [15,16], [4,9], [11,13]]
fig = plt.figure()
ax = fig.add_subplot(111)
for i, x in enumerate(a):
    ax.plot(x, [i, i], marker='o', linewidth=3)

FireShot Capture 272 - JupyterLab Alpha Preview - http___localhost_8888_lab

これも3つのクラスタに分かれている様にみえる.
同様の方法でグルーピング及びレンジを表してみると,

a = [[14,17], [4,7], [2,5], [10,12] , [15,16], [4,9], [11,13]]
li = sorted(a)
g = 0
res = {}
for i, x in enumerate(li):
    s, e = x
    if i == 0:
        res.setdefault(g, []).append([s, e])
    else:
        if li[i-1][0] <= s <= li[i-1][1]:
            res.setdefault(g, []).append([s, e])
        else:
            g += 1
            res.setdefault(g, []).append([s, e])

for k, v in res.items():
    res_ = list(zip(*v))
    print(f'---group{k}---')
    print(f'ranges: [{min(res_[0])}, {max(res_[1])}]')

—group0—
ranges: [2, 9]
—group1—
ranges: [10, 13]
—group2—
ranges: [14, 17]

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

数値範囲の交差に関するアルゴリズム問題,範囲集合をコンパクトに表す方法 への4件のフィードバック

  1. ピンバック: 重複しない範囲 | 粉末@それは風のように (日記)

  2. ピンバック: リスト内の連続する値のグループをピックアップ | 粉末@それは風のように (日記)

  3. ピンバック: リスト内の要素に応じてグルーピング | 粉末@それは風のように (日記)

  4. ピンバック: 年齢を値に持つリストを任意の範囲でグルーピング | 粉末@それは風のように (日記)

コメントを残す

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

WordPress.com ロゴ

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

Twitter 画像

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

Facebook の写真

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

Google+ フォト

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

%s と連携中