Possible combinations following a rule The problem is the following:

We have a number of months to buy a number of supplies. The sooner we finish buying them, the better, but we don't know how much we can buy per month and would like to calculate all possible scenarios.

Suppose months = 5 and supplies = 9, and (72000) means 7 in the first month, 2 in the second and 0 in the following months.


VALID:   (90000)
VALID:   (81000)
VALID:   (72000)
VALID:   (71100)
INVALID: (61200)
INVALID: (80100)



This is basically a problem of combinations following a rule: in a MONTHS sized array, the n-th element cannot be larger than the (n-1)-th element, and the sum of all elements must be SUPPLIES.

My solution to do this was slicing the array into smaller parts and carrying digits over:

var months = 5;
var supplies = 9;

function calc(sum, nslots, maxdigit){
    if (sum === 0) return [];
    if (nslots === 0) return [];

    maxdigit = maxdigit || sum;

    var results = [];

    var firstDigit = Math.min(maxdigit,sum);
    if (maxdigit &gt;= sum){
        var digits = [];
        for(var i=0;i&lt;nslots;i++) digits.push(0);       

        digits[0] = firstDigit;

        results = [digits];
    }

    for(;firstDigit&gt;0;firstDigit--){
        var pointsLeft = sum - firstDigit;
        if (pointsLeft === 0) continue;

        var subArrays = calc(pointsLeft, nslots-1, firstDigit);

        if (subArrays.length === 0) continue;

        var subResults = subArrays.map(function(i){return [firstDigit].concat(i);});
        results = results.concat(subResults);
    }

    return results;
}

var results = calc(supplies,months);
console.log(results);


It's not in any way clear what this does though, and I myself would probably have a hard time understanding this code a year from now.

The clearest way I can imagine is just generating all numbers from 90000 down to 0 (in the 9 supplies and 5 months example) and checking if each number follows the rule, but it's ridiculous for bigger values of MONTHS and SUPPLIES.

I'd prefer a solution in ALGOL-descending languages. I imagine Python, Haskell or Erlang probably have some awesome way to solve this in just a few lines, but I couldn't use them here.
What you're looking for is all (ordered) integer partitions (of supplies) up to a maximum length (months).

Here is a solution in C#, as I'm not that comfortable with JavaScript.

private static IEnumerable&lt;int[]&gt; GetPartitions(int n, int length)
{
    return GetPartitions(n, length, n);
}

private static IEnumerable&lt;int[]&gt; GetPartitions(int n, int length, int max)
{
    if (n == 0)
    {
        // Only one way to partition 0.
        yield return new int[length];
        yield break;
    }

    if (n &gt; length * max)
    {
        // No ways to partition n, as each of the elements
        // must be &lt;= max.
        yield break;
    }

    for (var i = Math.Min(n, max); i &gt; 0; i--)
    {
        foreach (var partition in GetPartitions(n - i, length - 1, i))
        {
            var newPartition = new List&lt;int&gt;(length);
            newPartition.Add(i);
            newPartition.AddRange(partition);
            yield return newPartition.ToArray();
        }
    }
}


And the output of GetPartitions(9, 5):

9, 0, 0, 0, 0
8, 1, 0, 0, 0
7, 2, 0, 0, 0
7, 1, 1, 0, 0
6, 3, 0, 0, 0
6, 2, 1, 0, 0
6, 1, 1, 1, 0
5, 4, 0, 0, 0
5, 3, 1, 0, 0
5, 2, 2, 0, 0
5, 2, 1, 1, 0
5, 1, 1, 1, 1
4, 4, 1, 0, 0
4, 3, 2, 0, 0
4, 3, 1, 1, 0
4, 2, 2, 1, 0
4, 2, 1, 1, 1
3, 3, 3, 0, 0
3, 3, 2, 1, 0
3, 3, 1, 1, 1
3, 2, 2, 2, 0
3, 2, 2, 1, 1
2, 2, 2, 2, 1


And here is my attempt in JavaScript:

function getPartitions(n, length, max) {
    if (n === 0) {
        // Only one way to partition 0.
        var result = [];
        for (var i = 0; i &lt; length; i++) {
            result[i] = 0;
        }
        return [result];
    }

    if (n &gt; length * max) {
        // No ways to partition n, as each of the elements
        // must be &lt;= max.
        return [];
    }

    var partitions = [];
    for (var i = Math.min(n, max); i &gt; 0; i--) {
        getPartitions(n - i, length - 1, i).forEach(function(partition) {
            partition.unshift(i);
            partitions.push(partition);
        });
    }

    return partitions;
}

getPartitions(9, 5, 9).forEach(function(partition) {
    console.log(partition);
});