잠재적으로 겹치는 범위 세트를 무너 뜨릴 수있는 좋은 일반적인 알고리즘은 무엇입니까?
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 's (정렬 된 목록 접근법을 얻었음)와 동일한 구현이지만 테스트 케이스로 수행되었으며 범위 클래스에 유용한 기능이 추가되었습니다.
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에서 작동합니다.
- 복잡성의 대부분은 범위의 오버랩/결합 방법에 있습니다.
- 알고리즘은 실제로 쉽게 이해할 수 있으며 부동 변형이 없습니다.
- 일반적으로 유용한 범위 클래스에 약간의 능력이 추가됩니다.
-- 마크 다운 문제를 해결하기 위해이 라인은 의도적으로 의미가 없습니다 --
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;
}
}
Python 답변을 기반으로 GO의 알고리즘 :
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
