5
\$\begingroup\$

The test

PublicQuestion_ComplexTest

is taking around 1600ms (1.6 seconds) to run, but used to take 92ms. I have a feeling this is because of recent code changes that include .Count() in many places within these 2 functions:

RemoveSmallerLengthNumberListsThatContainSameNumberCombinationAsLargerLengthCombinations

and

CropNumbersToBeWithinAllowances

The goal is for the code to run much more efficiently, hopefully under 100ms. Any suggestions?

    [Test] 
    public void PublicQuestion_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, //1
            group1, //1
            group2, //4
            group3, //6
            group4, //1, 2, 3
            group5, //3, 4
            group6, //3, 4, 5
            group7  //1, 5
        };

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

        var finder = new PickOneNumberFromEachGroupCombinationFinder(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 < 22); //7ms



        #region string maker
        List<string> combinationStringed = new List<string>();
        foreach (var group in results)
        {
            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|");
        System.Diagnostics.Debug.WriteLine(string.Format(
            "{0:#,##0} combinations found in {1:#,##0.000} seconds.",
            results.Count,
            watch.ElapsedMilliseconds / 1000.0));
    }

    [Test] 
    public void PublicQuestion_SimpleMoreCombinationsTest()
    {
        // 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,
            group4,
            group4,
            group4,
            group5,
            group6,
            group7,
            group8
        };

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

        var finder = new PickOneNumberFromEachGroupCombinationFinder(groups, allowances);
        var watch = System.Diagnostics.Stopwatch.StartNew();
        IList<IList<int>> results = finder.GetAll();



        #region string maker
        List<string> combinationStringed = new List<string>();
        foreach (var group in results)
        {
            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

        string x2 = x1;


        watch.Stop();
        Assert.AreEqual(684, results.Count);
        Assert.IsTrue(watch.ElapsedMilliseconds < 535); //265 //28ms
        System.Diagnostics.Debug.WriteLine(string.Format(
            "{0:#,##0} combinations found in {1:#,##0.000} seconds.",
            results.Count,
            watch.ElapsedMilliseconds / 1000.0));
    }

    [Test] 
    public void PublicQuestion_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 PickOneNumberFromEachGroupCombinationFinder(groups, allowances);
        var watch = System.Diagnostics.Stopwatch.StartNew();
        IList<IList<int>> results = finder.GetAll();
        watch.Stop();


        #region string maker
        List<string> combinationStringed = new List<string>();
        foreach (var group in results)
        {
            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
        string combinationsStringed = x1;


        Assert.AreEqual(852, results.Count);
        Assert.IsTrue(watch.ElapsedMilliseconds < 2000); //1625 
        System.Diagnostics.Debug.WriteLine(string.Format(
            "{0:#,##0} combinations found in {1:#,##0.000} seconds.",
            results.Count,
            watch.ElapsedMilliseconds / 1000.0));
    }

    [Test] 
    public void RestrictedTest1()
    {
        // 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 PickOneNumberFromEachGroupCombinationFinder(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 < 112); //19 //2ms
        System.Diagnostics.Debug.WriteLine(string.Format(
            "{0:#,##0} combinations found in {1:#,##0.000} seconds.",
            results.Count,
            watch.ElapsedMilliseconds / 1000.0));
    }

    [Test] 
    public void RestrictedTest2()
    {
        // Fixed values
        var group1 = new int[] { 4 };
        var group2 = new int[] { 6 };
        var group3 = new int[] { 7 };

        // Selection values
        var group4 = new int[] { 50, 51 };
        var group5 = new int[] { 3, 8, 12 };
        var group6 = new int[] { 42, 43 };

        var groups = new List<IList<int>>()
        {
            group1, //4
            group1, //4
            group2, //6
            group2, //6
            group2, //6
            group3, //7
            group3, //7
            group3, //7
            group4, //50, 51
            group4, //50, 51
            group5, //3, 8, 12
            group5, //3, 8, 12
            group6, //42, 43
        };

        var allowances = new Dictionary<int, int>()
        {
            {3, 2},
            {4, 1},
            {6, 1},
            {7, 0},
            {8, 1},
            {12, 0},
            {42, 0},
            {43, 0},
            {50, 2},
            {51, 2},
        };

        var finder = new PickOneNumberFromEachGroupCombinationFinder(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 < 113); //16 //3ms
        System.Diagnostics.Debug.WriteLine(string.Format(
            "{0:#,##0} combinations found in {1:#,##0.000} seconds.",
            results.Count,
            watch.ElapsedMilliseconds / 1000.0));
    }

    [Test]
    public void HugeNumbersTest()
    {
        // Fixed values
        int largestInt32 = Int32.MaxValue;
        var group1 = new int[] { 5 };
        var group2 = new int[] { 456789 };
        var group3 = new int[] { 982981929 };
        var group4 = new int[] { largestInt32 };

        // Selection values
        var group5 = new int[] { 43234234, 1111511, 77878778 };
        var group6 = new int[] { 24352, 44, 981981980 };
        var group7 = new int[] { largestInt32, 44, 981981980, 77878778 };

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

        var allowances = new Dictionary<int, int>()
        {
            {5, 999},
            {456789, 999},
            {982981929, 999},
            {largestInt32, 999},
            {43234234, 999},
            {1111511, 999},
            {77878778, 999},
            {24352, 999},
            {44, 999},
            {981981980, 999},
        };

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

    [Test]
    public void RemoveSmallerLengthNumberListsThatContainSameNumberCombinationAsLargerLengthCombinationsTest()
    {
        var combo1 = new int[] { 1, 2, 2, 2, 2, 2, 5, 6, 7 };
        var combo2 = new int[] { 1, 1, 2, 3, 4, 5 }; 
        var combo3 = new int[] { 1, 1,    3, 4, 5 }; //duplicate of combo2
        var combo4 = new int[] { 1, 1, 2, 3,    5 }; //duplicate of combo2
        var combo5 = new int[] {    1, 2, 3, 4, 5 }; //duplicate of combo2
        var combo6 = new int[] { 1, 1, 2, 3, 4    }; //duplicate of combo2
        var combo7 = new int[] {    1, 2,       5 }; //duplicate of combo2
        var combo8 = new int[] {       2,       5 }; //duplicate of combo2
        var combo9 = new int[] {       2          }; //duplicate of combo1 or combo2
        var combo10 = new int[] { 2, 2, 2, 2, 5 }; //duplicate of combo1
        var combo11 = new int[] { 2, 2, 2, 2, 6 }; //duplicate of combo1
        var combo12 = new int[] { 2, 2, 2, 2, 7 }; //duplicate of combo1
        var combo13 = new int[] { 2, 2, 2, 2, 8 };
        var combo14 = new int[] { 1, 2, 2, 2, 5 }; //duplicate of combo1
        var combo15 = new int[] { 0, 1, 4, 5 };
        var combo16 = new int[] { 1, 1, 4, 5 }; //duplicate of combo2 or combo3
        var combo17 = new int[] { 1, 1, 4, 5, 6 }; 

        var allCombos = new List<IList<int>>()
        {
            combo1,
            combo2,
            combo3,
            combo4,
            combo5,
            combo6,
            combo7,
            combo8,
            combo9,
            combo10,
            combo11,
            combo12,
            combo13,
            combo14,
            combo15,
            combo16,
            combo17
        };

        var watch = System.Diagnostics.Stopwatch.StartNew();

        for (int i = 0; i < 100; i++)
        {
            //testing to see how long it takes for this to run
            var ignoredResults = (new PickOneNumberFromEachGroupCombinationFinder()).RemoveSmallerLengthNumberListsThatContainSameNumberCombinationAsLargerLengthCombinations(allCombos);
        }
        var results = (new PickOneNumberFromEachGroupCombinationFinder()).RemoveSmallerLengthNumberListsThatContainSameNumberCombinationAsLargerLengthCombinations(allCombos);

        watch.Stop();

        Assert.IsTrue(watch.ElapsedMilliseconds < 25); //14





        Assert.AreEqual(5, results.Count());

        string resultsToString = string.Join("", results.Select(x => string.Join(",", x.Select(y => y.ToString()).ToArray()) + "|" ).ToArray());
        Assert.AreEqual(resultsToString, "1,2,2,2,2,2,5,6,7|1,1,2,3,4,5|2,2,2,2,8|1,1,4,5,6|0,1,4,5|");
    }


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

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

            combinations = RemoveSmallerLengthNumberListsThatContainSameNumberCombinationAsLargerLengthCombinations(combinations);

            return combinations;
        }

        private List<IList<int>> RemoveSmallerLengthNumberListsThatContainSameNumberCombinationAsLargerLengthCombinations(List<IList<int>> combinations)
        {
            if (combinations.Any() == false)
            {
                return new List<IList<int>>();
            }

            //it is assumed, due to previous code that generates the combinations, that no 2 combinations can be the exact same (1,2,2,3 vs 2,1,2,3 = same)
            var newCombinations = new List<IList<int>>();

            var sortedCombinations = (from w in combinations orderby w.Count descending select w);

            int maxLength = sortedCombinations.First().Count();
            for (int i = 0; i < sortedCombinations.Count(); i++)
            {
                var combination = sortedCombinations.Skip(i).First();
                if (combination.Count() == maxLength)
                {
                    newCombinations.Add(combination);
                    continue;
                }

                bool exists = false;
                foreach (var newCombo in newCombinations)
                {
                    if (LargerComboContainsSmallerCombo(newCombo, combination))
                    {
                        exists = true;
                        break;
                    }
                }

                if (exists == false)
                {
                    newCombinations.Add(combination);
                    continue;
                }
            }

            return newCombinations;
        }

        private bool LargerComboContainsSmallerCombo(IList<int> largerList, IList<int> smallerList)
        {
            if (largerList.Count() == smallerList.Count())
            {
                return false;
            }

            var distinctNumbersInSmaller = smallerList.Distinct();

            foreach (var number in distinctNumbersInSmaller)
            {
                if (largerList.Where(x => x == number).Count() < smallerList.Where(x => x == number).Count())
                {
                    return false;
                }
            }

            return true;
        }

        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)
        {
            currentCombination = CropNumbersToBeWithinAllowances(currentCombination);

            if (currentCombination.Count() == 0)
            {
                return false;
            }

            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 (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 int[] CropNumbersToBeWithinAllowances(int[] currentCombination)
        {
            if (this.Allowances == null)
            {
                return currentCombination;
            }

            List<int> newCombination = new List<int>();

            for (int i = 0; i < currentCombination.Length; i++)
            {
                int currentValue = currentCombination[i];

                if (newCombination.Where(x => x == currentValue).Count() >= this.Allowances[currentValue])
                {
                    continue;
                }

                newCombination.Add(currentValue);
            }

            return newCombination.ToArray();
        }

        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;
        }
    }
\$\endgroup\$
  • 2
    \$\begingroup\$ Only glanced at your code, but you should use .Count (property) on List<T>. The .Count() method works off the IEnumerable<T> and iterates the entire collection. You need to reduce the number of times you're iterating an IEnumerable<T> - call .ToList() once and use the list's Count property instead. \$\endgroup\$ – Mathieu Guindon Jun 17 '14 at 18:59
  • 1
    \$\begingroup\$ And as far as I know using the Count() on IEnumerable<T> will utilize the lazy evaluation and the results of it wouldn't be that trusted. \$\endgroup\$ – Mehrad Jun 18 '14 at 0:04
  • 6
    \$\begingroup\$ Just a note, Enumerable.Count() is optimized for ICollection<T> to use the .Count member property. I'm not worried about its usage on actual lists. On other enumerables (query results, etc.), it could still be an issue. \$\endgroup\$ – Anthony Pegram Jun 18 '14 at 2:16
  • \$\begingroup\$ @AnthonyPegram indeed! that's funny, I was just told exactly that! You bet I've learned something today! :) \$\endgroup\$ – Mathieu Guindon Jun 18 '14 at 2:19
4
\$\begingroup\$

Documentation

This is quite a lot of code. I can tell you've put some effort into the naming of methods, but comments describing the purpose of each would go a long way.

Imagine that you're looking at this code for the first time -- is it clear to you what the output of a call to GetAll should be? What conditions will hold on the result?

For example, I believe the following are true (correct me if I'm wrong) and worth documenting:

// For each `result` in the returned value, it is true that
//    result.Distinct().All(x => result.Count(y => y == x) <= allowances[x]).

// For each `result` in the returned value, it is true that
//     result.OrderBy(x => x).SequenceEqual(result).

// For each distinct `x` and `y` in the returned value, it is false that
//     x.SequenceEqual(y).

Use the framework

It looks like you're not using the .NET framework to its full extent. Let's look at a couple of examples.

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

Could be rewritten as

private static IList<int> RemoveRestrictedValues(IList<int> valueGroup, ICollection<int> restrictedValues)
{
    return valueGroup.Where(value => !restrictedValues.Contains(value))
        .ToList();
}

If the original version has significant performance benefits, document it as such to make it clear to the reader that that's why you wrote it that way. For example,

// PERFORMANCE: The foreach version is significantly faster
// than the valueGroup.Where(...).ToList() alternative.

In fact, I think both CopyGroupsWithoutRestrictedValues and RemoveRestrictedValues can be replaced by one method:

private static List<List<int>> CopyGroupsWithoutRestrictedValues(IList<IList<int>> groups, IDictionary<int, int> allowances)
{
    return groups.Select(group => group.Where(x => allowances[x] > 0).ToList())
        .Where(group => group.Any())
        .ToList();
}

In your tests, the string maker region can be replaced with this:

string.Join(
    "|",
    results.Select(result => string.Join(".", result)).OrderBy(result => result));

The method AddCandidateCombination could probably be replaced by a call to Distinct, with GetCombinationHash and CompareCombinations being the basis for the IEqualityComparer<int> argument (see code below if this isn't clear).

API

Why is there a parameterless constructor? What is the expected result of new PickOneNumberFromEachGroupCombinationFinder().GetAll()?

Why have a constructor at all? What can I do with an instance of PickOneNumberFromEachGroupCombinationFinder other than repeatedly call GetAll, returning the same result? I think it would be fine to replace GetAll with a static method, so client code might read

var combinations = CombinationFinder.PickOneFromEachGroup(groups, allowances);

Edit This code passes all tests and is significantly faster on my machine.

public static IEnumerable<IList<int>> PickOneFromEachGroup(
    IList<IList<int>> groups,
    Dictionary<int, int> allowed)
{
    var combinations = GetCombinationsHelper(new int[groups.Count], groups.Count, 0, groups, 0, allowed)
        .Distinct(new ArrayComparer());
    return RemoveSmallerCombinations(combinations);
}

private static IEnumerable<int[]> GetCombinationsHelper(
    int[] result,
    int resultLength,
    int resultIndex,
    IList<IList<int>> groups,
    int groupIndex,
    Dictionary<int, int> allowed)
{
    // Base case: the array is full.
    if (resultIndex == resultLength)
    {
        var copy = new int[resultLength];
        Array.Copy(result, copy, resultLength);
        Array.Sort(copy);
        yield return copy;
        yield break;
    }

    var nextGroupIndex = groupIndex + 1;
    var nextResultIndex = resultIndex + 1;
    var foundAny = false;
    foreach (var x in groups[groupIndex])
    {
        if (allowed[x] <= 0)
        {
            continue;
        }

        foundAny = true;

        result[resultIndex] = x;
        allowed[x]--;
        foreach (var combination in GetCombinationsHelper(result, resultLength, nextResultIndex, groups, nextGroupIndex, allowed))
        {
            yield return combination;
        }

        allowed[x]++;
    }

    // No elements in groups[groupIndex] had a positive allowance,
    // so skip this group.
    if (!foundAny)
    {
        foreach (var combination in GetCombinationsHelper(result, resultLength - 1, resultIndex, groups, nextGroupIndex, allowed))
        {
            yield return combination;
        }
    }
}

private static IEnumerable<int[]> RemoveSmallerCombinations(IEnumerable<int[]> combinations)
{
    using (var enumerator = combinations.OrderByDescending(combination => combination.Length).GetEnumerator())
    {
        if (!enumerator.MoveNext())
        {
            yield break;
        }

        var current = enumerator.Current;
        var maxLength = current.Length;
        yield return current;

        while (enumerator.MoveNext())
        {
            current = enumerator.Current;
            if (current.Length != maxLength)
            {
                yield break;
            }

            yield return current;
        }
    }
}

private class ArrayComparer : IEqualityComparer<int[]>
{
    public bool Equals(int[] x, int[] y)
    {
        if (x.Length != y.Length)
        {
            return false;
        }

        for (var i = 0; i < x.Length; i++)
        {
            if (x[i] != y[i])
            {
                return false;
            }
        }

        return true;
    }

    public int GetHashCode(int[] obj)
    {
        unchecked
        {
            var result = 17;
            foreach (var x in obj)
            {
                result = result * 31 + x.GetHashCode();
            }

            return result;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Very good feedback, much appreciated! Unfortunately the code suggestion you provided: 2 Tests fail, both are returning 0 results: RestrictedTest1 and RestrictedTest2 -- do you have any suggestions on how to rework your suggested answer to allow for all provided tests to pass? \$\endgroup\$ – SED Jun 23 '14 at 19:12
  • \$\begingroup\$ Updated the RestrictedTest1 and RestrictedTest2 to include more precise expected results -- refer to Assert.AreEqual(x1, ... \$\endgroup\$ – SED Jun 23 '14 at 19:21
  • \$\begingroup\$ @SED I've updated with code that passes the tests. \$\endgroup\$ – mjolka Jun 24 '14 at 6:28
  • \$\begingroup\$ Verified: all tests pass, speed is improved. The ComplexTest takes ~125ms -- THANK YOU! :) \$\endgroup\$ – SED Jun 24 '14 at 14:40
5
\$\begingroup\$

In CropNumbersToBeWithinAllowances() you do

newCombination.Where(x => x == currentValue).Count()

inside the for loop. newCombination is of type List<T> so calling Count() on that would fall back to Count (as Anthony Pegram already mentioned in the comments). However, the Where query turns that into an IEnumerable<T> so Count() will indeed iterate the whole enumerable in every iteration of the loop!

Instead keep track of the remaining allowances by decrementing the Allowances dictionary (or a copy if you need to keep it). Something like this (untested):

private int[] CropNumbersToBeWithinAllowances(int[] currentCombination)
{
    if (this.Allowances == null)
        return currentCombination;

    // Create a copy from the this.Allowances dictionary
    Dictionary<int, int> remainingAllowances = new Dictionary<int, int>(this.Allowances);

    List<int> newCombination = new List<int>();

    for (int i = 0; i < currentCombination.Length; i++)
    {
        int currentValue = currentCombination[i];

        if(remainingAllowances[currentValue]==0)
            continue;

        newCombination.Add(currentValue);
        remainingAllowances[currentValue]--;
    }

    return newCombination.ToArray();
}

Update

In the method with the long name you do

var sortedCombinations = (from w in combinations orderby w.Count descending select w);

int maxLength = sortedCombinations.First().Count();
for (int i = 0; i < sortedCombinations.Count(); i++)
{
    var combination = sortedCombinations.Skip(i).First();
    if (combination.Count() == maxLength)
    {
        ...

sortedCombinations is of type IEnumerable<T>. That means that you enumerate the whole enumerable every time you call Count() and Skip() inside the loop!

You could cast the sortedCombinations enumerable to something like an array or a list and use Length or Count instead of Count() (as Frank suggested). But since you are only using the loop variable to access elements of the enumerable in order you could as well just use foreach:

var sortedCombinations = (from w in combinations orderby w.Count descending select w);

// Note: IList<T> is an ICollection<T> so IList<T>.Count() will fall back to the Count property
int maxLength = sortedCombinations.First().Count();
foreach(var combination in sortedCombinations)
{
    if (combination.Count() == maxLength) // see note above
    {
        ...
\$\endgroup\$
2
\$\begingroup\$

After looking a bit at it, I managed to cut the runtime roughly in half by adding a .ToArray() in RemoveSmallerLengthNumberListsThatContainSameNumberCombinationAsLargerLengthCombinations on the sortedCombinations query like so:

var sortedCombinations = (from w in combinations orderby w.Count descending select w).ToArray();`

When using the Count() as the loop condition, and then doing a Skip + First, you are effectively sorting this collection Count*2 times because of deferred execution.

\$\endgroup\$
  • \$\begingroup\$ Very good suggestion! Yes on my end it cuts it in half as well, down from ~1400ms to ~600ms :) That "for" syntax that was badly written was my attempt to follow someone elses advice that you should "always use for instead of foreach for efficiency": I suppose that only helps if you write it a certain way ;) \$\endgroup\$ – SED Jun 20 '14 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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