通過c＃生成器設置最大獨立子集

Question

我想查找給定集合中所有相互排斥並且包含儘可能多的超集元素的子集。當用戶定義了排他性意義：

bool exclusion<T>(T a, T b) 

其中至少exclusion(a, b) == exclusion(b, a)成立。

而且exclusion(a, b) == true如果a.Equals(b) == true

我的代碼看起來是這樣的保證：

public static HashSet<HashSet<T>> MutuallyExclusive<T>(this IEnumerable<T> available, Func<T, T, bool> exclusion) { 
    HashSet<HashSet<T>> finished = new HashSet<HashSet<T>>(new HashSetEquality<T>()); 
    Recursion<T>(available, new HashSet<T>(), finished, exclusion); 
    return finished; 
} 

private static void Recursion<T>(IEnumerable<T> available, HashSet<T> accepted, HashSet<HashSet<T>> finished, Func<T, T, bool> exclusion) { 
    if (!available.Any()) 
     finished.Add(accepted); 
    else 
     foreach (T a in available) 
      Recursion<T>(available.Where(b => !exclusion(a, b)), new HashSet<T>(accepted) { a }, finished, exclusion); 
} 

private class HashSetEquality<T> : IEqualityComparer<HashSet<T>> { 
    public bool Equals(HashSet<T> x, HashSet<T> y) { 
     if (x.Count != y.Count) 
      return false; 
     return x.All(t => y.Contains(t)); 
    } 

    public int GetHashCode(HashSet<T> obj) { 
     return obj.Aggregate(0, (i, t) => i^t.GetHashCode()); 
    } 
} 

有沒有辦法把這個代碼轉換成一個迭代器通過接收到的值逐一移動？

編輯：

看來我是我在我的問題有點unprecise，對不起。我實際上正在尋找一個發生器來執行執行。所以，每次你調用它只剩下一接受的一套計算

Answer 1

基本上，你想要做的是每次調用finished.Add()的時間以產生一組新的並返回true。

但由於遞歸，您還需要產生從遞歸調用返回的所有值。你可以通過產生在一個循環中的所有這些值：

public static IEnumerable<HashSet<T>> MutuallyExclusive<T>(
    this IEnumerable<T> available, Func<T, T, bool> exclusion) 
{ 
    var finished = new HashSet<HashSet<T>>(new HashSetEquality<T>()); 
    return Recursion<T>(available, new HashSet<T>(), finished, exclusion); 
} 

private static IEnumerable<HashSet<T>> Recursion<T>(
    IEnumerable<T> available, HashSet<T> accepted, HashSet<HashSet<T>> finished, 
    Func<T, T, bool> exclusion) 
{ 
    if (!available.Any()) 
    { 
     if (finished.Add(accepted)) 
      yield return finished; 
    } 
    else 
     foreach (T a in available) 
     { 
      var results = Recursion<T>(
       available.Where(b => !exclusion(a, b)), 
       new HashSet<T>(accepted) { a }, finished, exclusion); 

      foreach (var set in results) 
       yield return set; 
     } 
} 

它可能不是最有效的解決方案，但它能夠完成任務。

此外，您可能需要考慮僅查看每個子集一次。這樣，你就不需要finished組，你可以直接得到你找到的所有結果。

Answer 2

而不是return finished;你可以使用

foreach (HashSet<T> set in finished) 
    yield return set; 

而且因爲你正在一臺發電機（我認爲這就是他們叫什麼？）您需要將MutuallyExclusive的簽名從HashSet<HashSet<T>>更改爲IEnumerable<HashSet<T>>。所以基本上MutuallyExclusive會是什麼樣子：

public static IEnumerable<HashSet<T>> MutuallyExclusive<T>(this IEnumerable<T> available, Func<T, T, bool> exclusion) 
{ 
    HashSet<HashSet<T>> finished = new HashSet<HashSet<T>>(new HashSetEquality<T>()); 
    Recursion<T>(available, new HashSet<T>(), finished, exclusion); 
    foreach (HashSet<T> set in finished) 
     yield return set; 
}