Efficient way to get every unique combination of "Pick 1 number from each Group of Numbers"

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:

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

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

```
[Test]
public void PublicQuestion_SimpleTest()
{

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

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

Dictionary maximumAllowedOccurances = new Dictionary()
{
{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 numbersPrePended = new List() { 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 combinationStringed = new List();
foreach (var group in combinations)
{
StringBuilder sb = new StringBuilder();
foreach (var number in group)
{

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> Groups { get; private set; }
public IDictionary Allowances { get; private set; }

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

public CombinationFinder(IList> groups, IDictionary 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> GetAll()
{
var combinations = new List>();

if (this.Groups.Count > 0)
{
var foundHashes = new Dictionary>>();
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> combinations, IDictionary>> foundHashes)
{
int maxGroupIndex = this.Groups.Count - 1;

for (int valueIndex = 0, valueCount = this.Groups[groupIndex].Count; valueIndex > combinations, IDictionary>> foundHashes)
{
int currentHash = GetCombinationHash(currentCombination);
IList> 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>();
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 extantCombination)
{
if (newCombination.Length != extantCombination.Count)
{
return false;
}

for (int valueIndex = 0, length = newCombination.Length; valueIndex this.Allowances[currentValue])
{
return false;
}

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

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

return true;
}

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

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

foreach (var allowance in allowances)
{
if (allowance.Value 0)
{
sourceGroups = new List>();

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

foreach (var valueGroup in sourceGroups)
{
if (valueGroup != null && value

StackExchange Code Review Q#53822, answer score: 5