Algoritmo para aplanar rangos superpuestos

15

Estoy buscando una buena forma de aplanar (dividir) una lista de rangos numéricos potencialmente superpuestos. El problema es muy similar al de esta pregunta: La forma más rápida de dividir intervalos de fechas superpuestas y muchos otros.

Sin embargo, los rangos no son solo enteros, y estoy buscando un algoritmo decente que pueda implementarse fácilmente en Javascript o Python, etc.

Datos de ejemplo:

Ejemplodesolución:

Le pido disculpas si es un duplicado, pero todavía tengo que encontrar una solución.

    
pregunta Jollywatt 29.05.2014 - 04:25
fuente

5 respuestas

9

Camina de izquierda a derecha, usando una pila para realizar un seguimiento del color en el que estás. En lugar de un mapa discreto, use los 10 números de su conjunto de datos como puntos de ruptura.

Comenzando con una pila vacía, y estableciendo start en 0, repite hasta que lleguemos al final:

  • Si la pila está vacía:
    • Busque el primer color que empiece en start o antes, e insértelo en la pila con todos los colores de rango inferior. En tu lista aplanada, marca el comienzo de ese color.
  • else (Si no está vacío):
    • Encuentre el siguiente punto de inicio para cualquier color de mayor rango en o después de start , y encuentre el final del color actual
      • Si el siguiente color comienza primero, empújalo y cualquier otra cosa en el camino hacia la pila. Actualice el final del color actual como el comienzo de este y agregue el inicio de este color a la lista plana.
      • Si no hay ninguno y el color actual termina primero, establezca start al final de este color, sáquelo de la pila y verifique el siguiente color de clasificación más alta
        • Si start está dentro del rango del siguiente color, agregue este color a la lista aplanada, comenzando en start .
        • Si la pila se vacía, simplemente continúe con el bucle (regrese al primer punto).

Este es un recorrido mental dados sus datos de ejemplo:

# 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.
    
respondido por el Izkata 29.05.2014 - 06:34
fuente
3

Esta solución parece la más simple. (O al menos, lo más fácil de entender)

Todo lo que se necesita es una función para restar dos rangos. En otras palabras, algo que dará esto:

A ------               A     ------           A    ----
B    -------    and    B ------        and    B ---------
=       ----           = ----                 = ---    --

Que es lo suficientemente simple. Luego, simplemente puede iterar a través de cada uno de los rangos, comenzando desde el más bajo, y para cada uno, restar de él todos los rangos por encima, a su vez. Y ahí está.

Aquí hay una implementación del restador de rango en Python:

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

Usando esta función, el resto se puede hacer así: (Un 'intervalo' significa un rango, ya que 'rango' es una palabra clave de Python)

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

Esto da [['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]]] , que es correcto.

    
respondido por el Jollywatt 29.05.2014 - 07:41
fuente
2

Si los datos realmente tienen un alcance similar al de los datos de muestra, podría crear un mapa como este:

map = [0 .. 150]

for each color:
    for loc range start * 10 to range finish * 10:
        map[loc] = color

Luego, recorra este mapa para generar los rangos

curcolor = none
for loc in map:
    if map[loc] != curcolor:
        if curcolor:
            rangeend = loc / 10
        make new range
        rangecolor = map[loc]
        rangestart = loc / 10

Para funcionar, los valores deben estar en un rango relativamente pequeño como en los datos de muestra.

Editar: para trabajar con flotadores verdaderos, usa el mapa para generar un mapeo de alto nivel y luego consulta los datos originales para crear los límites.

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
    
respondido por el Steven Burnap 29.05.2014 - 04:39
fuente
2

Aquí hay una solución relativamente sencilla en Scala. No debería ser demasiado difícil trasladar a otro idioma.

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 toma un Set de todos los rangos que ya se han aplicado, encuentra las superposiciones, luego devuelve un nuevo conjunto menos las superposiciones y más el nuevo rango y los nuevos rangos divididos. foldLeft llama repetidamente a apply con cada rango de entrada.

    
respondido por el Karl Bielefeldt 29.05.2014 - 19:52
fuente
0

Simplemente mantenga un conjunto de rangos ordenados por inicio. Añadir rango que cubre todo (-oo .. + oo). Para agregar un rango 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
    
respondido por el kevin cline 29.05.2014 - 06:59
fuente

Lea otras preguntas en las etiquetas