Suppose you have a set of values (1
,1
,1
,12
,12
,16
) how would you generate all possible combinations (without repetition) whose sum is within a predefined range [min,max]
. For example, here are all the combinations (of all depths) that have a range between 13
and 17
:
1
12
1
1
12
1
1
1
12
16
1
16
This assumes that each item of the same value is indistinguishable, so you don't have three results of 1
12
in the final output. Brute force is possible, but in situations where the number of items is large, the number of combinations at all depths is astronomical. In the example above, there are (3 + 1) * (2 + 1) * (1 + 1) = 24 combinations at all depths. Thus, the total combinations is the product of the number of items of any given value + 1. Of course we can logically throw out huge number of combinations whose partial sum is greater than the max value (e.g. the set 16
12
is already bigger than the max value of 17
, so skip any combinations that have a 16
and 12
in them).
I originally thought I could convert the input array into two arrays and increment them kind of like an odometer. But I am getting completely stuck on this recursive algorithm that breaks early. Any suggestions?
{
int uniqueValues = 3;
int[] maxCounts = new int[uniqueValues];
int[] values = new int[uniqueValues];
// easy code to bin the data, just hardcoding for example
maxCounts[0] = 3;
values[0] = 1;
maxCounts[1] = 2;
values[1] = 12;
maxCounts[2] = 1;
values[2] = 16;
GenerateCombinationsHelper(new List<int[]>(), 13, 17, 0, 0, maxCounts, new int[3], values);
}
private void GenerateCombinationsHelper(List<int[]> results, int min, int max, int currentValue, int index, int[] maxValues, int[] currentCombo, int[] values)
{
if (index >= maxValues.Length)
{
return;
}
while (currentCombo[index] < maxValues[index])
{
currentValue += values[index];
if (currentValue> max)
{
return;
}
currentCombo[index]++;
if (currentValue< min)
{
GenerateCombinationsHelper(results, min, max, currentValue, index + 1, maxValues, currentCombo, values);
}
else
{
results.Add((int[])currentCombo.Clone());
}
}
}
Edit
The integer values are just for demonstration. It can be any object that has a some sort of numerical value (int
, double
, float
, etc...)
Typically there will only be a handful of unique values (~10 or so) but there can be several thousands total items.
{1,16}
should be valid. – Geobits Oct 10 '13 at 1:12