增强以下组合算法的性能

Question

我正在使用以下代码获取输入对象列表的所有组合，同时限制组合的大小 (maxComboCount)。该代码虽然可以执行要求的操作，但速度非常慢。有人可以看一下并提出有助于提高性能的任何更改吗？

E.g. Input:

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

Output:

[obj1], [obj2], [obj3],

[obj1,obj1], [obj1,obj2], [obj1,obj3],

[obj2,obj1], [obj2,obj2], [obj2,obj3],

[obj3,obj1], [obj3,obj2], [obj3,obj3]

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);
        }
    }
}

编辑

这是我的 class，具有覆盖的 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。这将消除比较对象的需要，从而加快该过程。

这是我前段时间使用的以下函数，用于获取指定 length 的 HashSet 中所有对象的排列：

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 }));
}

您可以将其与以下函数结合使用，以获得指定 maxLength 的 HashSet 内的所有排列：

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);

和 return:

[obj1], [obj2], [obj3]
[obj1,obj1], [obj1,obj2], [obj1,obj3]
[obj2,obj1], [obj2,obj2], [obj2,obj3]
[obj3,obj1], [obj3,obj2], [obj3,obj3]

几个例子：

编辑：

当使用 class OBJECT 以便 HashSet 使用 Equals 和 GetHashCode 作为基于值的相等性检查而不是基于引用的相等性检查时，您需要声明你的class：

注意：注意方法包括 class 的两个变量，如果您需要仅基于特定变量将对象视为相等，则只需包括定义的变量"uniqueness".

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();
    }
}

之后，您的输出不应有重复项。

增强以下组合算法的性能

Enhancing Performance of the following combinatorial algorithm

c#

performance

combinatorics