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 permet de l'utiliser int pour des raisons de simplicité. Je voudrais une méthode qui s'effondre plages dans celles qui couvrent la même "zone", mais qui ne se chevauchent pas.

Donc, si j'avais les plages suivantes

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

La méthode devrait me donner

• 1 à 9
• De 11 à 20

Suppose qu'il serait appelé à un syndicat? J'imagine que la signature de la méthode pourrait ressembler à quelque chose comme ceci:

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

J'ai regardé quelques autres questions qui sont de nature similaire, mais je n'ai pas trouvé de mise en œuvre de cette encore. Cette réponse et quelques autres réponses à la même question décrit les algorithmes, mais je ne suis pas sûr si je comprends les algorithmes. Pas très bon à la mise en œuvre des algorithmes, donc j'espérais 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 variation 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 rassembler une liste avant de revenir.

     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

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 5

L'idée de réduire une liste vient de crier "réduire" pour moi. Cela ne s'est pas avéré aussi élégant que je l'avais espéré.

 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 pour pouvoir les copier / coller :)