列表的唯一組合

Question

絕對的頭腦在這個空白。這是那些日子之一。但是我一直在尋找一種解決方案來獲得一定長度的項目列表的獨特組合。例如給出一個列表[a，b，c]和長度爲2，它將返回[a，b] [a，c] [b，c]但不是[b，a] [c，a] [c ，b]

爲此，我找到了大量的代碼，但沒有一個似乎適合。下面的代碼似乎是最合適的，我一直在試圖改變它爲我的需求：

// Returns an enumeration of enumerators, one for each permutation 
// of the input. 
public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> list, int count) 
{ 
    if (count == 0) 
    { 
     yield return new T[0]; 
    } 
    else 
    { 
     int startingElementIndex = 0; 
     foreach (T startingElement in list) 
     { 
      IEnumerable<T> remainingItems = AllExcept(list, startingElementIndex); 

      foreach (IEnumerable<T> permutationOfRemainder in Permute(remainingItems, count - 1)) 
      { 
       yield return Concat<T>(
        new T[] { startingElement }, 
        permutationOfRemainder); 
      } 
      startingElementIndex += 1; 
     } 
    } 
} 

// Enumerates over contents of both lists. 
public static IEnumerable<T> Concat<T>(IEnumerable<T> a, IEnumerable<T> b) 
{ 
    foreach (T item in a) { yield return item; } 
    foreach (T item in b) { yield return item; } 
} 

// Enumerates over all items in the input, skipping over the item 
// with the specified offset. 
public static IEnumerable<T> AllExcept<T>(IEnumerable<T> input, int indexToSkip) 
{ 
    int index = 0; 
    foreach (T item in input) 
    { 
     if (index != indexToSkip) yield return item; 
     index += 1; 
    } 
} 

該做的事情是應該做的，但它返回所有排列，無論他們是唯一的。我試圖讓我的腦袋圍繞這段代碼的哪一部分（如果有的話）進行更改以獲取唯一值。或者是實現此功能的更好方法？

Answer 1

實現中的其餘項目列表包含除當前起始項目以外的所有項目。

獲取屬於啓動項，而不是後事項：

IEnumerable<T> remainingItems = list.Skip(startingElementIndex + 1); 

Answer 2

而不是AllExcept，你應該使用一個Subsequence，只給你正在考慮的項目之後的項目。

Answer 3

試試這個：

void Main() 
{ 
    var list = new List<string> { "a", "b", "c", "d", "e" }; 
    var result = GetPermutations(list, 3); 
} 

IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items, int count) 
{ 
    int i = 0; 
    foreach(var item in items) 
    { 
     if(count == 1) 
      yield return new T[] { item }; 
     else 
     { 
      foreach(var result in GetPermutations(items.Skip(i + 1), count - 1)) 
       yield return new T[] { item }.Concat(result); 
     } 

     ++i; 
    } 
} 

對於計數2它返回：

a, b 
a, c 
a, d 
a, e 
b, c 
b, d 
b, e 
c, d 
c, e 
d, e 

對於計數3它返回這個：

a, b, c 
a, b, d 
a, b, e 
a, c, d 
a, c, e 
a, d, e 
b, c, d 
b, c, e 
b, d, e 
c, d, e 

這是你所期望的嗎？

Answer 4

在set-speak中，您要查找的是基於長度n的功率集的子集。如果你做了一個谷歌搜索「C＃」+「Power set」，這應該可以讓你有足夠的起步。

http://en.wikipedia.org/wiki/Power_set

Answer 5

和公正的完整性..如果你已經有了所有排列 （:)因爲它只是一個複製和粘貼對我來說） 下面你extensionmethods可以得到不同的結果是這樣的：

var result = permutations.Distinct((p1, p2) => !p1.Differs(p2)); 

只是舉個例子，如果你有比較列出了很多工作的其他方法可以派上用場，其他地方也

public static class Extensionmethods 
{ 
    /// <summary> 
    /// Checks if both IEnumerables contain the same values regardless of their sequence 
    /// </summary> 
    /// <typeparam name="T">Type of Elements</typeparam> 
    /// <param name="result">IEnumerable to compare to</param> 
    /// <param name="compare">IEnumerable to compare to</param> 
    /// <returns>Returns false if both IEnumerables contain the same values</returns> 
    public static bool Differs<T>(this IEnumerable<T> result, IEnumerable<T> compare) 
    { 
     if (result == null && compare == null) 
      return false; 
     if (result != null && compare == null) 
      return true; 
     if (result == null && compare != null) 
      return true; 
     return result.Count() != compare.Count() 
      || compare.Where(c => c == null).Count() != result.Where(r => r == null).Count() 
      || compare.Where(c => c != null).Distinct().Any(item => result.Where(r => item.Equals(r)).Count() != compare.Where(r => item.Equals(r)).Count()); 
    } 
    /// <summary> 
    /// Checks if both IEnumerables contain the same values (corresponding to <paramref name="comparer"/> regardless of their sequence 
    /// </summary> 
    /// <typeparam name="T">Type of Elements</typeparam> 
    /// <param name="result">IEnumerable to compare to</param> 
    /// <param name="compare">IEnumerable to compare to</param> 
    /// <param name="comparer">IEqualityComparer to use</param> 
    /// <returns>Returns false if both IEnumerables contain the same values</returns> 
    public static bool Differs<T>(this IEnumerable<T> result, IEnumerable<T> compare, IEqualityComparer<T> comparer) 
    { 
     if (result == null && compare == null) 
      return false; 
     if (result != null && compare == null) 
      return true; 
     if (result == null && compare != null) 
      return true; 
     return result.Count() != compare.Count() 
      || compare.Where(c => c == null).Count() != result.Where(r => r == null).Count() 
      || compare.Where(c => c != null).Distinct().Any(item => result.Where(r => comparer.Equals(item, r)).Count() != compare.Where(r => comparer.Equals(item, r)).Count()); 
    } 

    public static IEnumerable<T> Distinct<T>(this IEnumerable<T> source, Func<T, T, bool> compareFunction, Func<T, int> hashFunction = null) 
    { 
     var ecomparer = new DynamicEqualityComparer<T>(compareFunction, hashFunction); 
     return source.Distinct(ecomparer); 
    } 


} 

internal class DynamicEqualityComparer<T> : IEqualityComparer<T> 
{ 

    public DynamicEqualityComparer(Func<T, T, bool> equalFunction, Func<T, int> hashFunction = null) 
    { 
     this.equalFunc = equalFunction; 
     this.hashFunc = hashFunction; 
    } 

    private Func<T, T, bool> equalFunc; 
    public bool Equals(T x, T y) 
    { 
     if (x == null && y == null) return true; 
     if (x == null) return false; 
     if (y == null) return false; 
     if (hashFunc != null) 
     { 
      if (hashFunc.Invoke(x) != hashFunc.Invoke(y)) return false; 
     } 
     return this.equalFunc.Invoke(x, y); 
    } 

    private Func<T, int> hashFunc; 
    public int GetHashCode(T obj) 
    { 
     if (hashFunc != null) return hashFunc.Invoke(obj); 
     return 0; 
    } 
}