Possible combinations following a rule

Question

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 >= sum){
        var digits = [];
        for(var i=0;i<nslots;i++) digits.push(0);       

        digits[0] = firstDigit;

        results = [digits];
    }

    for(;firstDigit>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.

Answer 1

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<int[]> GetPartitions(int n, int length)
{
    return GetPartitions(n, length, n);
}

private static IEnumerable<int[]> 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 > length * max)
    {
        // No ways to partition n, as each of the elements
        // must be <= max.
        yield break;
    }

    for (var i = Math.Min(n, max); i > 0; i--)
    {
        foreach (var partition in GetPartitions(n - i, length - 1, i))
        {
            var newPartition = new List<int>(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 < length; i++) {
            result[i] = 0;
        }
        return [result];
    }

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

    var partitions = [];
    for (var i = Math.min(n, max); i > 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);
});

Answer 2

Your function seems to generate correct results. It took me many tries to get a similarly correct program.

The function name, calc(), is excessively generic. Since it's an integer partitioning problem, and the entries in the results are all monotonically non-increasing, I suggest nonIncreasingPartition() instead.

Recursion is definitely the way to go. However, instead of concatenating subarrays, it would be simpler to use nested calls to fill in entries after a certain index. Memory use would be more efficient as well: for scratch space, only one array, of length nSlots, is ever allocated.

function nonIncreasingPartition(sum, nSlots, maxElement) {
    var solutions = [];

     /**
      * Recursively fill one element of the partition array per call,
      * starting at index.  If partition is completely and correctly
      * filled, then a copy of partition is appended to solutions.
      */
    function fill(partition, sum, maxElement, index) {
        if (index >= nSlots) {
            // partition.slice(0) makes a copy -- see (3) in the comment below.
            if (sum == 0) solutions.push(partition.slice(0));
            return;
        }
        if (sum > nSlots * maxElement) {            // Optional optimization
            return;
        }

        for (var n = Math.min(sum, maxElement); n >= 0; n--) {
            // Note: we are doing mutation with recursion, which has the
            // danger of side-effects.  However, this use is safe because:
            // 1. The recursion is depth-first
            // 2. Nested calls will only affect elements after startIndex
            // 3. We eventually make a copy of each good solution
            partition[index] = n;
            fill(partition, sum - n, n, index + 1);
        }
    }

    fill(new Array(nSlots), sum, maxElement || sum, 0);
    return solutions;
}