5
\$\begingroup\$

My question is: Using C# and/or Linq, how can this existing code be improved to be more efficient? (My "Complex" example takes about 5 seconds to run, how to make it faster?)

What the code is actually doing: I want to get all unique combinations from choosing 1 number from each group of numbers.

However, I have added 2 additional complexities to this:

  1. I have limitations on the Maximum allowed occurrences of each number in any given combination result set.

  2. I have "prepended" number set that gets applied to every combination, like a prefix.

[Test] 
public void PublicQuestion_SimpleTest() 
{

    List<int> group1 = new List<int>() { 1, 2, 3 };
    List<int> group2 = new List<int>() { 3, 4 };
    List<int> group3 = new List<int>() { 3, 4, 5 };
    List<int> group4 = new List<int>() { 1, 5 };

    List<List<int>> groups = new List<List<int>>()
    {
        group1,
        group2,
        group3,
        group4
    };

    Dictionary<int, int> maximumAllowedOccurances = new Dictionary<int, int>()
    {
         {1, 999}, //1 can occur 999 times: no limitations
         {2, 1}, //2 can occur 1 time, shouldnt be exceeded in this scenario
         {3, 2}, //3 can occur 2 times, will be exceeded a few times
         {4, 2}, //4 can occur 2 times, will be exceeded a few times
         {5, 1}, //5 can occur 1 time, will be exceeded a few times
         {6, 1}  //6 can occur 1 time, shouldn't be exceeded in this scenario, only exists in the prepended set
    };

    List<int> numbersPrePended = new List<int>() { 1, 1, 4, 6 };


    DateTime startTime = DateTime.Now;

    var combinations = GetAllCombinationsOfOneNumberFromEachGroup(numbersPrePended, groups, maximumAllowedOccurances);
    Assert.AreEqual(14, combinations.Count());

    TimeSpan endTime = DateTime.Now.Subtract(startTime);

    Assert.Less(endTime.TotalSeconds, 0.05); //0.0156

    #region string maker
    List<string> combinationStringed = new List<string>();
    foreach (var group in combinations)
    {
        StringBuilder sb = new StringBuilder();
        foreach (var number in group)
        {
            sb.Append(number + ".");
        }
        combinationStringed.Add(sb.ToString());
    }
    StringBuilder sbOrderedResults = new StringBuilder();
    foreach (var result in combinationStringed.OrderBy(x => x))
    {
        sbOrderedResults.Append(result + "|");
    }
    string x1 = sbOrderedResults.ToString().Replace(".|","|");
    #endregion

    Assert.AreEqual(x1, "1.1.1.1.3.3.4.6|1.1.1.1.3.4.4.6|1.1.1.1.3.4.5.6|1.1.1.1.4.4.5.6|1.1.1.2.3.3.4.6|1.1.1.2.3.4.4.6|1.1.1.2.3.4.5.6|1.1.1.2.4.4.5.6|1.1.1.3.3.4.4.6|1.1.1.3.3.4.5.6|1.1.1.3.4.4.5.6|1.1.2.3.3.4.5.6|1.1.2.3.4.4.5.6|1.1.3.3.4.4.5.6|");

}

[Test]
public void PublicQuestion_ComplexTest()
{

    List<int> group1 = new List<int>() { 1, 2, 3 };
    List<int> group2 = new List<int>() { 3, 4 };
    List<int> group3 = new List<int>() { 3, 4, 5 };
    List<int> group4 = new List<int>() { 1, 5 };
    List<int> group5 = new List<int>() { 5, 6, 7, 8 };

    List<List<int>> groups = new List<List<int>>()
    {
        group1,
        group1,
        group2,
        group2,
        group2,
        group3,
        group3,
        group3,
        group4,
        group4,
        group4,
        group5
    };

    Dictionary<int, int> maximumAllowedOccurances = new Dictionary<int, int>()
    {
         {1, 999},
         {2, 1},
         {3, 5},
         {4, 5},
         {5, 7},
         {6, 999},
         {7, 999},
         {8, 999}
    };

    List<int> numbersPrePended = new List<int>() { 1, 1, 4, 6 };



    DateTime startTime = DateTime.Now;

    var combinations = GetAllCombinationsOfOneNumberFromEachGroup(numbersPrePended, groups, maximumAllowedOccurances);
    Assert.AreEqual(852, combinations.Count());

    TimeSpan endTime = DateTime.Now.Subtract(startTime);

    Assert.Less(endTime.TotalSeconds, 5.25); //4.758 seconds

}

public IEnumerable<IEnumerable<int>> GetAllCombinationsOfOneNumberFromEachGroup(
    List<int> numbersPrePended, 
    List<List<int>> groups, 
    Dictionary<int, int> maximumAllowedOccurances)
{
    List<List<int>> returnList = new List<List<int>>();

    _RecursiveGetMoreCombinationsOfOneNumberFromEachGroup(
        ref returnList,
        numbersPrePended,
        groups,
        maximumAllowedOccurances,
        0
        );

    if (returnList.Count() == 0)
    {
        returnList.Add(numbersPrePended);
    }

    return returnList;
}
private void _RecursiveGetMoreCombinationsOfOneNumberFromEachGroup(
    ref List<List<int>> returnList,
    List<int> numbersPrePended,
    List<List<int>> groups,
    Dictionary<int, int> maximumAllowedOccurances,
    int index)
{
    if (groups.Count() < index + 1)
    {
        return;
    }

    var group = groups[index];

    foreach (var number in group)
    {
        List<int> newNumberList = numbersPrePended.ToList();


        int max = 0;
        maximumAllowedOccurances.TryGetValue(number, out max);
        if (newNumberList.Where(x => x == number).Count() < max)
        {
            newNumberList.Add(number);
        }
        else
        {
            continue;
        }

        if (groups.Count() == index + 1)
        {
            newNumberList = newNumberList.OrderBy(x => x).ToList();
            if (ListOfIntListAlreadyContainsThisList(returnList, newNumberList) == false)
            {
                returnList.Add(newNumberList);
            }
        }
        else
        {
            _RecursiveGetMoreCombinationsOfOneNumberFromEachGroup(
                ref returnList,
                newNumberList,
                groups,
                maximumAllowedOccurances,
                index + 1);
        }
    }
}

public bool ListOfIntListAlreadyContainsThisList(List<List<int>> sourceList, List<int> newList)
{            
    foreach (var _list in sourceList)
    {
        var list = _list;

        if (list.Count() == newList.Count())
        {
            if (newList.Count() == 0)
            {
                return true;
            }

            if (list.SequenceEqual(newList))
            {
                return true;
            }
        }
    }

    return false;
}
\$\endgroup\$
4
  • \$\begingroup\$ Use a HashSet<List<int>> instead of a list of lists; that makes adding and checking for a match much much faster. \$\endgroup\$
    – Snowbody
    Commented Jun 10, 2014 at 4:20
  • \$\begingroup\$ @Snowbody Thanks! That appears to have shaved about 10% off the total time to calculate. \$\endgroup\$
    – SED
    Commented Jun 10, 2014 at 13:42
  • \$\begingroup\$ @SED if you would like further review please post a new question that links back to this one and leave a link in the comments here please. \$\endgroup\$
    – Malachi
    Commented Jun 16, 2014 at 22:09
  • \$\begingroup\$ FYI: For an iterative review, is it okay to edit my own question to include revised code? \$\endgroup\$
    – rolfl
    Commented Jun 16, 2014 at 22:14

2 Answers 2

5
\$\begingroup\$

If performance is a big concern, then the following routine will reduce the ComplexTest to 0.08 seconds (on my computer, which appears slower than yours based on your posted results). It can also process any number of groupings. Prepended values are handled like any other group; just add your "prepended" list as several additional 1-item groups.

A class encapsulates the functionality and test methods appear beneath.

public class CombinationFinder
{
    public IList<IList<int>> Groups { get; private set; }
    public IDictionary<int, int> Allowances { get; private set; }

    public CombinationFinder(IList<IList<int>> groups)
        : this(groups, null)
    {
    }

    public CombinationFinder(IList<IList<int>> groups, IDictionary<int, int> allowances)
    {
        // Check if groups are specified
        if (groups == null)
        {
            throw new ArgumentNullException("groups");
        }

        // Copy the list of groups, removing any restricted values
        this.Groups = CopyGroupsWithoutRestrictedValues(groups, allowances);

        // Check if optional allowances are specified
        if (allowances != null && allowances.Count > 0)
        {
            this.Allowances = allowances;
        }
    }

    public IList<IList<int>> GetAll()
    {
        var combinations = new List<IList<int>>();

        if (this.Groups.Count > 0)
        {
            var foundHashes = new Dictionary<int, IList<IList<int>>>();
            var currentCombination = new int[this.Groups.Count];
            int groupIndex = 0;
            FindPermutations(currentCombination, groupIndex, combinations, foundHashes);
        }

        return combinations;
    }

    private void FindPermutations(int[] currentCombination, int groupIndex,
        IList<IList<int>> combinations, IDictionary<int, IList<IList<int>>> foundHashes)
    {
        int maxGroupIndex = this.Groups.Count - 1;

        for (int valueIndex = 0, valueCount = this.Groups[groupIndex].Count; valueIndex < valueCount; ++valueIndex)
        {
            currentCombination[groupIndex] = this.Groups[groupIndex][valueIndex];

            if (groupIndex == maxGroupIndex)
            {
                AddCandidateCombination(currentCombination, combinations, foundHashes);
            }
            else
            {
                FindPermutations((int[])currentCombination.Clone(), groupIndex + 1, combinations, foundHashes);
            }
        }
    }

    private bool AddCandidateCombination(int[] currentCombination,
        IList<IList<int>> combinations, IDictionary<int, IList<IList<int>>> foundHashes)
    {
        int currentHash = GetCombinationHash(currentCombination);
        IList<IList<int>> extantCombinations;
        bool hashCollision = foundHashes.TryGetValue(currentHash, out extantCombinations);
        int[] sortedValues = (int[])currentCombination.Clone();
        Array.Sort(sortedValues);

        if (hashCollision)
        {
            bool combinationFound = false;

            foreach (var extantCombination in extantCombinations)
            {
                combinationFound = CompareCombinations(sortedValues, extantCombination);

                if (combinationFound)
                {
                    break;
                }
            }

            if (combinationFound)
            {
                return false;
            }
        }

        if (!IsWithinAllowances(sortedValues))
        {
            return false;
        }

        if (hashCollision)
        {
            extantCombinations.Add(sortedValues);
        }
        else
        {
            var newCombinationList = new List<IList<int>>();
            newCombinationList.Add(sortedValues);
            foundHashes.Add(currentHash, newCombinationList);
        }

        combinations.Add(sortedValues);
        return true;
    }

    private static int GetCombinationHash(int[] combination)
    {
        int hash = 1;

        unchecked
        {
            for (int index = 0, length = combination.Length; index < length; ++index)
            {
                int operand = combination[index] + 1;
                hash += operand * operand * operand * operand * operand;
            }
        }

        return hash;
    }

    private static bool CompareCombinations(int[] newCombination, IList<int> extantCombination)
    {
        if (newCombination.Length != extantCombination.Count)
        {
            return false;
        }

        for (int valueIndex = 0, length = newCombination.Length; valueIndex < length; ++valueIndex)
        {
            if (newCombination[valueIndex] != extantCombination[valueIndex])
            {
                return false;
            }
        }

        return true;
    }

    private bool IsWithinAllowances(int[] currentCombination)
    {
        if (this.Allowances == null)
        {
            return true;
        }

        int currentValue = 0;
        int currentCount = 0;

        for (int valueIndex = 0, length = currentCombination.Length; valueIndex < length; ++valueIndex)
        {
            if (currentCount == 0)
            {
                currentValue = currentCombination[valueIndex];
                currentCount = 1;
            }
            else if (currentValue != currentCombination[valueIndex])
            {
                if (currentCount > this.Allowances[currentValue])
                {
                    return false;
                }

                currentValue = currentCombination[valueIndex];
                currentCount = 1;
            }
            else
            {
                currentCount++;
            }
        }

        if (currentCount > this.Allowances[currentValue])
        {
            return false;
        }

        return true;
    }

    private static IList<IList<int>> CopyGroupsWithoutRestrictedValues(IList<IList<int>> groups, IDictionary<int, int> allowances)
    {
        IList<IList<int>> sourceGroups;

        if (allowances != null && allowances.Count > 0)
        {
            var restrictedValues = new HashSet<int>();

            foreach (var allowance in allowances)
            {
                if (allowance.Value < 1)
                {
                    restrictedValues.Add(allowance.Key);
                }
            }

            if (restrictedValues.Count > 0)
            {
                sourceGroups = new List<IList<int>>();

                foreach (var valueGroup in groups)
                {
                    if (valueGroup != null && valueGroup.Count > 0)
                    {
                        sourceGroups.Add(RemoveRestrictedValues(valueGroup, restrictedValues));
                    }
                }
            }
            else
            {
                sourceGroups = groups;
            }
        }
        else
        {
            sourceGroups = groups;
        }

        var prunedGroups = new List<IList<int>>();

        foreach (var valueGroup in sourceGroups)
        {
            if (valueGroup != null && valueGroup.Count > 0)
            {
                prunedGroups.Add(valueGroup);
            }
        }

        return prunedGroups;
    }

    private static IList<int> RemoveRestrictedValues(IList<int> valueGroup, ICollection<int> restrictedValues)
    {
        var prunedGroup = new List<int>();

        foreach (int value in valueGroup)
        {
            if (!restrictedValues.Contains(value))
            {
                prunedGroup.Add(value);
            }
        }

        return prunedGroup;
    }
}


[TestMethod]
public void SimpleTest()
{
    // Fixed values
    var group1 = new int[] { 1 };
    var group2 = new int[] { 4 };
    var group3 = new int[] { 6 };

    // Selection values
    var group4 = new int[] { 1, 2, 3 };
    var group5 = new int[] { 3, 4 };
    var group6 = new int[] { 3, 4, 5 };
    var group7 = new int[] { 1, 5 };

    var groups = new List<IList<int>>()
{
    group1,
    group1,
    group2,
    group3,
    group4,
    group5,
    group6,
    group7
};

    var allowances = new Dictionary<int, int>()
{
        {1, 999},
        {2, 1},
        {3, 2},
        {4, 2},
        {5, 1},
        {6, 1}
};

    var finder = new CombinationFinder(groups, allowances);
    var watch = System.Diagnostics.Stopwatch.StartNew();
    IList<IList<int>> results = finder.GetAll();
    watch.Stop();
    Assert.AreEqual(14, results.Count);
    Assert.IsTrue(watch.ElapsedMilliseconds < 50);
    System.Diagnostics.Debug.WriteLine(string.Format(
        "{0:#,##0} combinations found in {1:#,##0.000} seconds.",
        results.Count,
        watch.ElapsedMilliseconds / 1000.0));
}

[TestMethod]
public void ComplexTest()
{
    // Fixed values
    var group1 = new int[] { 1 };
    var group2 = new int[] { 4 };
    var group3 = new int[] { 6 };

    // Selection values
    var group4 = new int[] { 1, 2, 3 };
    var group5 = new int[] { 3, 4 };
    var group6 = new int[] { 3, 4, 5 };
    var group7 = new int[] { 1, 5 };
    var group8 = new int[] { 5, 6, 7, 8 };

    var groups = new List<IList<int>>()
{
    group1,
    group1,
    group2,
    group3,
    group4,
    group4,
    group5,
    group5,
    group5,
    group6,
    group6,
    group6,
    group7,
    group7,
    group7,
    group8
};

    var allowances = new Dictionary<int, int>()
{
        {1, 999},
        {2, 1},
        {3, 5},
        {4, 5},
        {5, 7},
        {6, 999},
        {7, 999},
        {8, 999}
};

    var finder = new CombinationFinder(groups, allowances);
    var watch = System.Diagnostics.Stopwatch.StartNew();
    IList<IList<int>> results = finder.GetAll();
    watch.Stop();
    Assert.AreEqual(852, results.Count);
    Assert.IsTrue(watch.ElapsedMilliseconds < 5250);
    System.Diagnostics.Debug.WriteLine(string.Format(
        "{0:#,##0} combinations found in {1:#,##0.000} seconds.",
        results.Count,
        watch.ElapsedMilliseconds / 1000.0));
}

[TestMethod]
public void RestrictedTest()
{
    // Fixed values
    var group1 = new int[] { 1 };
    var group2 = new int[] { 4 };
    var group3 = new int[] { 6 };

    // Selection values
    var group4 = new int[] { 1, 2, 3 };
    var group5 = new int[] { 3, 4 };
    var group6 = new int[] { 3, 4, 5 };
    var group7 = new int[] { 1, 5 };
    var group8 = new int[] { 5, 6, 7, 8 };

    var groups = new List<IList<int>>()
{
    group1,
    group1,
    group2,
    group3,
    group4,
    group4,
    group5,
    group5,
    group5,
    group6,
    group6,
    group6,
    group7,
    group7,
    group7,
    group8
};

    var allowances = new Dictionary<int, int>()
{
        {1, 999},
        {2, 1},
        {3, 0},
        {4, 0},
        {5, 0},
        {6, 999},
        {7, 999},
        {8, 999}
};

    var finder = new CombinationFinder(groups, allowances);
    var watch = System.Diagnostics.Stopwatch.StartNew();
    IList<IList<int>> results = finder.GetAll();
    watch.Stop();
    Assert.AreEqual(6, results.Count);
    Assert.IsTrue(watch.ElapsedMilliseconds < 5250);
    System.Diagnostics.Debug.WriteLine(string.Format(
        "{0:#,##0} combinations found in {1:#,##0.000} seconds.",
        results.Count,
        watch.ElapsedMilliseconds / 1000.0));
}

Updated: Added the capability of removing restricted values (allowance = 0).

Updated: Removed unnecessary argument exceptions.

\$\endgroup\$
7
  • \$\begingroup\$ There's a problem with your has function. It has a lot of clashes even for small numbers. For example, 0^5 + 5^5 + 6^5 + 16^5 + 17^5 + 22^5 = 1^5 + 2^5 + 10^5 + 12^5 + 20^5 + 21^5. Stolen from en.wikipedia.org/wiki/… \$\endgroup\$
    – Snowbody
    Commented Jun 10, 2014 at 19:24
  • \$\begingroup\$ The hash function is not intended to be collision proof; only to reduce the number of full comparisons between combinations. There is a subsequent routine to verify true duplicates, since hash collisions between different sets are possible. This hash is odd in the sense that it needs to ignore the order of the elements in the array of integers. I arrived at raising to the fifth power, because it yielded zero hash collisions for the posted test data. \$\endgroup\$ Commented Jun 10, 2014 at 19:52
  • \$\begingroup\$ I'd be very interested in ideas for a better hash function for this use case. I was fumbling around trying to find one that worked well. The function needs to process an array of integers, but generate the same hash code for arrays with the same integer values in a different order. \$\endgroup\$ Commented Jun 10, 2014 at 20:26
  • \$\begingroup\$ Very nice job! This has greatly improved performance with the same results, thank you! :) \$\endgroup\$
    – SED
    Commented Jun 11, 2014 at 14:51
  • \$\begingroup\$ @BrianR.Mullin An unintended side effect is that it appears to crap out if a group of numbers have allowances = 0. For example if group6 [3,4,5] are all Allowance = 0, then the entire result set comes back as combinations.Count = 0. How can the code be modified to simply ignore that number instead of doing a return false, so that for example combination "1.1.1.3.7" would return as "1.1.1.7" instead of crapping out completely because the "3" is involved? \$\endgroup\$
    – SED
    Commented Jun 11, 2014 at 17:36
3
\$\begingroup\$

Use a cross join with LINQ to combine the lists of numbers and filter them.

You don't want a list, you want a Multiset, best implemented as a Dictionary<int,int>.

Use a helper class to prevent LINQ from concatenating the multisets/dictionaries. (there may be a better way to do this)

Use Distinct() instead of the HashSet or trying to compare lists yourself.

https://stackoverflow.com/questions/56547/how-do-you-perform-a-cross-join-with-linq-to-sql

using System;
using System.Linq;
using System.Collections.Generic;

public class Listint : IEquatable<Listint>
{
    public Dictionary<int,int> listi;
    public Listint(IEnumerable<int> i)
    {
        listi = new Dictionary<int,int>();
        foreach (var j in i)
        {
            int count;
            listi.TryGetValue(j,out count);
            listi[j] = count+1;
        }
    }
    public bool Equals(Listint other)
    {
        if (Object.ReferenceEquals(other, null)) return false;
        if (Object.ReferenceEquals(this, other)) return true;
        return listi.Equals(other.listi);
    }

    // If Equals() returns true for a pair of objects 
    // then GetHashCode() must return the same value for these objects.
    public override int GetHashCode()
    {
        return listi == null ? 0 : listi.GetHashCode();
    }
}

public class Test
{
    public static void Main()
    {
        List<int> group1 = new List<int>() { 1, 2, 3 };
        List<int> group2 = new List<int>() { 3, 4 };
        List<int> group3 = new List<int>() { 3, 4, 5 };
        List<int> group4 = new List<int>() { 1, 5 };
        Dictionary<int, int> maximumAllowedOccurances = new Dictionary<int, int>()
        {
             {1, 999}, //1 can occur 999 times: no limitations
             {2, 1}, //2 can occur 1 time, shouldnt be exceeded in this scenario
             {3, 2}, //3 can occur 2 times, will be exceeded a few times
             {4, 2}, //4 can occur 2 times, will be exceeded a few times
             {5, 1}, //5 can occur 1 time, will be exceeded a few times
             {6, 1}  //6 can occur 1 time, shouldn't be exceeded in this scenario
        };
        List<int> numbersPrePended = new List<int>() { 1, 1, 4, 6 };
        Func<KeyValuePair<int,int>,bool> SatisfiesConstraint = kvp=>maximumAllowedOccurances[kvp.Key]>=kvp.Value;
        IEnumerable<Listint> result = (
            from n1 in group1
            from n2 in group2
            from n3 in group3
            from n4 in group4
            select new Listint(numbersPrePended.Concat(new int[] {n1,n2,n3,n4})) into d 
            where d.listi.All<KeyValuePair<int,int>>(SatisfiesConstraint)
            select d
            ).Distinct();

        foreach (var l in result) 
        {
            foreach (var n in l.listi)
            {
                Console.Write("{0}:{1},",n.Key,n.Value);
            }
            Console.WriteLine("");
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.