Qu'est-ce qu'un bon algorithme générique pour réduire un ensemble de plages potentiellement chevauchantes?

Question

J'ai une méthode qui obtient un certain nombre d'objets de cette classe

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

Dans mon cas, T est DateTime , mais utilisons int pour des raisons de simplicité. Je voudrais une méthode qui réduit ces plages dans celles qui couvrent la même "zone" mais cela ne se chevauche pas.

Donc si j'avais les gammes suivantes

• 1 à 5
• 3 à 9
• du 11 au 15
• 12 à 14
• du 13 au 20

La méthode devrait me donner

• 1 à 9
• du 11 au 20

Je suppose que ça s'appellerait un syndicat? J'imagine que la signature de la méthode pourrait ressembler à ceci:

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

J'ai examiné d'autres questions similaires, mais je n'ai pas encore trouvé de mise en œuvre. Cette réponse et quelques autres réponses à la même question décrivent des algorithmes, mais je ne suis pas tout à fait sûr de bien comprendre ces algorithmes. Pas particulièrement doué pour implémenter des algorithmes, j'espérais donc que quelqu'un ici pourrait m'aider.

Answer 1

Cela semble fonctionner et est facile à comprendre.

    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;
    }

Voici la variante que j'ai mentionnée dans les commentaires. C'est fondamentalement la même chose, mais avec quelques vérifications et résultats des résultats au lieu de les rassembler dans une liste avant de les renvoyer.

    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

Une solution Python pour le non-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 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);
    }
}

Quelque chose comme ça. N'a pas vérifié que cela fonctionne avec toutes les entrées.

Answer 4

L’idée de réduire une liste vient de crier "Réduire". pour moi. Il n’a pas été aussi élégant que je l’espérais.

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

merci à yairchu pour avoir tapé les données afin que je puisse les couper et les coller:)

Answer 5

Cela pourrait probablement être optimisé ...

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 6

Une version rubis. Trier les plages avant la fusion semble être une bonne idée.

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 7

Jeter un autre chapeau dans le ring. Quasiment la même implémentation que Gary W (d’où j’ai eu l’approche de la liste triée), mais en tant que scénario de test et avec quelques fonctions utiles ajoutées à la classe 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

Voici une simple impelmentation en boucle, mais au moins elle est claire.

• Cela fonctionne pour DateTime ainsi que pour Int, dans mes tests simples
• La plus grande partie de la complexité réside dans les méthodes de superposition / combinaison sur la plage
• L'algorithme est facilement compréhensible, pas de vars flottants
• Ajoute une capacité à la classe Range qui est probablement utile en général

- cette ligne n'a aucun sens intentionnellement, pour résoudre le problème de démarquage -

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 9

Algorithme dans Go basé sur la réponse 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

Ceci est une légère variation. Je n'avais pas besoin de réduire une liste non ordonnée, je voulais plutôt conserver une liste triée. C'est plus efficace dans mon cas. Je le poste ici au cas où il serait utile à quiconque de lire ce fil. Évidemment, on peut très facilement créer un générique.

        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;
        }