ما هي الخوارزمية العامة الجيدة لطي مجموعة من النطاقات المتداخلة المحتملة؟
https://stackoverflow.com/questions/1233292
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لدي طريقة تحصل على عدد من الكائنات من هذه الفئة
class Range<T>
{
public T Start;
public T End;
}
في حالتي T يكون DateTime, ، ولكن دعونا نستخدم int للبساطة.أرغب في طريقة تدمج هذه النطاقات في نطاقات تغطي نفس "المنطقة" ولكنها لا تتداخل.
لذلك إذا كان لدي النطاقات التالية
- 1 إلى 5
- 3 إلى 9
- 11 إلى 15
- 12 إلى 14
- 13 إلى 20
يجب أن تعطيني الطريقة
- 1 إلى 9
- 11 إلى 20
أعتقد أنه سيسمى الاتحاد؟أتخيل أن توقيع الطريقة يمكن أن يبدو كالتالي:
public static IEnumerable<Range<T>> Collapse<T>(
this IEnumerable<Range<T>>,
IComparable<T> comparer)
{
...
}
لقد ألقيت نظرة على بعض الأسئلة الأخرى المشابهة نوعًا ما هنا، لكنني لم أجد تنفيذًا لذلك بعد. هذه الإجابة وبعض الإجابات الأخرى على نفس السؤال تصف الخوارزميات، لكنني لست متأكدًا تمامًا مما إذا كنت أفهم الخوارزميات.لست جيدًا بشكل خاص في تنفيذ الخوارزميات أيضًا، لذلك كنت آمل أن يتمكن شخص ما هنا من مساعدتي.
المحلول
يبدو أن هذا يعمل وسهل الفهم.
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;
}
هنا هو الاختلاف الذي ذكرته في التعليقات.إنه نفس الشيء بشكل أساسي، ولكن مع بعض التدقيق وإخراج النتائج بدلاً من تجميعها في قائمة قبل العودة.
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);
}
نصائح أخرى
حل بايثون لغير محبي الكلام:
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);
}
}
شيء من هذا القبيل.لم أتحقق من أنه يعمل مع جميع المدخلات.
لقد صرخت في ذهني فكرة طي القائمة "تقليل".لم ينتهي الأمر بالأناقة كما كنت أتمنى.
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
شكرًا لـ yairchu على كتابة البيانات حتى أتمكن من قصها ولصقها :)
ربما يمكن تحسين هذا ...
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);
}
}
}
نسخة روبي.يبدو أن فرز النطاقات قبل الدمج فكرة جيدة.
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
رمي قبعة أخرى في الحلبة.يشبه إلى حد كبير تطبيق Gary W (الذي حصلت منه على نهج القائمة المصنفة)، ولكن تم إجراؤه كحالة اختبار مع إضافة بعض الوظائف المفيدة إلى فئة 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);
}
}
}
فيما يلي تنفيذ بسيط للحلقات، لكنه واضح على الأقل.
- إنه يعمل مع DateTime بالإضافة إلى Int، في اختباراتي البسيطة
- معظم التعقيد موجود في أساليب التداخل/الدمج في النطاق
- الخوارزمية في الواقع سهلة الفهم، ولا توجد vars عائمة
- يضيف بعض القدرة إلى فئة Range والتي ربما تكون مفيدة بشكل عام
-- هذا السطر لا معنى له عمدا، لإصلاح مشكلة تخفيض السعر --
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;
}
}
الخوارزمية في Go بناءً على إجابة 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
}
هذا هو الاختلاف الطفيف.لم أكن بحاجة إلى طي قائمة غير مرتبة، بل أردت الاحتفاظ بقائمة مرتبة بدلاً من ذلك.وهذا أكثر كفاءة في حالتي.أنا أنشره هنا في حالة أنه مفيد لأي شخص آخر يقرأ هذا الموضوع.ومن الواضح أنه يمكن جعلها عامة بسهولة بالغة.
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;
}
لا تنتمي إلى StackOverflow
