私はこれらの範囲を持っています:
7,10
11,13
11,15
14,20
23,39
重複していない範囲を指定するには、重複する範囲の結合を実行する必要があるため、例では次のようにします。
7,20
23,39
私はRubyでこれを行い、範囲の開始と終了を配列にプッシュしてソートし、重複する範囲の結合を実行しました。Pythonでこれを行う簡単な方法はありますか?
質問する
14015 次
5 に答える
22
言ってみましょう、(7, 10)そして(11, 13)結果は次のようになり(7, 13)ます：
a = [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39)]
b = []
for begin,end in sorted(a):
if b and b[-1][1] >= begin - 1:
b[-1] = (b[-1][0], end)
else:
b.append((begin, end))
b今でしょ
[(7, 20), (23, 39)]
編集：
@CentAu[(2,4), (1,6)]が正しく認識しているように、(1,4)代わりに(1,6). このケースを正しく処理した新しいバージョンは次のとおりです。
a = [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39)]
b = []
for begin,end in sorted(a):
if b and b[-1][1] >= begin - 1:
b[-1][1] = max(b[-1][1], end)
else:
b.append([begin, end])
于 2013-03-07T14:28:28.440 に答える
14
古い質問。しかし、今後の参考のためにこの回答を追加したいと思いました。 sympyを使用して区間の結合を実現できます。
from sympy import Interval, Union
def union(data):
""" Union of a list of intervals e.g. [(1,2),(3,4)] """
intervals = [Interval(begin, end) for (begin, end) in data]
u = Union(*intervals)
return [list(u.args[:2])] if isinstance(u, Interval) \
else list(u.args)
Union間隔が 2 つを超える出力はUnionオブジェクトであり、間隔が 1 つの場合は出力がIntervalオブジェクトです。if statementそれが return 行の の理由です。
例:
In [26]: union([(10, 12), (14, 16), (15, 22)])
Out[26]: [[10, 12], [14, 22]]
In [27]: union([(10, 12), (9, 16)])
Out[27]: [[9, 16]]
于 2015-12-15T00:47:57.130 に答える
1
(45, 46) と (45, 45) が存在する特定のケースと
、アプリケーションで発生する可能性が低いテスト ケースを試してみました: (11,6) の存在、(-1, -5) の存在、 (-9, 5) の存在、(-3, 10) の存在。
とにかく、これらすべてのケースで結果は正しいです。それはポイントです。
アルゴリズム:
def yi(li):
gen = (x for a,b in li for x in xrange(a,b+1))
start = p = gen.next()
for x in gen:
if x>p+2:
yield (start,p)
start = p = x
else:
p = x
yield (start,x)
aff次のコードで True に設定されている場合、実行のステップが表示されます。
def yi(li):
aff = 0
gen = (x for a,b in li for x in xrange(a,b+1))
start = p = gen.next()
for x in gen:
if aff:
print ('start %s p %d p+2 %d '
'x==%s' % (start,p,p+2,x))
if x>p+2:
if aff:
print 'yield range(%d,%d)' % (start,p+1)
yield (start,p)
start = p = x
else:
p = x
if aff:
print 'yield range(%d,%d)' % (start,x+1)
yield (start,x)
for li in ([(7,10),(23,39),(11,13),(11,15),(14,20),(45,46)],
[(7,10),(23,39),(11,13),(11,15),(14,20),(45,46),(45,45)],
[(7,10),(23,39),(11,13),(11,15),(14,20),(45,45)],
[(7,10),(23,39),(11,13),(11,6),(14,20),(45,46)],
#1 presence of (11, 6)
[(7,10),(23,39),(11,13),(-1,-5),(14,20),(45,45)],
#2 presence of (-1,-5)
[(7,10),(23,39),(11,13),(-9,-5),(14,20),(45,45)],
#3 presence of (-9, -5)
[(7,10),(23,39),(11,13),(-3,10),(14,20),(45,45)]):
#4 presence of (-3, 10)
li.sort()
print 'sorted li %s'%li
print '\n'.join(' (%d,%d) %r' % (a,b,range(a,b))
for a,b in li)
print 'list(yi(li)) %s\n' % list(yi(li))
結果
sorted li [(7, 10), (11, 13), (11, 15), (14, 20),
(23, 39), (45, 46)]
(7,10) [7, 8, 9]
(11,13) [11, 12]
(11,15) [11, 12, 13, 14]
(14,20) [14, 15, 16, 17, 18, 19]
(23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
35, 36, 37, 38]
(45,46) [45]
list(yi(li)) [(7, 20), (23, 39), (45, 46)]
sorted li [(7, 10), (11, 13), (11, 15), (14, 20),
(23, 39), (45, 45), (45, 46)]
(7,10) [7, 8, 9]
(11,13) [11, 12]
(11,15) [11, 12, 13, 14]
(14,20) [14, 15, 16, 17, 18, 19]
(23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
35, 36, 37, 38]
(45,45) []
(45,46) [45]
list(yi(li)) [(7, 20), (23, 39), (45, 46)]
sorted li [(7, 10), (11, 13), (11, 15), (14, 20),
(23, 39), (45, 45)]
(7,10) [7, 8, 9]
(11,13) [11, 12]
(11,15) [11, 12, 13, 14]
(14,20) [14, 15, 16, 17, 18, 19]
(23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
35, 36, 37, 38]
(45,45) []
list(yi(li)) [(7, 20), (23, 39), (45, 45)]
sorted li [(7, 10), (11, 6), (11, 13), (14, 20),
(23, 39), (45, 46)]
(7,10) [7, 8, 9]
(11,6) []
(11,13) [11, 12]
(14,20) [14, 15, 16, 17, 18, 19]
(23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
35, 36, 37, 38]
(45,46) [45]
list(yi(li)) [(7, 20), (23, 39), (45, 46)]
sorted li [(-1, -5), (7, 10), (11, 13), (14, 20),
(23, 39), (45, 45)]
(-1,-5) []
(7,10) [7, 8, 9]
(11,13) [11, 12]
(14,20) [14, 15, 16, 17, 18, 19]
(23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
35, 36, 37, 38]
(45,45) []
list(yi(li)) [(7, 20), (23, 39), (45, 45)]
sorted li [(-9, -5), (7, 10), (11, 13), (14, 20),
(23, 39), (45, 45)]
(-9,-5) [-9, -8, -7, -6]
(7,10) [7, 8, 9]
(11,13) [11, 12]
(14,20) [14, 15, 16, 17, 18, 19]
(23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
35, 36, 37, 38]
(45,45) []
list(yi(li)) [(-9, -5), (7, 20), (23, 39), (45, 45)]
sorted li [(-3, 10), (7, 10), (11, 13), (14, 20),
(23, 39), (45, 45)]
(-3,10) [-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
(7,10) [7, 8, 9]
(11,13) [11, 12]
(14,20) [14, 15, 16, 17, 18, 19]
(23,39) [23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
35, 36, 37, 38]
(45,45) []
list(yi(li)) [(-3, 20), (23, 39), (45, 45)]
于 2013-03-07T16:33:56.793 に答える
0
次の関数は、指定されたサンプル データに対して適切に機能します。
def range_overlap_adjust(list_ranges):
overlap_corrected = []
for start, stop in sorted(list_ranges):
if overlap_corrected and start-1 <= overlap_corrected[-1][1] and stop >= overlap_corrected[-1][1]:
overlap_corrected[-1] = min(overlap_corrected[-1][0], start), stop
elif overlap_corrected and start <= overlap_corrected[-1][1] and stop <= overlap_corrected[-1][1]:
break
else:
overlap_corrected.append((start, stop))
return overlap_corrected
使用法
list_ranges = [(7, 10), (11, 13), (11, 15), (14, 20), (23, 39)]
print(range_overlap_adjust(list_ranges))
# prints [(7, 20), (23, 39)]
于 2015-12-17T22:33:03.123 に答える