Finding all possibilities between 4 percentages

Question

I'd like to find a way to combine in an array all possiblities between four percentages.

Results wanted :

possibilities = [[100,0,0,0],[99,1,0,0],[99,0,1,0],...,[0,0,1,99],[0,0,0,100]]

I'm using this function but it's very slow and doesn't seem to generate all possibilities.

combinePossibilities : function(a, min, max) {
    var deferred = $q.defer();
    function toObject(arr) {
        var rv = {};
        for (var i = 0; i < arr.length; ++i){
            rv['fund'+i] = arr[i];
        }
        return rv;
     }
     var fn = function(n, src, got, all) {
       if (n === 0) {
           if (got.length > 0) {
                var total = 0;
                angular.forEach(got, function(value){
                    total += value; //GET TOTAL OF THE COMBINATION
                });
                if(total === 100){
                    all.push(toObject(got));
                }
            }
            return;
         }
         for (var j = 0; j < src.length; j++) {
             fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
         }
         return;
     };
     var all = [];
     for (var i = min; i <= max; i++) {
        console.log(a);
        fn(i, a, [], all);
     }
     deferred.resolve(all);
     return deferred.promise;
}

I found this function here Find all possible subset combos in an array? and modified it to only take in my array results equal to 100%.

Any clue ?

Thank you.

What do you mean by all possibilities? Like `[0, 0, 0, 0]` to `[0, 0, 0, 100]` to `[0, 0, 1, 0]` ultimately to `[100, 100, 100, 100]`? — Ivar, Mar 01 '16 at 15:53
Define you problem more clearly. What's the input and what's the expected output? — Matt Burland, Mar 01 '16 at 15:54
@MattBurland, I'd like an array of arrays with all possiblities equal to 100. results = [[100,0,0,0],[99,1,0,0],...,[95,2,1,2],...,[25,25,25,25]...,[0,0,0,100]]. Hope I'm clear enough. — Matt Walterspieler, Mar 01 '16 at 15:56
var anArray = { ofArray { "allPossibilities" : 100 } } There you go, anArray ofArray with allPossibilities equal to 100 — Jorel Amthor, Mar 01 '16 at 16:00
Why so many arrays? You want all permutations of 4 whole numbers that sum to 100? — ryanyuyu, Mar 01 '16 at 16:03
@Ivar Yes except when the addition of the for value of the array > 100 — Matt Walterspieler, Mar 01 '16 at 16:03

Nina Scholz · Accepted Answer · 2016-03-02T16:56:07.667

This proposal is a functional recursive function, which takes sum and length. It returns an array with arrays of the combined values from the sum to zero.

function combine(sum, length, part) {
    var result = [],
        i = sum;

    part = part || [];
    if (length === 1) {
        return [part.concat(sum)];
    }
    if (length === 0) {
        return [part];
    }
    do {
        result = result.concat(combine(sum - i, length - 1, part.concat(i)));
    } while (i--);
    return result;
}

How it works:

It starts with the given sum and length and an empty result set, as well as an iterator variable i with the value of sum.

If part is not given, then an empty array is assigned.

Now follows some checks for the (leftover) length and their special treatment, if it is

1: This is last iteration and the sum is left, only. Then return the partial result part concatenated by sum in an array.

0: No more iteration, then return the partial result part in an array.

If the length is neither 1 nor 0, then interate over the sum to zero.

The call of combine takes the reduced sum, the decremented length and the partial result part with the value of i.

The result of the call of combine() is concatenated to the result set.

Example for combine(5, 3):
length: 21
[
    [5, 0, 0],
    [4, 1, 0],
    [4, 0, 1],
    [3, 2, 0],
    [3, 1, 1],
    [3, 0, 2],
    [2, 3, 0],
    [2, 2, 1],
    [2, 1, 2],
    [2, 0, 3],
    [1, 4, 0],
    [1, 3, 1],
    [1, 2, 2],
    [1, 1, 3],
    [1, 0, 4],
    [0, 5, 0],
    [0, 4, 1],
    [0, 3, 2],
    [0, 2, 3],
    [0, 1, 4],
    [0, 0, 5]
]

Working code with two examples:

combine(5, 3)
combine(10, 4)

function combine(sum, length, part) {
    var result = [],
        i = sum;

    part = part || [];
    if (length === 1) {
        return [part.concat(sum)];

    }
    if (length === 0) {
        return [part];
    }
    do {
        result = result.concat(combine(sum - i, length - 1, part.concat(i)));
    } while (i--);
    return result;
}

function print(array) {
    document.write('<pre>length: ' + array.length + '\n' + JSON.stringify(array, 0, 4) + '</pre>');
}

print(combine(5, 3));
print(combine(10, 4));

This is exactly what i needed. Thank you very much @NinaScholz ! 176850 possibilities, that's quite a lot. — Matt Walterspieler, Mar 01 '16 at 16:29

Finding all possibilities between 4 percentages

1 Answers1