Adrien Aggery - 4 months ago 22

Javascript Question

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.

Answer Source

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);
}([[]])); // start with empty array []
}
const result = createVector(2);
console.log(result);
// [[0,1], [0.1,0.9], [0.2,0.8], [0.3,0.7], [0.4,0.6], [0.5,0.5], [0.6,0.4], [0.7,0.3], [0.8,0.2], [0.9,0.1], [1,0]]
```