Algorithms – What is the Most Elegant Algorithm to Find the Best Combination?

algorithms

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. 🙂

Best Answer

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));
Related Topic