代码之家 › 专栏 › 技术社区 › Satya

提高以下组合算法的性能

combinatorics performance c#

Satya · 技术社区 · 7 年前

例如。

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

编辑

这是我的类,包含重写的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() ^

    }
}

1 回复 | 直到 7 年前

Hubbs 7 年前

所以基本上你在寻找排列。很多事情都可以简化。为了删除重复项,您可以传递 HashSet List . 这将消除比较对象的需要,从而加快过程。

这是我不久前使用的以下函数,用于获取 哈希集 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 }));
}

哈希集 对于指定的 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]、[obj2]、[obj3]
[obj1,obj1],[obj1,obj2],[obj1,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();
    }
}

在此之后,您的输出不应该有重复项。