排序可枚举

Question

鉴于相同类型的Ñ可枚举该升序顺序返回不同的元件，例如N路相交：

IEnumerable<char> sx = Intersect(new[] { s1, s2, s3 }); 

Debug.Assert(sx.SequenceEqual("djs")); 

“高效” 在这里是指

1. 输入枚举应该只被枚举一次，
2. 输入枚举元素应该只在需要时才能被检索，而
3. 该算法不应该递归枚举自己的输出。

我需要一些提示如何解决问题。

---

这是我的（幼稚）尝试到目前为止：

static IEnumerable<T> Intersect<T>(IEnumerable<T>[] enums) 
{ 
    return enums[0].Intersect(
     enums.Length == 2 ? enums[1] : Intersect(enums.Skip(1).ToArray())); 
} 

Enumerable.Intersect收集第一枚举成一个HashSet，然后枚举第二枚举并产生所有匹配元素。 Intersect然后递归地将结果与下一个可枚举值相交。 这显然不是很有效率（它不符合约束条件）。而且它并没有利用这些元素完全排序的事实。

---

这是我试图交叉两个枚举。也许它可以推广为n enumerables？

static IEnumerable<T> Intersect<T>(IEnumerable<T> first, IEnumerable<T> second) 
{ 
    using (var left = first.GetEnumerator()) 
    using (var right = second.GetEnumerator()) 
    { 
     var leftHasNext = left.MoveNext(); 
     var rightHasNext = right.MoveNext(); 

     var comparer = Comparer<T>.Default; 

     while (leftHasNext && rightHasNext) 
     { 
      switch (Math.Sign(comparer.Compare(left.Current, right.Current))) 
      { 
      case -1: 
       leftHasNext = left.MoveNext(); 
       break; 
      case 0: 
       yield return left.Current; 
       leftHasNext = left.MoveNext(); 
       rightHasNext = right.MoveNext(); 
       break; 
      case 1: 
       rightHasNext = right.MoveNext(); 
       break; 
      } 
     } 
    } 
} 

Answer 1

OK;更复杂的答案：

public static IEnumerable<T> Intersect<T>(params IEnumerable<T>[] enums) { 
    return Intersect<T>(null, enums); 
} 
public static IEnumerable<T> Intersect<T>(IComparer<T> comparer, params IEnumerable<T>[] enums) { 
    if(enums == null) throw new ArgumentNullException("enums"); 
    if(enums.Length == 0) return Enumerable.Empty<T>(); 
    if(enums.Length == 1) return enums[0]; 
    if(comparer == null) comparer = Comparer<T>.Default; 
    return IntersectImpl(comparer, enums); 
} 
public static IEnumerable<T> IntersectImpl<T>(IComparer<T> comparer, IEnumerable<T>[] enums) { 
    IEnumerator<T>[] iters = new IEnumerator<T>[enums.Length]; 
    try { 
     // create iterators and move as far as the first item 
     for (int i = 0; i < enums.Length; i++) { 
      if(!(iters[i] = enums[i].GetEnumerator()).MoveNext()) { 
       yield break; // no data for one of the iterators 
      } 
     } 
     bool first = true; 
     T lastValue = default(T); 
     do { // get the next item from the first sequence 
      T value = iters[0].Current; 
      if (!first && comparer.Compare(value, lastValue) == 0) continue; // dup in first source 
      bool allTrue = true; 
      for (int i = 1; i < iters.Length; i++) { 
       var iter = iters[i]; 
       // if any sequence isn't there yet, progress it; if any sequence 
       // ends, we're all done 
       while (comparer.Compare(iter.Current, value) < 0) { 
        if (!iter.MoveNext()) goto alldone; // nasty, but 
       } 
       // if any sequence is now **past** value, then short-circuit 
       if (comparer.Compare(iter.Current, value) > 0) { 
        allTrue = false; 
        break; 
       } 
      } 
      // so all sequences have this value 
      if (allTrue) yield return value; 
      first = false; 
      lastValue = value; 
     } while (iters[0].MoveNext()); 
    alldone: 
     ; 
    } finally { // clean up all iterators 
     for (int i = 0; i < iters.Length; i++) { 
      if (iters[i] != null) { 
       try { iters[i].Dispose(); } 
       catch { } 
      } 
     } 
    } 
} 

Answer 2

你可以使用LINQ：

public static IEnumerable<T> Intersect<T>(IEnumerable<IEnumerable<T>> enums) { 
     using (var iter = enums.GetEnumerator()) { 
      IEnumerable<T> result; 
      if (iter.MoveNext()) { 
       result = iter.Current; 
       while (iter.MoveNext()) { 
        result = result.Intersect(iter.Current); 
       } 
      } else { 
       result = Enumerable.Empty<T>(); 
      } 
      return result; 
     } 
    } 

这将是简单，虽然它构建hash组多重倍;一次推进所有n（以利用排序）将很难，但是你也可以构建一个单一的哈希集并删除丢失的东西？