Adrien Aggery - 1 year ago 55
Javascript Question

# Iterate throught options with a constrain on each possibility

I have a problem where I need to iterate through many possibilities programatically.

Let me give you an example as it'll be far more understandable.

I got a vector (or array for simplicity) say [0.4, 0.2, 0.3, 0.1] where every value is between 0 and 1, with a step of 0.1 and the sum of them has to be 1.

I also have function to which I pass this array and it returns me a number.

The goal is to try all the possible combination of the values into the array and keep the one where the function gives me the lowest number possible.

I tried to find a simple way to iterate throught the possible solutions but couldn't arrive to something I could code easily.

First, you'll need a function that calculate all possible permutations of your array.

Here it is (I took it from here):

function permutations(list) {
if (list.length <= 1) {
return list.slice();
}

var result = [];
var rest;
var current;
var permutationsRest;
var i, j;

for (i = 0; i < list.length; i++) {
rest = list.slice(); // make a copy of list
current = rest.splice(i, 1);
permutationsRest = permutations(rest);
for (j = 0; j < permutationsRest.length; j++) {
result.push(current.concat(permutationsRest[j]));
}
}

return result;
}

Next, make your function that return a number for a given array. For the sake of example, I made mine:

function calculate(array) {
var i;
var score = 0;
for (i = 0; i < array.length; i++) {
score = array[i] * (i + 1);
}
return score;
}

Then apply this function over all permutations, while storing the best result.

var permutations = permutations([0.4, 0.2, 0.3, 0.1]);
var score;
var bestScore = Number.MAX_VALUE; // as you stated that lower the score is, better it is, so MAX_VALUE would be the worst score possible
var bestPermutation;
var i;

for (i = 0; i < permutations.length; i++) {
score = calculate(permutations[i]);
if (score < bestScore) { // lower is best
bestScore = score;
bestPermutation = permutations[i];
}
}

console.log(bestScore);
console.log(bestPermutation);
// prints "[0.4, 0.2, 0.3, 0.1]"

To answer to your comment, the following function will create any possible permutation for given size, where sum would be equal to 1 and step to 0.1. I used ES6 to be more concise, tell me if you need old browser support.

Note that to avoid weird float values (like 0.7999999999999998), I use integers from 0 to 10, that I divide just before returning array of results.

function createVector(size) {
return (function recursive(permutations) {
if (permutations[0].length === size) {
// end of recursive, so map 0-10 values to 0.0-1.0
return permutations.filter(t => t.reduce((a, b) => a + b, 0) === 10)
.map(t => t.map(i => i / 10));
}

// calculate each permutation which sum <= 10
const newPermutations = [];
for (let i = 0; i <= 10; i++) {
permutations.filter(permutation => permutation.reduce((a, b) => a + b, i) <= 10)
.forEach(permutation => newPermutations.push([i].concat(permutation)));
}

return recursive(newPermutations);