Un algoritmo per generare sottoinsiemi di un insieme che soddisfa le condizioni totalmente certe

Question

Supponiamo che io sono dato una lista ordinata di elementi e voglio generare tutti i sottoinsiemi soddisfare alcune condizioni, in modo che se un dato insieme non soddisfa la condizione, quindi un sottoinsieme più grande sarà, inoltre, non soddisfarla, e tutti i set di uno elemento non soddisfarlo.

Per esempio, data una lista di tutti i numeri interi positivi di dimensioni inferiori a 100, determinare sottoinsiemi la cui somma è minore di 130: (100,29) (0,1,40), (0), ecc ...

Come posso farlo (preferibilmente in Python)?

Grazie! :)

Answer 1

È possibile generare tutti i sottoinsiemi utilizzando un tecnica branch-and-bound : è possibile generare tutti i sottoinsiemi in maniera incrementale (generando sovrainsieme di sottoinsiemi già determinati), utilizzando come condizione prune "non esplorare questo ramo dell'albero se la radice non satify il vincolo".

Se si vuole essere generico per quanto riguarda il vincolo, penso che questa sia la migliore strategia.

Assicurati di scrivere in modo corretto il codice che genera i sottoinsiemi, altrimenti si genera molte volte gli stessi sottoinsiemi: al fine di evitare Memoizzazione, che può richiedere molto tempo a causa di mappare le ricerche e introdurre overhead di memoria, è possibile generare i sottoinsiemi in questo modo:

GetAllSubsets(List objects) {
    List generated = {};
    GetAllSubsets(generated, [], objects);
    return generated;
}

GetAllSubsets(List subsetGenerated, List objectFixed, List objectsToFix) {
    GetAllSubsets(subsetGenerated, objectFixed, objectsToFix.sublist(1, objectsToFix.length());
    if (satisfy(toCheck = objectsFixed.add(objectsToFix.get(0)))) {
        subsetGenerated.add(toCheck);
        GetAllSubsets(subsetGenerated, toCheck, objectsToFix.sublist(1, objectsToFix.length());
    }
}

Infatti, i sottoinsiemi aggiunto dalla prima chiamata di GetAllSubsets non ha il primo elemento di objectsToFix, dove i sottoinsiemi aggiunto dalla seconda chiamata (se la condizione di potatura non viene violata) hanno tale elemento, così l'intersezione delle due serie di sottoinsiemi generati è vuota.

Answer 2

Si potrebbe costruire il vostro set ricorsivamente, a partire l'insieme vuoto e il tentativo di aggiungere ulteriori elementi, rinunciando a una linea ricorsiva di esecuzione, se uno dei sottoinsiemi (e quindi tutti i suoi superset) non riesce a soddisfare la condizione. Ecco alcuni pseudocodice, ipotizzando un insieme S la cui condizione soddisfacente sottoinsiemi che si desidera elencare. Per comodità, si supponga che gli elementi di S possono essere indicizzati come x (0), x (1), x (2), ...

EnumerateQualifyingSets(Set T)
{
    foreach (x in S with an index larger than the index of any element in T)
    {
            U = T union {x}

            if (U satisfies condition)
            {
                print U
                EnumerateQualifyingSets(U)
            }
    }
}

La prima chiamata sarebbe con T come l'insieme vuoto. Poi, tutti i sottoinsiemi di S che soddisfa le condizioni sarebbero state stampate. Questa strategia si basa essenzialmente sul fatto che un sottoinsieme di S che non soddisfa la condizione non può essere contenuto in quello che fa.

Answer 3

Ci sono certamente modi per farlo, ma se non è possibile vincolare la condizione in qualche modo, sta andando a prendere O (2 ^ n) passi. Se si considera, ad esempio, una condizione su 1-100 in cui sarebbero stati selezionati tutti i sottoinsiemi (ad esempio, <Σ i per i in 1- n ), allora si finirebbe per enumerare tutti i sottoinsiemi.

Si potrebbe essere guardando

for i in the powerset of {1-n}
    if cond(i)
       note that set

È possibile ottenere il Powerset del set con la semplice generazione di tutti i numeri binari da 0 a s n -1, e ho elemento scegliendo per il sottoinsieme quando il bit i è 1.

Answer 4

Ho fatto qualcosa di simile per un algoritmo di generazione di orario delle lezioni. La nostra classe programma aveva 2 elementi -. Un elenco di corsi aggiunti al programma, e un elenco dei corsi disponibili per aggiungere

Pseudocodice:

queue.add(new schedule(null, available_courses))
while( queue is not empty )
    sched = queue.next()
    foreach class in sched.available_courses
        temp_sched = sched.copy()
        temp_sched.add(class)
        if(temp_sched.is_valid())
            results.add(temp_sched)
            queue.add(temp_sched)

L'idea è di iniziare con un programma vuoto e l'elenco delle classi disponibili, e per cercare l'albero di programmi validi (significato valido si adatta ai requisiti indicati dall'utente, non ha conflitti di tempo, ecc). Se un programma non è valido, viene buttato via - non possiamo fare un programma valido valido con l'aggiunta di classi (vale a dire, la potatura dell'albero)

.

Dovrebbe essere abbastanza facile da modificare questo per lavorare con il vostro problema.

Answer 5

Ecco un esempio concreto di risposta di akappa, utilizzando una funzione ricorsiva per generare i sottoinsiemi:

def restofsubsets(goodsubset, remainingels, condition):
    answers = []
    for j in range(len(remainingels)):
        nextsubset = goodsubset + remainingels[j:j+1]
        if condition(nextsubset):
            answers.append(nextsubset)
            answers += restofsubsets(nextsubset, remainingels[j+1:], condition)
    return answers

 #runs slowly
 easieranswer = restofsubsets([], range(101), lambda l:sum(l)<40)

 #runs much faster due to eliminating big numbers first
 fasteranswer = restofsubsets([], range(100,-1,-1), lambda l:sum(l)<40)

 #runs extremely slow even with big-numbers-first strategy
 finalanswer = restofsubsets([], range(100,-1,-1), lambda l:sum(l)<130)

Answer 6

Credo che nel peggiore dei casi, si devono ancora produrre tutti i sottoinsiemi e calcolare la somma di ogni set per determinare se si tratta di qualificare o meno. Asintoticamente, è il costo di sottoinsiemi generano procedura.

Di seguito è il metodo ho implementato in javascript per la stessa idea.

//this is to generate an array to test
var numbers = (function(start, end){
    var result = [],
        i =  start; 
    for(; i <= end; i++){
        result.push(i);
    }
    return result; 
})(1, 12);

//this is the qualifying function to determine if the generated array is qualified
var fn = (function(maxSum){
    return function(set){
        var sum = 0;
        for(var i = 0 ; i< set.length; i++){
            sum += set[i];
            if( sum > maxSum ){
                return false;
            }
        }
        return true;
    }
})(30);

//main function
(function(input, qualifyingFn){
    var result, mask, total = Math.pow(2, input.length);
    for(mask = 0; mask < total; mask++){

        result = [];
        sum = 0;

        i = input.length - 1; 
        do{
            if( (mask & (1 << i)) !== 0){
                result.push(input[i]);
                sum += input[i];
                if( sum > 30 ){
                    break;
                }
            }
        }while(i--);
        if( qualifyingFn(result) ){
            console.log(JSON.stringify(result));
        }
    }

})(numbers, fn);