Was ist ein guter, generischer Algorithmus eine Reihe von potentiell überlappende Bereiche zum Zusammenlegen?
https://stackoverflow.com/questions/1233292
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe eine Methode, die eine Reihe von Objekten dieser Klasse bekommt
class Range<T>
{
public T Start;
public T End;
}
In meinem Fall T ist DateTime, aber die Verwendung int der Einfachheit halber können. Ich würde eine Methode wie die jene Bereiche in denen kollabiert, die den gleichen „Bereich“ abdecken, aber das nicht überlappen.
Also, wenn ich die folgenden Bereiche hatte
- 1 bis 5
- 3 bis 9
- 11 bis 15
- 12 bis 14
- 13 bis 20
Das Verfahren sollte gib mir
- 1 bis 9
- 11 bis 20
Erraten, es wäre eine Vereinigung genannt werden? Ich stelle mir die Methode Signatur etwas könnte wie folgt aussehen:
public static IEnumerable<Range<T>> Collapse<T>(
this IEnumerable<Range<T>>,
IComparable<T> comparer)
{
...
}
Ich habe schon in einigen anderen Fragen hier sah die Art ähnlich sind, aber ich habe nicht eine Implementierung dieser noch nicht gefunden. Diese Antwort und einige andere Antworten auf die gleiche Frage beschreibt Algorithmen, aber ich bin nicht ganz sicher, ob ich die Algorithmen verstehen. Nicht besonders gut Algorithmen entweder Implementierung, so dass ich hoffte, dass jemand hier könnte mir helfen.
Lösung
Das scheint funktioniert und ist leicht zu verstehen.
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;
}
Hier ist die Veränderung, die ich in den Kommentaren erwähnt. Es ist im Grunde das Gleiche, aber mit einem gewissen Kontrolle und Nachgeben der Ergebnisse statt vor der Rückkehr in einer Liste gesammelt werden.
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);
}
Andere Tipps
Ein Python-Lösung für die nicht-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
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);
}
}
So etwas wie dies. Haben Sie nicht überprüfen, dass es mit allen Eingängen arbeitet.
Die Idee, eine Liste der zusammenbrech schrie nur aus „reduzieren“ für mich. Es hat nicht ganz am Ende so elegant wie ich aber gehofft hatte.
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
dank yairchu für die Daten eingeben, damit ich schneiden und fügen Sie ihn:)
Dies könnte wahrscheinlich optimiert werden ...
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);
}
}
}
Eine Rubin-Version. Sortieren Sie die Bereiche vor merge scheint eine gute Idee zu sein.
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
Tossing einen anderen Hut in den Ring. Sehr viel die gleiche Umsetzung wie Gary Ws (von denen bekam ich den sortierte Liste Ansatz), aber als Testfall gemacht und mit einigen hilfreichen Funktionen der Range-Klasse hinzugefügt.
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);
}
}
}
Hier ist ein einfaches Looping impelmentation, aber zumindest ist klar.
- Es funktioniert für Datetime sowie Int, in meinen einfachen Tests
- Die meisten der Komplexität ist in der Overlap / Combine Methoden auf den Bereich
- Der Algorithmus tatsächlich leicht verständlich ist, kein schwebender Vars
- Fügt eine gewisse Fähigkeit zur Range-Klasse, die im allgemeinen wahrscheinlich nützlich ist
- diese Linie absichtlich sinnlos, beheben Abschlag Problem -
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;
}
}
Algorithmus in Go basierend auf der Python Antwort:
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
}
Dies ist eine leichte Variation. Ich brauche nicht eine ungeordnete Liste zu kollabieren, wollte ich stattdessen eine sortierte Liste halten. Das ist effizienter in meinem Fall. Ich bin Entsendung es hier falls es jemand anderes nützlich ist dieses Thema zu lesen. Offensichtlich kann sehr leicht gemacht generic werden.
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;
}
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
