RMad9248 - 1 year ago 65
C# Question

# Enhancing Performance of the following combinatorial algorithm

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

if (newList.Count() <= maxComboCount)
{
}

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

if (newList.Count() <= maxComboCount)
{
}

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 BaseCard
{
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)
{
BaseCard baseCard = obj as BaseCard;
return baseCard != null &&
baseCard.Price == this.Price &&
baseCard.Name == this.Name &&
baseCard.Num1 == this.Num1 &&
baseCard.Num2 == this.Num2 &&
baseCard.Num3 == this.Num3 &&

}

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

}
}
``````

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download