# Finding unique tuples list of options

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.

• Do you have any further constraints on this? The naive brute force approach of "try every permutation" will eventually succeed Commented 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. Commented May 9, 2016 at 15:15
• 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 Commented May 9, 2016 at 15:26
• This seems like a reduced subset of sudoku; a constraint-based solver would probably help Commented Jul 11, 2016 at 15:32

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

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,