Ricerca di liste tuple uniche di opzioni

Question

Ricerca di liste tuple uniche di opzioni

#1 da (2 voti)
#2 da (0 voti)

4

Sto avendo un po 'di difficoltà a trovare una soluzione al seguente problema. Ho bisogno di trovare tuple di (a-c, 0-2) tali che se faccio una scelta con una lettera e un tasto non riesco a selezionarlo di nuovo. Esempio:

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

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

Esempi di scelte valide che portano a set incompleti sono i seguenti: 1. selezionare (a, 0) e 2. (b, 1). Quindi non ho opzioni valide per c perché (c, 0) e (c, 1) non sono più possibili.

algorithms

posta Krolique 09.05.2016 - 15:25

fonte

2 risposte

Leggi altre domande sui tag algorithms

Guida all'architettura del livello dati Come attribuire l'attribuzione per lavori derivati sotto il MIT, quando il lavoro è un porto?

score 2 · Answer 1

Questo è un problema noto chiamato Problema di assegnazione .

L'obiettivo è quello di accoppiare elementi da 2 set in modo tale da minimizzare il costo totale delle coppie.

Ad esempio quando si desidera assegnare attività ai lavoratori, in cui ogni attività può essere eseguita da un solo lavoratore e ciascun lavoratore può svolgere solo un'attività. Ogni coppia di operatori ha un costo e tu vuoi ridurre al minimo il costo totale.

Molto di più su Wikipedia. Per piccoli set sarà sufficiente un semplice backtracking. Per set di grandi dimensioni, un algoritmo per trovare la soluzione ottimale è l' algoritmo ungherese .

Nel tuo caso, devi mettere un costo di 0 su ogni coppia consentita e un costo di 1 su ogni coppia proibita. L'algoritmo restituirà l'associazione che riduce al minimo il costo totale, ovvero massimizza il numero di coppie consentite.

Un altro metodo è convertirlo in un problema di flusso massimo. Può essere risolto con il metodo Ford-Fulkerson. È stato discusso qui:
link

score 0 · Answer 2

Ecco una soluzione di backtrack ingenuo, in JavaScript:

link

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());

che produce:

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

'HTH,