Adrien Aggery Adrien Aggery - 2 months ago 16
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.

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]]