Enhancing Performance of the following combinatorial algorithm

Question

I am using the following code to get all the combinations of an input list of objects while restricting the size of combination (maxComboCount). The code although does what is asked of it ,but is very slow. Could someone please take a look and suggest any changes that can help with the performance.

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

EDIT

This is my class with overridden Equals and 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

So basically you're looking for permutations. A lot of this could really be simplified. In order to remove duplicates you can pass a HashSet to it instead of a List. This would eliminate the need of comparing object which would speed up the process.

Here's the following function I used a while back ago to get the permutations of all objects within a HashSet for a specified 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 }));
}

You can combine it the following function in order to get all permutations within a HashSet for a specified 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;
}

Calling it:

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

And the return:

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

Several examples:

EDIT:

When using a class OBJECT in order for HashSet to use Equals and GetHashCode as value based equality check instead of reference based equality check, you need to declare your class as such:

NOTE: Pay attention that the methods include both variables of the class, if you need the objects to be considered equal only based on a specific variable, you'd need to include only the variable that defines the "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();
    }
}

After that, your output shouldn't have duplicates.