¿Qué es un buen algoritmo genérico para colapsar un conjunto de rangos potencialmente superpuestos?

Question

Tengo un método que consigue un número de objetos de esta clase

class Range<T> 
{ 
    public T Start; 
    public T End; 
} 

En mi caso es TDateTime, pero permite utilizar int por simplicidad. Me gustaría un método que colapse esos rangos en unos que cubran el mismo "área" pero que no se superpongan.

Así si tuviera las siguientes gamas

• 1 a 5
• 3 a 9
• 11 a 15
• 12 a 14
• 13 a 20

El método debería darme

• 1 a 9
• 11 a 20

supongo que sería llamado un sindicato? Imagino la firma del método podría ser algo como esto:

public static IEnumerable<Range<T>> Collapse<T>(
    this IEnumerable<Range<T>>, 
    IComparable<T> comparer) 
{ 
    ... 
} 

he visto algunas otras preguntas aquí que son un poco similar, pero no he encontrado una implementación de esto todavía. This answer y algunas otras respuestas a la misma pregunta describen algoritmos, pero no estoy seguro si entiendo los algoritmos. No es especialmente bueno para implementar algoritmos tampoco, así que esperaba que alguien aquí pudiera ayudarme.

Answer 1

Esto parece funcionar y es fácil de entender.

public static IEnumerable<Range<T>> Collapse<T>(this IEnumerable<Range<T>> me, IComparer<T> comparer) 
    { 
     List<Range<T>> orderdList = me.OrderBy(r => r.Start).ToList(); 
     List<Range<T>> newList = new List<Range<T>>(); 

     T max = orderdList[0].End; 
     T min = orderdList[0].Start; 

     foreach (var item in orderdList.Skip(1)) 
     { 
      if (comparer.Compare(item.End, max) > 0 && comparer.Compare(item.Start, max) > 0) 
      { 
       newList.Add(new Range<T> { Start = min, End = max }); 
       min = item.Start; 
      } 
      max = comparer.Compare(max, item.End) > 0 ? max : item.End; 
     } 
     newList.Add(new Range<T>{Start=min,End=max}); 

     return newList; 
    } 

---

Aquí es la variación, que he mencionado en los comentarios. Básicamente es lo mismo, pero con cierta comprobación y rendimiento de los resultados en lugar de recopilar en una lista antes de volver.

public static IEnumerable<Range<T>> Collapse<T>(this IEnumerable<Range<T>> ranges, IComparer<T> comparer) 
    { 
     if(ranges == null || !ranges.Any()) 
      yield break; 

     if (comparer == null) 
      comparer = Comparer<T>.Default; 

     var orderdList = ranges.OrderBy(r => r.Start); 
     var firstRange = orderdList.First(); 

     T min = firstRange.Start; 
     T max = firstRange.End; 

     foreach (var current in orderdList.Skip(1)) 
     { 
      if (comparer.Compare(current.End, max) > 0 && comparer.Compare(current.Start, max) > 0) 
      { 
       yield return Create(min, max); 
       min = current.Start; 
      } 
      max = comparer.Compare(max, current.End) > 0 ? max : current.End; 
     } 
     yield return Create(min, max); 
    } 

Answer 2

Esto probablemente se podría optimizar ...

using System.Collections.Generic; 
using System.Linq; 
using System; 
static class Range 
{ 
    public static Range<T> Create<T>(T start, T end) 
    { 
     return new Range<T>(start, end); 
    } 
    public static IEnumerable<Range<T>> Normalize<T>(
     this IEnumerable<Range<T>> ranges) 
    { 
     return Normalize<T>(ranges, null); 
    } 
    public static IEnumerable<Range<T>> Normalize<T>(
     this IEnumerable<Range<T>> ranges, IComparer<T> comparer) 
    { 
     var list = ranges.ToList(); 
     if (comparer == null) comparer = Comparer<T>.Default; 
     for (int i = list.Count - 1; i >= 0; i--) 
     { 
      var item = list[i]; 

      for (int j = 0; j < i; j++) 
      { 
       Range<T>? newValue = TryMerge<T>(comparer, item, list[j]); 

       // did we find a useful transformation? 
       if (newValue != null) 
       { 
        list[j] = newValue.GetValueOrDefault(); 
        list.RemoveAt(i); 
        break; 
       } 
      } 
     } 
     list.Sort((x, y) => 
     { 
      int t = comparer.Compare(x.Start, y.Start); 
      if (t == 0) t = comparer.Compare(x.End, y.End); 
      return t; 
     }); 
     return list.AsEnumerable(); 
    } 

    private static Range<T>? TryMerge<T>(IComparer<T> comparer, Range<T> item, Range<T> other) 
    { 
     if (comparer.Compare(other.End, item.Start) == 0) 
     { // adjacent ranges 
      return new Range<T>(other.Start, item.End); 
     } 
     if (comparer.Compare(item.End, other.Start) == 0) 
     { // adjacent ranges 
      return new Range<T>(item.Start, other.End); 
     } 
     if (comparer.Compare(item.Start, other.Start) <= 0 
      && comparer.Compare(item.End, other.End) >= 0) 
     { // item fully swalls other 
      return item; 
     } 
     if (comparer.Compare(other.Start, item.Start) <= 0 
      && comparer.Compare(other.End, item.End) >= 0) 
     { // other fully swallows item 
      return other; 
     } 
     if (comparer.Compare(item.Start, other.Start) <= 0 
      && comparer.Compare(item.End, other.Start) >= 0 
      && comparer.Compare(item.End, other.End) <= 0) 
     { // partial overlap 
      return new Range<T>(item.Start, other.End); 
     } 
     if (comparer.Compare(other.Start, item.Start) <= 0 
      && comparer.Compare(other.End, item.Start) >= 0 
      && comparer.Compare(other.End, item.End) <= 0) 
     { // partial overlap 
      return new Range<T>(other.Start, item.End); 
     } 
     return null; 
    } 
} 
public struct Range<T> 
{ 
    private readonly T start, end; 
    public T Start { get { return start; } } 
    public T End { get { return end; } } 
    public Range(T start, T end) 
    { 
     this.start = start; 
     this.end = end; 
    } 
    public override string ToString() 
    { 
     return start + " to " + end; 
    } 
} 

static class Program 
{ 
    static void Main() 
    { 
     var data = new[] 
     { 
      Range.Create(1,5), Range.Create(3,9), 
      Range.Create(11,15), Range.Create(12,14), 
      Range.Create(13,20) 
     }; 
     var result = data.Normalize(); 
     foreach (var item in result) 
     { 
      Console.WriteLine(item); 
     } 
    } 
} 

Answer 3

static void Main(string[] args) { 
    List<Range<int>> ranges = new List<Range<int>>() 
    {    
     new Range<int>(3,9), 
     new Range<int>(1,5), 
     new Range<int>(11,15), 
     new Range<int>(12,14), 
     new Range<int>(13,20), 
    }; 

    var orderedRanges = ranges.OrderBy(r => r.Start); 
    var lastRange = new Range<int>(orderedRanges.First().Start, orderedRanges.First().End); 

    List<Range<int>> newranges = new List<Range<int>>();    
    newranges.Add(lastRange); 

    foreach (var range in orderedRanges.Skip(1)) { 
     if (range.Start >= lastRange.Start && range.Start <= lastRange.End && range.End > lastRange.End) { 
      lastRange.End = range.End; 
     } 
     else if (range.Start > lastRange.End) { 
      lastRange = new Range<int>(range.Start, range.End); 
      newranges.Add(lastRange); 
     } 
    } 

    foreach (var r in newranges) { 
     Console.WriteLine("{0}, {1}", r.Start, r.End); 
    } 
} 

Algo como esto. No verifiqué que funciona con todas las entradas.

Answer 4

Una solución de Python para la no verbosephile:

ranges = [ 
    (11, 15), 
    (3, 9), 
    (12, 14), 
    (13, 20), 
    (1, 5)] 

result = [] 
cur = None 
for start, stop in sorted(ranges): # sorts by start 
    if cur is None: 
    cur = (start, stop) 
    continue 
    cStart, cStop = cur 
    if start <= cStop: 
    cur = (cStart, max(stop, cStop)) 
    else: 
    result.append(cur) 
    cur = (start, stop) 
result.append(cur) 

print result 

Answer 5

La idea de colapsar una lista simplemente gritó "reducir" a mí. Sin embargo, no terminó tan elegante como esperaba.

def collapse(output,next_range): 
    last_start,last_end = output[-1] 
    next_start, next_end = next_range 
    if (next_start <= last_end): 
     output[-1] = (last_start, max(next_end, last_end)) 
    else: 
     output.append(next_range) 
    return output 

ranges = [ 
    (11, 15), 
    (3, 9), 
    (12, 14), 
    (13, 20), 
    (1, 5)] 

ranges.sort() 
result = [ranges.pop(0)] 
reduce(collapse, ranges,result) 

print result 

gracias a yairchu para introducir los datos para que pudiera cortar y pegar :)

Answer 6

Aquí es un simple bucle impelmentation, pero al menos está claro.

• Funciona para DateTime, así como Int, en mis pruebas simples
• La mayor parte de la complejidad está en el solapamiento/Combinar métodos en la gama
• El algoritmo es realmente fácil de entender, sin flotando vars
• añade un poco de habilidad de la clase Range que es probablemente útil en general

- esta línea intencionadamente sin sentido, para corregir un problema de reducción del precio -

public static class CollapseRange 
{ 
    public static IEnumerable<Range<T>> Collapse<T>(this IEnumerable<Range<T>> me) 
     where T:struct 
    { 
     var result = new List<Range<T>>(); 
     var sorted = me.OrderBy(x => x.Start).ToList(); 
     do { 
      var first = sorted.FirstOrDefault(); 
      sorted.Remove(first); 
      while (sorted.Any(x => x.Overlap(first))) { 
       var other = sorted.FirstOrDefault(x => x.Overlap(first)); 
       first = first.Combine(other); 
       sorted.Remove(other); 
      } 
      result.Add(first); 
     } while (sorted.Count > 0); 
     return result; 
    } 
} 

[DebuggerDisplay("Range {Start} - {End}")] 
public class Range<T> where T : struct 
{ 
    public T Start { set; get; } 
    public T End { set; get; } 
    public bool Overlap(Range<T> other) 
    { 
     return (Within(other.Start) || Within(other.End) || other.Within(this.Start) || other.Within(this.End)); 
    } 
    public bool Within(T point) 
    { 
     var Comp = Comparer<T>.Default; 
     var st = Comp.Compare(point, this.Start); 
     var ed = Comp.Compare(this.End, point); 
     return (st >= 0 && ed >= 0); 
    } 
    /// <summary>Combines to ranges, updating the current range</summary> 
    public void Merge(Range<T> other) 
    { 
     var Comp = Comparer<T>.Default; 
     if (Comp.Compare(this.Start, other.Start) > 0) this.Start = other.Start; 
     if (Comp.Compare(other.End, this.End) > 0) this.End = other.End; 
    } 
    /// <summary>Combines to ranges, returning a new range in their place</summary> 
    public Range<T> Combine(Range<T> other) 
    { 
     var Comp = Comparer<T>.Default; 
     var newRange = new Range<T>() { Start = this.Start, End = this.End }; 
     newRange.Start = (Comp.Compare(this.Start, other.Start) > 0) ? other.Start : this.Start; 
     newRange.End = (Comp.Compare(other.End, this.End) > 0) ? other.End : this.End; 
     return newRange; 
    } 
} 

Answer 7

Lanzando otro sombrero en el ring. Casi la misma implementación que la de Gary W (de la que obtuve el enfoque de la lista ordenada), pero hecha como un caso de prueba y con algunas funciones útiles añadidas a la clase Range.

import java.util.ArrayList; 
import java.util.HashSet; 
import java.util.Set; 

import edu.emory.mathcs.backport.java.util.Collections; 

import junit.framework.TestCase; 

public class Range2Test extends TestCase { 
    public void testCollapse() throws Exception { 
     Set<Range<Integer>> set = new HashSet<Range<Integer>>(); 
     set.add(new Range<Integer>(1, 5)); 
     set.add(new Range<Integer>(3, 9)); 
     set.add(new Range<Integer>(11, 15)); 
     set.add(new Range<Integer>(12, 14)); 
     set.add(new Range<Integer>(13, 20)); 
     Set<Range<Integer>> expected = new HashSet<Range<Integer>>(); 
     expected.add(new Range<Integer>(1, 9)); 
     expected.add(new Range<Integer>(11, 20)); 
     assertEquals(expected, collapse(set)); 
    } 

    private static <T extends Comparable<T>> Set<Range<T>> collapse(Set<Range<T>> ranges) { 
     if (ranges == null) 
      return null; 
     if (ranges.size() < 2) 
      return new HashSet<Range<T>>(ranges); 
     ArrayList<Range<T>> list = new ArrayList<Range<T>>(ranges); 
     Collections.sort(list); 
     Set<Range<T>> result = new HashSet<Range<T>>(); 
     Range<T> r = list.get(0); 
     for (Range<T> range : list) 
      if (r.overlaps(range)) { 
       r = r.union(range); 
      } else { 
       result.add(r); 
       r = range; 
      } 
     result.add(r); 
     return result; 
    } 

    private static class Range<T extends Comparable<T>> implements Comparable<Range<T>> { 
     public Range(T start, T end) { 
      if (start == null || end == null) 
       throw new NullPointerException("Range requires start and end."); 
      this.start = start; 
      this.end = end; 
     } 
     public T start; 
     public T end; 

     private boolean contains(T t) { 
      return start.compareTo(t) <= 0 && t.compareTo(end) <= 0; 
     } 

     public boolean overlaps(Range<T> that) { 
      return this.contains(that.start) || that.contains(this.start); 
     } 

     public Range<T> union(Range<T> that) { 
      T start = this.start.compareTo(that.start) < 0 ? this.start : that.start; 
      T end = this.end.compareTo(that.end) > 0 ? this.end : that.end; 
      return new Range<T>(start, end); 
     } 

     public String toString() { 
      return String.format("%s - %s", start, end); 
     } 

     public int hashCode() { 
      final int prime = 31; 
      int result = 1; 
      result = prime * result + end.hashCode(); 
      result = prime * result + start.hashCode(); 
      return result; 
     } 

     @SuppressWarnings("unchecked") 
     public boolean equals(Object obj) { 
     if (this == obj)     return true; 
     if (obj == null)     return false; 
     if (getClass() != obj.getClass()) return false; 
     Range<T> that = (Range<T>) obj; 
     return end.equals(that.end) && start.equals(that.start); 
     } 

     public int compareTo(Range<T> that) { 
      int result = this.start.compareTo(that.start); 
      if (result != 0) 
       return result; 
      return this.end.compareTo(that.end); 
     } 
    } 
} 

Answer 8

Una versión ruby. Ordenar los rangos antes de la fusión parece ser una buena idea.

def merge a , b 
    return b if a.nil? 
    if b.begin <= a.end 
     (a.begin..b.end) 
    el 
     [a , b ]  #no overlap 
    end 
end 

ranges = [(1..5),(11..15),(3..9),(12..14),(13..20)] 
sorted_ranges = ranges.sort_by {|r| r.begin} #sorted by the start of the range 

merged_ranges = sorted_ranges.inject([]) do |m , r| 
     last = m.pop 
     m << merge(last , r) 
     m.flatten 
end 

puts merged_ranges 

Answer 9

Algoritmo Ir basado en la respuesta de Python:

package main 

import "sort" 
import "fmt" 

type TupleList [][]int 

// Methods required by sort.Interface. 
func (s TupleList) Len() int { 
    return len(s) 
} 
func (s TupleList) Less(i, j int) bool { 
    return s[i][1] < s[j][1] 
} 
func (s TupleList) Swap(i, j int) { 
    s[i], s[j] = s[j], s[i] 
} 

func main() { 

    ranges := 
     TupleList{ 
      {11, 15}, 
      {3, 9}, 
      {12, 14}, 
      {13, 20}, 
      {1, 5}} 

    fmt.Print(ranges) 
    sort.Sort(ranges) 
    fmt.Print("\n") 
    fmt.Print(ranges) 
    fmt.Print("\n") 
    result := TupleList{} 

    var cur []int 
    for _, t := range ranges { 
     if cur == nil { 
      cur = t 
      continue 
     } 
     cStart, cStop := cur[0], cur[1] 
     if t[0] <= cStop { 
      cur = []int{cStart, max(t[1], cStop)} 
     } else { 
      result = append(result, cur) 
      cur = t 
     } 
    } 
    result = append(result, cur) 
    fmt.Print(result) 
} 

func max(v1, v2 int) int { 
    if v1 <= v2 { 
     return v2 
    } 
    return v1 
} 

Answer 10

Esta es una ligera variación. No necesité colapsar una lista desordenada, quería mantener una lista ordenada en su lugar. Esto es más eficiente en mi caso. Lo estoy publicando aquí en caso de que sea útil para cualquier otra persona que lea este hilo. Obviamente se puede hacer genérico con mucha facilidad.

 private static List<Tuple<int, int>> Insert(List<Tuple<int, int>> ranges, int startIndex, int endIndex) 
     { 
      if (ranges == null || ranges.Count == 0) 
       return new List<Tuple<int, int>> { new Tuple<int, int>(startIndex, endIndex) }; 

      var newIndex = ranges.Count; 
      for (var i = 0; i < ranges.Count; i++) 
      { 
       if (ranges[i].Item1 > startIndex) 
       { 
        newIndex = i; 
        break; 
       } 
      } 

      var min = ranges[0].Item1; 
      var max = ranges[0].Item2; 

      var newRanges = new List<Tuple<int, int>>(); 
      for (var i = 0; i <= ranges.Count; i++) 
      { 
       int rangeStart; 
       int rangeEnd; 
       if (i == newIndex) 
       { 
        rangeStart = startIndex; 
        rangeEnd = endIndex; 
       } 
       else 
       { 
        var range = ranges[i > newIndex ? i - 1 : i]; 
        rangeStart = range.Item1; 
        rangeEnd = range.Item2; 
       } 

       if (rangeStart > max && rangeEnd > max) 
       { 
        newRanges.Add(new Tuple<int, int>(min, max)); 
        min = rangeStart; 
       } 
       max = rangeEnd > max ? rangeEnd : max; 
      } 
      newRanges.Add(new Tuple<int, int>(min, max)); 

      return newRanges; 
     }