겹치는 범위 세트를 겹치지 않는 범위로 나누는 방법은 무엇입니까?
https://stackoverflow.com/questions/628837
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
범위 세트가 있다고 가정 해 봅시다.
- 0-100 : 'a'
- 0-75 : 'b'
- 95-150 : 'C'
- 120-130 : 'D'
분명히, 이러한 범위는 특정 지점에서 겹칩니다. 원래 범위와 관련된 정보를 유지하면서 (이 경우 범위 이후의 문자)이 범위가 아닌 범위 목록을 생성하기 위해 이러한 범위를 어떻게 해부 하시겠습니까?
예를 들어, 알고리즘을 실행 한 후 위의 결과는 다음과 같습니다.
- 0-75 : 'a', 'b'
- 76-94 : 'a'
- 95-100 : 'a', 'c'
- 101-119 : 'C'
- 120-130 : 'c', 'd'
- 131-150 : 'C'
해결책
오디오 샘플을 혼합 (부분적으로 겹치는) 프로그램을 작성할 때도 같은 질문이있었습니다.
내가 한 일은 "시작 이벤트"와 "각 항목에 대한"스톱 이벤트 "(각 항목에 대한)을 목록에 추가하고 시간에 따라 목록을 정렬 한 다음 순서대로 처리하는 것입니다. 시간 대신 정수 지점을 사용하는 것을 제외하고는 동일한 작업을 수행 할 수 있으며 사운드를 혼합하는 대신 범위에 해당하는 세트에 기호를 추가합니다. 빈 범위를 생성하든 생략하든 선택 사항은 선택 사항입니다.
Edit 아마도 일부 코드 ...
# input = list of (start, stop, symbol) tuples
points = [] # list of (offset, plus/minus, symbol) tuples
for start,stop,symbol in input:
points.append((start,'+',symbol))
points.append((stop,'-',symbol))
points.sort()
ranges = [] # output list of (start, stop, symbol_set) tuples
current_set = set()
last_start = None
for offset,pm,symbol in points:
if pm == '+':
if last_start is not None:
#TODO avoid outputting empty or trivial ranges
ranges.append((last_start,offset-1,current_set))
current_set.add(symbol)
last_start = offset
elif pm == '-':
# Getting a minus without a last_start is unpossible here, so not handled
ranges.append((last_start,offset-1,current_set))
current_set.remove(symbol)
last_start = offset
# Finish off
if last_start is not None:
ranges.append((last_start,offset-1,current_set))
완전히 테스트되지 않았습니다.
다른 팁
나는 엔드 포인트 목록을 만들고 정렬하고, 시작 및 종료 지점에 의해 범위 목록을 색인한다고 말합니다. 그런 다음 정렬 된 엔드 포인트 목록을 반복하고 각각의 경우 범위를 확인하여 해당 시점에서 어떤 범위가 시작/정지되는지 확인하십시오.
이것은 아마도 코드로 더 잘 표현 될 것입니다 ... 당신의 범위가 튜플로 표시되는 경우 :
ranges = [(0,100,'a'),(0,75,'b'),(95,150,'c'),(120,130,'d')]
endpoints = sorted(list(set([r[0] for r in ranges] + [r[1] for r in ranges])))
start = {}
end = {}
for e in endpoints:
start[e] = set()
end[e] = set()
for r in ranges:
start[r[0]].add(r[2])
end[r[1]].add(r[2])
current_ranges = set()
for e1, e2 in zip(endpoints[:-1], endpoints[1:]):
current_ranges.difference_update(end[e1])
current_ranges.update(start[e1])
print '%d - %d: %s' % (e1, e2, ','.join(current_ranges))
이것을 회고 적으로 살펴 보지만, 더 효율적이고 (또는 적어도 깨끗한) 방법이 없다면 놀랄 것입니다.
당신이 설명하는 것은 세트 이론의 예입니다. 노조, 교차로 및 세트 차이를위한 일반적인 알고리즘은 다음을 참조하십시오.
www.gvu.gatech.edu/~jarek/graphics/papers/04polygonbooleansmargalit.pdf
이 논문은 그래픽을 대상으로하지만 일반 세트 이론에도 적용됩니다. 정확히 가벼운 독서 자료가 아닙니다.
의사 코드 :
unusedRanges = [ (each of your ranges) ]
rangesInUse = []
usedRanges = []
beginningBoundary = nil
boundaries = [ list of all your ranges' start and end values, sorted ]
resultRanges = []
for (boundary in boundaries) {
rangesStarting = []
rangesEnding = []
// determine which ranges begin at this boundary
for (range in unusedRanges) {
if (range.begin == boundary) {
rangesStarting.add(range)
}
}
// if there are any new ones, start a new range
if (rangesStarting isn't empty) {
if (beginningBoundary isn't nil) {
// add the range we just passed
resultRanges.add(beginningBoundary, boundary - 1, [collected values from rangesInUse])
}
// note that we are starting a new range
beginningBoundary = boundary
for (range in rangesStarting) {
rangesInUse.add(range)
unusedRanges.remove(range)
}
}
// determine which ranges end at this boundary
for (range in rangesInUse) {
if (range.end == boundary) {
rangesEnding.add(range)
}
}
// if any boundaries are ending, stop the range
if (rangesEnding isn't empty) {
// add the range up to this boundary
resultRanges.add(beginningBoundary, boundary, [collected values from rangesInUse]
for (range in rangesEnding) {
usedRanges.add(range)
rangesInUse.remove(range)
}
if (rangesInUse isn't empty) {
// some ranges didn't end; note that we are starting a new range
beginningBoundary = boundary + 1
}
else {
beginningBoundary = nil
}
}
}
단위 테스트 :
결국, 결과는 당신이 찾고있는 결과를 가져야하고, 사용하지 않는 rangesinuse는 비어 있어야하고, 초기화는 nil이어야하며, 중고 방향에는 미사용 rang에 사용 된 것을 포함해야합니다 (그러나 Range.end에 의해 정렬 됨).
(1,1)와 같은 간격에 대한 지원을 포함하여 테스트 된 Edmunds와의 유사한 답변 : :
class MultiSet(object):
def __init__(self, intervals):
self.intervals = intervals
self.events = None
def split_ranges(self):
self.events = []
for start, stop, symbol in self.intervals:
self.events.append((start, True, stop, symbol))
self.events.append((stop, False, start, symbol))
def event_key(event):
key_endpoint, key_is_start, key_other, _ = event
key_order = 0 if key_is_start else 1
return key_endpoint, key_order, key_other
self.events.sort(key=event_key)
current_set = set()
ranges = []
current_start = -1
for endpoint, is_start, other, symbol in self.events:
if is_start:
if current_start != -1 and endpoint != current_start and \
endpoint - 1 >= current_start and current_set:
ranges.append((current_start, endpoint - 1, current_set.copy()))
current_start = endpoint
current_set.add(symbol)
else:
if current_start != -1 and endpoint >= current_start and current_set:
ranges.append((current_start, endpoint, current_set.copy()))
current_set.remove(symbol)
current_start = endpoint + 1
return ranges
if __name__ == '__main__':
intervals = [
(0, 100, 'a'), (0, 75, 'b'), (75, 80, 'd'), (95, 150, 'c'),
(120, 130, 'd'), (160, 175, 'e'), (165, 180, 'a')
]
multiset = MultiSet(intervals)
pprint.pprint(multiset.split_ranges())
[(0, 74, {'b', 'a'}),
(75, 75, {'d', 'b', 'a'}),
(76, 80, {'d', 'a'}),
(81, 94, {'a'}),
(95, 100, {'c', 'a'}),
(101, 119, {'c'}),
(120, 130, {'d', 'c'}),
(131, 150, {'c'}),
(160, 164, {'e'}),
(165, 175, {'e', 'a'}),
(176, 180, {'a'})]
