# What is the most elegant algorithm to find the best combination?

I have a function, let's call it `test`. This function has arguments, but I don't know how many arguments it has. It returns always a Boolean.

I have another function, let's call it `calibrator`. This `calibrator` function gets the possible `alternatives` of the `test` arguments in a 2d array. Every argument can have many alternatives. I need to call the `test` function on argument `combination`s until I find something that returns `true`. The `calibrator` function should return that `combination` or the `default` if it does not find a proper `combination`.

What is the best algorithm for the `calibrator`?

I have come up something like this so far, but I am stuck:

``````function calibrator(test, alternatives, default){
var combination = [];

// certainly not the way I need to use for iteration
// this does not find every combination
for (var argument in alternatives)
for (var alternative in alternatives[argument])
combination[argument] = alternatives[argument][alternative];

// returns the combination when the test succeeds, so exists from the loop
// this should run by every possible combination
if (test(combination))
return combination;

// returns default if no proper combination
return default;
}
``````

I need to iterate through every combination, but I don't know how to do that. :S

edit:

I ended up with the following code based on the accepted answer.

``````var eachCombination = function (alternativesByDimension, callback, combination){
if (!combination)
combination = [];
if (combination.length < alternativesByDimension.length) {
var alternatives = alternativesByDimension[combination.length];
for (var index in alternatives) {
combination[combination.length] = alternatives[index];
eachCombination(alternativesByDimension, callback, combination);
--combination.length;
}
}
else
callback(combination);
};

function calibrator(alternativesByDimension, test) {
try {
eachCombination(alternativesByDimension, function (combination){
if (test.apply(null, combination))
throw combination;
});
} catch (combination){
return combination;
}
return alternativesByDimension.map(function (alternatives){
return alternatives[0];
});
}

console.log(calibrator([
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
], function(x, y, z) {
return x > 2 && y > 5;
}));
``````

I realized meanwhile that the problem is somewhat similar to iterating tree leaves and so is the solution as well. I acknowledge it's more elegant with generators, but I needed something which works with MSIE too. :-)

You can add another function `getCombinations` that generates all the combinations of items in alternatives. `index` is the index of we've created all the combinations up to, and `combination` the the array containing the current combination.

``````function* getCombinations(index, combination, alternatives) {
if (index == alternatives.length) {
yield combination;
} else {
for (var alternative of alternatives[index]) {
combination[index] = alternative;
yield* getCombinations(index + 1, combination, alternatives);
}
}
}

function calibrator(test, alternatives, defaultValue) {
for (var combination of getCombinations(0, [], alternatives)) {
if (test(combination)) {
return combination;
}
}

return defaultValue;
}

test = function([x, y, z]) { return x > 2 && y > 5; };
alternatives = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
defaultValue = [0, 0, 0];

console.log(calibrator(test, alternatives, defaultValue));
``````
• Nice, it works! I just have to translate this to old style javascript to support more browsers. Commented Aug 21, 2016 at 21:38
• Please reject the edit, I added almost the same code to my question... Commented Aug 21, 2016 at 23:36

Without knowing any better, and without any hint on what combination has the most probability to succeed, this sounds like you "just" need to implement the full set of permutation of all alternatives, test each one and return on success

``````for (i = 0; i < numAlternatives[0]; i++)
for (j = 0; j < numAlternatives [1]; j++)
for (k = 0; k < numAlternatives [2]; k++)
if (test (alternative [0, i],
alternative [1, j],
alternative [2, k]) == TRUE)
return new solutionSet (alternative [0, i],
alternative [1, j],
alternative [2, k]);
``````

And "elegance" can only come into the question as soon as you have some sort of idea what alternatives are more likely to succeed than others. You would want to sort the alternatives in decreasing probability in order to hit the more probable combinations first.

• Yes it is something similar, but your code works only by 3 arguments and I don't know how many arguments there will be, since this should be a general function instead of a concrete one. Commented Aug 21, 2016 at 17:43
• It's just showing the concept - instead of i, j, k use an array the size of your dimensions Commented Aug 21, 2016 at 18:01
• I think you misunderstood the question. I have to iterate through every alternative in order to find one which is passing the test. I don't know how many dimensions the alternatives will have. Sorting won't help, since I don't know (did not know) how to iterate through every combination without knowing the number of the dimensions. Using recursive functions is the key to do this. Another possible solution to use generators, but they follow the same logic. Commented Aug 21, 2016 at 22:25
• Recursion can only be an approach if you know (or at least have a rough idea) on the number of dimensions and permutations beforehand - Otherwise, it's simply suicide... Commented Aug 21, 2016 at 23:00