잠재적으로 겹치는 숫자 범위 목록을 병합 (분할)하는 좋은 방법을 찾고 있습니다. 이 문제는이 질문과 매우 유사합니다. 겹치는 날짜 범위를 분할하는 가장 빠른 방법 및 기타 여러 가지.
그러나 범위는 정수 일뿐 만 아니라 Javascript 또는 Python 등에서 쉽게 구현할 수있는 괜찮은 알고리즘을 찾고 있습니다.
데이터 예 :
솔루션 예 :
이것이 중복이라면 사과하지만 아직 해결책을 찾지 못했습니다.
답변
스택을 사용하여 왼쪽에서 오른쪽으로 이동하여 현재 사용중인 색상을 추적합니다. 불연속 맵 대신 데이터 세트의 10 개 숫자를 중단 점으로 사용하십시오.
빈 스택으로 시작 start
하여 0으로 설정 하면 끝까지 도달합니다.
- 스택이 비어있는 경우 :
- 에서 또는 이후에 시작하는 첫 번째 색상을
start
찾아서 색상이 낮은 모든 색상을 스택에 밀어 넣습니다. 병합 된 목록에서 해당 색상의 시작을 표시하십시오.
- 에서 또는 이후에 시작하는 첫 번째 색상을
- else (비어 있지 않은 경우) :
- 에서 또는 이후에 높은 등급의 색상에 대한 다음 시작점을
start
찾고 현재 색상의 끝을 찾습니다- 다음 색상이 먼저 시작되면 색상과 그 밖의 다른 것을 스택에 밀어 넣습니다. 현재 색의 끝을이 색의 시작으로 업데이트하고이 색의 시작을 병합 된 목록에 추가하십시오.
- 아무 것도없고 현재 색상이 먼저 끝나는
start
경우이 색상의 끝으로 설정 하고 스택에서 튀어 나와 다음으로 높은 등급의 색상을 확인하십시오start
다음 색상 범위 내에 있으면 에서 시작하여이 색상을 병합 된 목록에 추가하십시오start
.- 스택이 비면 루프를 계속 진행하십시오 (첫 번째 글 머리 기호로 돌아 가기).
- 에서 또는 이후에 높은 등급의 색상에 대한 다음 시작점을
이것은 예제 데이터가 주어지면 정신적으로 실행됩니다.
# Initial data.
flattened = []
stack = []
start = 0
# Stack is empty. Look for the next starting point at 0 or later: "b", 0 - Push it and all lower levels onto stack
flattened = [ (b, 0, ?) ]
stack = [ r, b ]
start = 0
# End of "b" is 5.4, next higher-colored start is "g" at 2 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, ?) ]
stack = [ r, b, g ]
start = 2
# End of "g" is 12, next higher-colored start is "y" at 3.5 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, ?) ]
stack = [ r, b, g, y ]
start = 3.5
# End of "y" is 6.7, next higher-colored start is "o" at 6.7 - Delimit and continue
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, ?) ]
stack = [ r, b, g, y, o ]
start = 6.7
# End of "o" is 10, and there is nothing starting at 12 or later in a higher color. Next off stack, "y", has already ended. Next off stack, "g", has not ended. Delimit and continue.
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, ?) ]
stack = [ r, b, g ]
start = 10
# End of "g" is 12, there is nothing starting at 12 or later in a higher color. Next off stack, "b", is out of range (already ended). Next off stack, "r", is out of range (not started). Mark end of current color:
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12) ]
stack = []
start = 12
# Stack is empty. Look for the next starting point at 12 or later: "r", 12.5 - Push onto stack
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12), (r, 12.5, ?) ]
stack = [ r ]
start = 12
# End of "r" is 13.8, and there is nothing starting at 12 or higher in a higher color. Mark end and pop off stack.
flattened = [ (b, 0, 2), (g, 2, 3.5), (y, 3.5, 6.7), (o, 6.7, 10), (g, 10, 12), (r, 12.5, 13.8) ]
stack = []
start = 13.8
# Stack is empty and nothing is past 13.8 - We're done.
답변
이 솔루션은 가장 단순 해 보입니다. (또는 적어도 이해하기 가장 쉬운 방법)
필요한 것은 두 범위를 빼는 기능입니다. 다시 말해, 이것을 줄 것입니다 :
A ------ A ------ A ----
B ------- and B ------ and B ---------
= ---- = ---- = --- --
어느 정도 간단합니다. 그런 다음 가장 낮은 범위에서 시작하여 각 범위 를 반복하고 각 범위에서 그 위의 모든 범위를 차례로 뺍니다. 그리고 거기 있습니다.
다음은 파이썬에서 범위 감산기의 구현입니다.
def subtractRanges((As, Ae), (Bs, Be)):
'''SUBTRACTS A FROM B'''
# e.g, A = ------
# B = -----------
# result = -- ---
# Returns list of new range(s)
if As > Be or Bs > Ae: # All of B visible
return [[Bs, Be]]
result = []
if As > Bs: # Beginning of B visible
result.append([Bs, As])
if Ae < Be: # End of B visible
result.append([Ae, Be])
return result
이 함수를 사용하면 나머지는 다음과 같이 수행 할 수 있습니다. ”범위 ‘는 파이썬 키워드이므로’범위 ‘는 범위를 의미합니다.
spans = [["red", [12.5, 13.8]],
["blue", [0.0, 5.4]],
["green", [2.0, 12.0]],
["yellow", [3.5, 6.7]],
["orange", [6.7, 10.0]]]
i = 0 # Start at lowest span
while i < len(spans):
for superior in spans[i+1:]: # Iterate through all spans above
result = subtractRanges(superior[1], spans[i][1])
if not result: # If span is completely covered
del spans[i] # Remove it from list
i -= 1 # Compensate for list shifting
break # Skip to next span
else: # If there is at least one resulting span
spans[i][1] = result[0]
if len(result) > 1: # If there are two resulting spans
# Insert another span with the same name
spans.insert(i+1, [spans[i][0], result[1]])
i += 1
print spans
이것은 [['red', [12.5, 13.8]], ['blue', [0.0, 2.0]], ['green', [2.0, 3.5]], ['green', [10.0, 12.0]], ['yellow', [3.5, 6.7]], ['orange', [6.7, 10.0]]]
정확합니다.
답변
데이터가 실제로 샘플 데이터와 범위가 비슷한 경우 다음과 같은 맵을 만들 수 있습니다.
map = [0 .. 150]
for each color:
for loc range start * 10 to range finish * 10:
map[loc] = color
그런 다음이지도를 통해 범위를 생성하십시오.
curcolor = none
for loc in map:
if map[loc] != curcolor:
if curcolor:
rangeend = loc / 10
make new range
rangecolor = map[loc]
rangestart = loc / 10
작동하려면 값이 샘플 데이터에서와 같이 상대적으로 작은 범위에 있어야합니다.
편집 : 진정한 수레로 작업하려면 맵을 사용하여 높은 수준의 매핑을 생성 한 다음 원래 데이터를 참조하여 경계를 만듭니다.
map = [0 .. 15]
for each color:
for loc round(range start) to round(range finish):
map[loc] = color
curcolor = none
for loc in map
if map[loc] != curcolor:
make new range
if loc = round(range[map[loc]].start)
rangestart = range[map[loc]].start
else
rangestart = previous rangeend
rangecolor = map[loc]
if curcolor:
if map[loc] == none:
last rangeend = range[map[loc]].end
else
last rangeend = rangestart
curcolor = rangecolor
답변
Scala의 비교적 간단한 솔루션은 다음과 같습니다. 다른 언어로 포팅하기가 너무 어렵지 않아야합니다.
case class Range(name: String, left: Double, right: Double) {
def overlapsLeft(other: Range) =
other.left < left && left < other.right
def overlapsRight(other: Range) =
other.left < right && right < other.right
def overlapsCompletely(other: Range) =
left <= other.left && right >= other.right
def splitLeft(other: Range) =
Range(other.name, other.left, left)
def splitRight(other: Range) =
Range(other.name, right, other.right)
}
def apply(ranges: Set[Range], newRange: Range) = {
val left = ranges.filter(newRange.overlapsLeft)
val right = ranges.filter(newRange.overlapsRight)
val overlaps = ranges.filter(newRange.overlapsCompletely)
val leftSplit = left.map(newRange.splitLeft)
val rightSplit = right.map(newRange.splitRight)
ranges -- left -- right -- overlaps ++ leftSplit ++ rightSplit + newRange
}
val ranges = Vector(
Range("red", 12.5, 13.8),
Range("blue", 0.0, 5.4),
Range("green", 2.0, 12.0),
Range("yellow", 3.5, 6.7),
Range("orange", 6.7, 10.0))
val flattened = ranges.foldLeft(Set.empty[Range])(apply)
val sorted = flattened.toSeq.sortBy(_.left)
sorted foreach println
apply
Set
이미 적용된 모든 범위 중 하나 를 취하고 겹침을 찾은 다음 겹침을 뺀 새 세트와 겹침을 더한 값과 새 범위 및 새로 분할 된 범위를 반환합니다. 각 입력 범위로 foldLeft
반복해서 호출 apply
합니다.
답변
시작으로 정렬 된 범위 세트를 유지하십시오. 모든 것을 포함하는 범위를 추가하십시오 (-oo .. + oo). 범위 r을 추가하려면 :
let pre = last range that starts before r starts
let post = earliest range that starts before r ends
now iterate from pre to post: split ranges that overlap, remove ranges that are covered, then add r