4

I'm having a bit of hard time finding a solution to the following problem. I need to find tuples of (a-c, 0-2) such that if I make a choice with one letter and a key I can't select it again. Example:

input: {'a': [0, 1], 'b': [1, 2], 'c': [0, 1]}

output: [(a, 0), (b, 2), (c, 1)]

Example valid choices which lead to incomplete set is as follows: 1. select (a, 0) and 2. (b, 1). Then I have no valid options for c because (c, 0) and (c, 1) are no longer possible.

4
  • Do you have any further constraints on this? The naive brute force approach of "try every permutation" will eventually succeed
    – Caleth
    May 9, 2016 at 13:35
  • @Caleth I do not, I just thought there might be another way of solving than through exhaustion. For instance you can model this as a matrix and solve as a system of equations.
    – Krolique
    May 9, 2016 at 15:15
  • 2
    A potentially useful heuristic would be "least frequently occurring" i.e. 2 in your example has to associate with 'b'. That won't improve the worst case however
    – Caleth
    May 9, 2016 at 15:26
  • This seems like a reduced subset of sudoku; a constraint-based solver would probably help
    – Daenyth
    Jul 11, 2016 at 15:32

2 Answers 2

2

This is a well-known problem called the Assignment Problem.

The aim is to pair elements from 2 sets in such a way to minimize the total cost of the pairs.

For instance when you want to assign tasks to workers, where each task can be done only by one worker and each worker can do only one task. Each task-worker pair has a cost and you want to minimize the total cost.

Much more on Wikipedia. For small sets simple backtracking will be sufficient. For large sets, one algorithm to find the optimal solution is the Hungarian algorithm.

In your case, you need to put cost 0 on each allowed pair and a cost 1 on each forbidden pair. The algorithm will return the pairing that minimizes the total cost, that is, maximize the number of allowed pairs.

Another method is to convert it to a maximum flow problem. It can be solved with the Ford-Fulkerson method. It has been discussed here:
https://stackoverflow.com/questions/22747088/maximum-bipartite-matching-ford-fulkerson

0

Here's a naive backtracking solution, in JavaScript:

https://jsfiddle.net/YSharpLanguage/dbt1gwk5

function q317951(input, exclusions) {
    // quick'n dirty cloning helper:
    var clone = function (o) {
        var c = {};
        for (var k in o) {
            if (o.hasOwnProperty(k)) {
                c[k] = o[k];
            }
        }
        return c;
    };
    // make working copies of the input and exclusions
    // (for the recursive call below):
    var copy = clone(input);
    var exclude = [].slice.call(exclusions);
    var solution = null;
    var values = null;
    for (var key in copy) {
        if (copy.hasOwnProperty(key)) {
            // cache the current key's associated values:
            values = copy[key];
            // exclude the current key from the copy:
            // (required by the recursive call below)
            delete copy[key];
            for (var i = 0; i < values.length; i++) {
                var value = values[i];
                var partialSolution, obj;
                if (
                  (exclusions.indexOf(value) < 0) &&
                  ((partialSolution = q317951(copy, exclude.concat(value))) != null)
                ) {
                    // successful backtracking...
                    solution = (solution != null) ? solution : partialSolution;
                    // ... so, accumulate { key: value } with the solution:
                    obj = {};
                    obj[key] = value;
                    return solution.concat(obj);
                }
            }
        }
    }
    // succeed with an empty array if input is empty to begin with,
    // or else, return the solution, if any (non-null)
    return (values != null) ? solution : [];
}

console.log(q317951({ "a": [0, 1], "b": [1, 2], "c": [0, 1] }, [ ]).reverse());

which yields:

[ { "a": 0 }, { "b": 2 }, { "c" : 1 } ]

'HTH,

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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