提高以下組合算法的性能

Question

我正在使用以下代碼來獲取輸入對象列表的所有組合，同時限制組合的大小（maxComboCount）。雖然代碼雖然提出了問題，但速度很慢。有人可以請看一看，並建議可以幫助演出的任何變化。

例如， 輸入：

List<int> input = new List<int>() {obj1, obj2, obj3}; 
int maxComboCount = 2; 

輸出：

[OBJ1]，[OBJ2]，[OBJ3]，

[OBJ1，OBJ1]，[OBJ1，OBJ2]，[OBJ1 ，OBJ3]，

[OBJ2，OBJ1]，[OBJ2，OBJ2]，[OBJ2，OBJ3]，

[OBJ3，OBJ1]，[OBJ3，OBJ2]，[OBJ3，OB J3]

public static IEnumerable<List<T>> GetCombo<T>(List<T> listObject, int maxComboCount) 
{ 
    var resultList = new List<List<T>>(); 
    var distinctObjects = listObject.Distinct().ToList(); 

    for (int j = 0; j < distinctObjects.Count(); j++) 
    { 
     var objPosition = distinctObjects[j]; 

     var newList = new List<T>(); 
     newList.Add(objPosition); 

     if (newList.Count() <= maxComboCount) 
     { 
      resultList.Add(newList); 
     } 

     var listMinusOneObject = listObject.Select(x => x).ToList(); 
     listMinusOneObject.Remove(listMinusOneObject.Where(x => Compare(x, objPosition)).First()); 
      //Compare method returns true if the objects are equal 

     if (listMinusOneObject.Any()) 
     { 
      GetAllCombinationsOfAllSizes(listMinusOneObject, newList, ref resultList, maxComboCount); 
     } 
     } 
     return resultList; 
} 

public static void GetAllCombinationsOfAllSizes<T>(List<T> listObject, List<T> growingList, ref List<List<T>> returnResult, int maxComboCount) 
{ 
    var distinctObjects = listObject.Distinct().ToList(); 

    for (int j = 0; j < distinctObjects.Count(); j++) 
    { 
     var objPosition = distinctObjects[j]; 
     var newList = growingList.ToList(); 
     newList.Add(objPosition); 

     if (newList.Count() <= maxComboCount) 
     { 
      returnResult.Add(newList); 
     } 

     var listMinusOneObject = listObject.Select(x => x).ToList(); 
     listMinusOneObject.Remove(listMinusOneObject.Where(x => Compare(x, objPosition)).First()); 

     if (listMinusOneObject.Any()) 
     { 
      GetAllCombinationsOfAllSizes(listMinusOneObject, newList, ref returnResult, maxComboCount); 
     } 
    } 
} 

編輯

這是我的類重寫Equals和GetHashCode的

public class Material 
{ 
    public int Price { get; set; } 
    public string Name { get; set; } 
    public int Num1 { get; set; } 
    public int Num2 { get; set; } 
    public int Num3 { get; set; } 
    public bool isInStock { get; set; } 

    public override bool Equals(object obj) 
    { 
     Material material = obj as Material; 
     return material != null && 
      material.Price == this.Price && 
      material.Name == this.Name && 
      material.Num1 == this.Num1 && 
      material.Num2 == this.Num2 && 
      material.Num3 == this.Num3 && 

    } 

    public override int GetHashCode() 
    { 
     return this.Price.GetHashCode()^
      this.Name.GetHashCode()^
      this.Num1.GetHashCode()^
      this.Num2.GetHashCode()^
      this.Num3.GetHashCode()^

    } 
} 

Answer 1

所以基本上你要找的排列。很多這個可以真正簡化。爲了刪除重複項，您可以傳遞HashSet而不是List。這將消除比較對象的需要，從而加速該過程。

下面是我用了一段時間回來前把所有對象的排列一個HashSet內以下函數指定length：

static IEnumerable<IEnumerable<T>> PermutationOfObjects<T>(IEnumerable<T> objects, int length) 
{ 
    if (length == 1) return objects.Select(t => new T[] { t }); 
    return PermutationOfObjects(objects, length - 1).SelectMany(t => objects, (t1, t2) => t1.Concat(new T[] { t2 })); 
} 

你可以爲了得到內的所有排列組合了以下功能一個HashSet爲指定maxLength：

static IEnumerable<IEnumerable<T>> AllPermutations<T>(IEnumerable<T>list, int maxLength) 
{ 
    IEnumerable<IEnumerable<T>> newList = null; 
    for (int i = 1; i <= maxLength; i++) 
    { if (newList == null) { newList = PermutationOfObjects(list, i); } else newList = newList.Union(PermutationOfObjects(list, i)); } 
    return newList; 
} 

調用它：

HashSet<OBJECT> input = new HashSet<OBJECT>() { obj1, obj2, obj3}; 
int maxComboCount = 2; 
IEnumerable<IEnumerable<OBJECT>> perms = AllPermutations(input, maxComboCount); 

而且回：

[OBJ1]，[OBJ 2]，[OBJ 3]
[OBJ1，OBJ1]，[OBJ1，OBJ2]，[OBJ1，OBJ 3]
[obj2的，OBJ1 ]，[OBJ2，OBJ2]，[OBJ2，OBJ3]
[OBJ3，OBJ1]，[OBJ3，OBJ2]，[OBJ3，OBJ3]

幾個例子：

編輯：

當爲了使用類OBJECT爲HashSet的使用Equals和GetHashCode基於價值的平等檢查，而不是基於引用相等檢查，您需要聲明類這樣：

注意：請注意，這些方法包括類的兩個變量，如果您只需要基於特定變量將對象視爲相同，則只需要包含定義「唯一性」的變量即可。

public class OBJECT 
{ 
    public int ID { get; set; } 
    public string someString { get; set; } 

    public override bool Equals(object obj) 
    { 
     OBJECT q = obj as OBJECT; 
     return q != null && q.ID == this.ID && q.someString == this.someString; 
    } 

    public override int GetHashCode() 
    { 
     return this.ID.GetHashCode()^this.someString.GetHashCode(); 
    } 
} 

之後，您的輸出不應該有重複。