Databases
StackOverflow2013
Postsdbo
POHow to efficiently generate all combinations (at all depths) whose sum is within a specified range
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to efficiently generate all combinations (at all depths) whose sum is within a specified range
    text
    copied!<p>Suppose you have a set of values (<code>1</code>,<code>1</code>,<code>1</code>,<code>12</code>,<code>12</code>,<code>16</code>) how would you generate all possible combinations (without repetition) whose sum is within a predefined range <code>[min,max]</code>. For example, here are all the combinations (of all depths) that have a range between <code>13</code> and <code>17</code>:</p> <p><code>1</code> <code>12</code></p> <p><code>1</code> <code>1</code> <code>12</code></p> <p><code>1</code> <code>1</code> <code>1</code> <code>12</code></p> <p><code>16</code></p> <p><code>1</code> <code>16</code></p> <p>This assumes that each item of the same value is indistinguishable, so you don't have three results of <code>1</code> <code>12</code> 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 <code>16</code> <code>12</code> is already bigger than the max value of <code>17</code>, so skip any combinations that have a <code>16</code> and <code>12</code> in them).</p> <p>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?</p> <pre><code>{ 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&lt;int[]&gt;(), 13, 17, 0, 0, maxCounts, new int[3], values); } private void GenerateCombinationsHelper(List&lt;int[]&gt; results, int min, int max, int currentValue, int index, int[] maxValues, int[] currentCombo, int[] values) { if (index &gt;= maxValues.Length) { return; } while (currentCombo[index] &lt; maxValues[index]) { currentValue += values[index]; if (currentValue&gt; max) { return; } currentCombo[index]++; if (currentValue&lt; min) { GenerateCombinationsHelper(results, min, max, currentValue, index + 1, maxValues, currentCombo, values); } else { results.Add((int[])currentCombo.Clone()); } } } </code></pre> <p><strong>Edit</strong></p> <p>The integer values are just for demonstration. It can be any object that has a some sort of numerical value (<code>int</code>, <code>double</code>, <code>float</code>, etc...)</p> <p>Typically there will only be a handful of unique values (~10 or so) but there can be several thousands total items.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload