C＃遞歸問題

Question

我有一個Range類，我希望能夠減去一組範圍。

我可以做一個罰款。

例如

Range range1 = new Range(0,100); 
Range range2 = new Range(40,60); 

List<Range> differences = range1.Difference(range2); 

differences[0]; // 0 to 40 
differences[1]; // 60 to 100 

找到一個範圍，一組範圍之間的區別，當我被困在的問題是：

List<Range> rangeSet = new List<Range>(); 
rangeSet.Add(new Range(10, 30); 
rangeSet.Add(new Range(25, 70); 
rangeSet.Add(new Range(90, 120); 

List<Range> results = range1.Difference(rangeSet); 

結果應該是：

results[0]; // 0 to 10 
results[1]; // 70 to 90 

算法應該採取來自範圍和rangeSet [0]之間的差異的結果，然後將該結果用作下一次迭代的輸入等等，並最終返回結果集合的範圍。

我猜這將需要一個遞歸方法，但我不能讓我的頭繞它嗎？

「澄清」。問題比我給出的範圍例子更復雜。這是我試圖通過的測試。

[Test] 
    public void BandCanReturnDifferenceWithASetOfOtherBands() 
    { 
     var bandA = Band.Create<ChargeBand>("Band A"); 
     bandA.AddMonth(EMonth.January); 
     bandA.AddMonth(EMonth.February); 
     bandA.AddDayOfWeek(DayOfWeek.Monday); 
     bandA.AddDayOfWeek(DayOfWeek.Tuesday); 
     bandA.AddTimeRange(5, 0, 11, 0); 

     var bandA2 = Band.Create<ChargeBand>("Band A2"); 
     bandA2.AddMonth(EMonth.January); 
     bandA2.AddMonth(EMonth.December); 
     bandA2.AddDayOfWeek(DayOfWeek.Wednesday); 
     bandA2.AddDayOfWeek(DayOfWeek.Friday); 
     bandA2.AddTimeRange(1, 0, 10, 0); 
     bandA2.AddTimeRange(12, 0, 24, 0); 

     IList<IBand> bands = new List<IBand>(); 
     bands.Add(bandA); 
     bands.Add(bandA2); 

     var bandB = Band.CreateAllTimesBand<ChargeBand>("Band B"); 

     // this should result in 
     var bandR1 = Band.Create<ChargeBand>("R1"); 
     var bandR2 = Band.Create<ChargeBand>("R2"); 
     var bandR3 = Band.Create<ChargeBand>("R3"); 

     bandR1.AddMonth(EMonth.January); 
     bandR1.AddMonth(EMonth.February); 
     bandR1.AddDayOfWeek(DayOfWeek.Monday); 
     bandR1.AddDayOfWeek(DayOfWeek.Tuesday); 
     bandR1.AddTimeRange(0, 0, 5, 0); 
     bandR1.AddTimeRange(11, 0, 24, 0); 

     bandR2.AddMonth(EMonth.January); 
     bandR2.AddMonth(EMonth.December); 
     bandR2.AddDayOfWeek(DayOfWeek.Wednesday); 
     bandR2.AddDayOfWeek(DayOfWeek.Thursday); 
     bandR2.AddTimeRange(0, 0, 1, 0); 
     bandR2.AddTimeRange(10, 0, 12, 0); 

     bandR3.AddMonth(EMonth.March); 
     bandR3.AddMonth(EMonth.April); 
     bandR3.AddMonth(EMonth.May); 
     bandR3.AddMonth(EMonth.June); 
     bandR3.AddMonth(EMonth.July); 
     bandR3.AddMonth(EMonth.August); 
     bandR3.AddMonth(EMonth.September); 
     bandR3.AddMonth(EMonth.October); 
     bandR3.AddMonth(EMonth.November); 
     bandR3.SetAllDays(); 
     bandR3.AddTimeRange(0, 0, 24, 0); 


     //        J,F,M,A,M,J,J,A,S,O,N,D - M,T,W,T,F,S,S - (00:00,24:00) 
     //        J,F      - M,T   - (05:00,11:00)    
     //        J,     D -  W F  - (01:00,10:00),(12:00,24:00) 


     IList<IBand> expectedResults = new List<IBand>(); 
     expectedResults.Add(bandR1); // J,F - M,T    - (00:00,05:00),(11:00,24:00) 
     expectedResults.Add(bandR2); // J,D - W,F    - (00:00,01:00),(10:00,12:00) 
     expectedResults.Add(bandR3); // M,A,M,J,J,A,S,O,N  - (00:00,24:00) 

     var actualResults = bandB.Difference(bands); 

     Assert.AreEqual(expectedResults.Count, actualResults.Count); 

     foreach (var result in actualResults) 
     { 
      Assert.IsTrue(expectedResults.Contains(result)); 
     } 
    } 

對不起，如果我沒有意義，但我很難解釋。

Answer 1

你可以試試這個：

 List<Range> rangeSet = new List<Range>(); 
     rangeSet.Add(new Range(10, 30)); 
     rangeSet.Add(new Range(25, 70)); 
     rangeSet.Add(new Range(90, 120)); 

     List<Range> results = new List<Range>(); 
     Range currentRange = rangeSet.First(); 
     foreach (var x in rangeSet.Skip(1)) 
     { 
      results.Add(x.Difference(currentRange)); 
      currentRange = x; 
     } 

Answer 2

同意，遞歸算法是不必要的。你只需要一些原始集合操作來處理，這可以很容易地完成。其中最難的是減法操作，即從單一範圍中刪除一個或多個範圍。一旦你有了這個，你需要一個可以重新規範範圍的聯盟。

這裏是一個工作示例：

[System.Diagnostics.DebuggerDisplay("Range({Start} - {End})")] 
    public class Range : IEnumerable<int> 
    { 
     public int Start, End; 

     public Range(int start, int end) 
     { 
      Start = start; 
      End = end; 
     } 

     public IEnumerator<int> GetEnumerator() 
     { 
      for (int i = Start; i <= End; i++) 
       yield return i; 
     } 

     System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
     { return GetEnumerator(); } 

     public IEnumerable<Range> Subtract(IEnumerable<int> removed) 
     { 
      IEnumerator<int> add = this.GetEnumerator(); 
      IEnumerator<int> rem = removed.GetEnumerator(); 

      bool hasmore = rem.MoveNext(); 
      while (add.MoveNext()) 
      { 
       int start = add.Current; 
       int end = start; 

       while (hasmore && rem.Current < start) 
        hasmore = rem.MoveNext(); 

       if(!hasmore) 
       { 
        while (add.MoveNext()) 
         end = add.Current; 
        yield return new Range(start, end); 
        yield break; 
       } 

       if(rem.Current == start) 
       { 
        hasmore = rem.MoveNext(); 
        continue; 
       } 

       while (add.MoveNext()) 
       { 
        if (add.Current == rem.Current) 
        { 
         hasmore = rem.MoveNext(); 
         break; 
        } 
        end = add.Current; 
       } 
       if (end >= start) 
        yield return new Range(start, end); 
      } 
     } 
    } 

    public static IEnumerable<int> UnionRanges(this IEnumerable<Range> ranges) 
    { 
     int pos = int.MinValue; 
     foreach(Range r in ranges.OrderBy(x => x.Start)) 
     { 
      pos = Math.Max(pos, r.Start); 
      for (; pos <= r.End; pos++) 
       yield return pos; 
     } 
    } 

    public static IEnumerable<Range> CreateRanges(this IEnumerable<int> values) 
    { 
     Range r = null; 
     foreach (int val in values) 
     { 
      if (r == null) 
       r = new Range(val, val); 
      else if (val == r.End + 1) 
       r.End++; 
      else 
      { 
       yield return r; 
       r = new Range(val, val); 
      } 
     } 
     if (r != null) 
      yield return r; 
    } 

    public static void Main() 
    { 
     Range range1 = new Range(0, 100); 
     Range range2 = new Range(40, 60); 

     IEnumerable<Range> diff1 = range1.Subtract(range2); 

     Console.WriteLine("Subtract 40-60 from 0-100:"); 
     foreach (Range r in diff1) 
      Console.WriteLine("{0} ~ {1}", r.Start, r.End); 

     List<Range> rangeSet = new List<Range>(); 
     rangeSet.Add(new Range(10, 30)); 
     rangeSet.Add(new Range(25, 70)); 
     rangeSet.Add(new Range(90, 120)); 

     Console.WriteLine("Normalized ranges to remove:"); 
     foreach (Range r in rangeSet.UnionRanges().CreateRanges()) 
      Console.WriteLine("{0} ~ {1}", r.Start, r.End); 

     IEnumerable<Range> diff2 = range1.Subtract(rangeSet.UnionRanges()); 

     Console.WriteLine("Results:"); 
     foreach (Range r in diff2) 
      Console.WriteLine("{0} ~ {1}", r.Start, r.End); 
    } 

前述程序產生以下輸出：

Subtract 40-60 from 0-100: 
0 ~ 39 
61 ~ 100 
Normalized ranges to remove: 
10 ~ 70 
90 ~ 120 
Results: 
0 ~ 9 
71 ~ 89 
Press any key to continue . . . 

其餘的主要問題是在你的實施例中的圍欄柱的錯誤。您需要確定範圍是否包含結束，然後進行相應調整。

我會注意到前面的程序並不打算做'生產'準備好......它只是一個如何解決相關問題的例子。更好的實現可以結合並減去範圍，而不必迭代範圍中的項目。這個概念仍然是一樣的，建立集合操作並從那裏開始。

順便說一句，如果你只打算有幾百個項目，我只想用一個HashSet或字典和享受生活;）