0

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 combinations 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. :-)

1

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. – inf3rno Aug 21 '16 at 21:38
  • Please reject the edit, I added almost the same code to my question... – inf3rno Aug 21 '16 at 23:36
-2

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. – inf3rno Aug 21 '16 at 17:43
  • It's just showing the concept - instead of i, j, k use an array the size of your dimensions – tofro Aug 21 '16 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. – inf3rno Aug 21 '16 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... – tofro Aug 21 '16 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.