Ein Algorithmus zum Erzeugung Teilmenge einer Menge erfüllt certian Bedingungen

Question

Angenommen, ich eine sortierte Liste von Elementen ist gegeben und ich möchte alle Untergruppen erzeugen, eine Bedingung erfüllt, so dass, wenn eine bestimmte Gruppe die Bedingung nicht erfüllt, dann eine größere Teilmenge wird auch sie nicht erfüllen, und alle Sätze von einem Element genügt es.

Zum Beispiel gegeben wird eine Liste aller positiven ganzen Zahlen kleiner als 100, Teilmengen bestimmen, deren Summe kleiner als 130: (100,29) (0,1,40), (0), etc ...

Wie kann ich das tun (vorzugsweise in Python)?

Danke! :)

Answer 1

Sie können generieren alle Teilmengen ein Branch-and-bound Technik: Sie können erzeugen alle Teilmengen in einer inkrementellen Art und Weise (Superset der Subsets bereits bestimmt erzeugt), wobei als prune Bedingung „erforscht nicht diesen Zweig des Baumes, wenn die Wurzel die Einschränkung nicht satify“.

Wenn Sie generische bezüglich der Einschränkung sein wollen, ich denke, das ist die beste Strategie.

Seien Sie sicher, dass Sie den Code in korrekter Weise zu schreiben, die die Teilmengen erzeugt, sonst hat man viel Zeit die gleichen Teilmengen erzeugen: um memoization zu vermeiden, die zeitaufwendig fällig kann Lookups Karte und Speicher-Overhead einführen, können Sie erzeugt die Teilmengen in dieser Weise:

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

Tatsächlich addiert sich die Teilmengen durch den ersten Aufruf von GetAllSubsets hat nicht das erste Element des objectsToFix, wo die Teilmengen durch den zweiten Anruf hinzugefügt (wenn das Beschneiden Bedingung nicht verletzt wird), das Element haben, so dass der Schnittpunkt der die beiden Sätze von Teilmengen erzeugen leer ist.

Answer 2

Sie können Ihre Sets rekursiv, beginnend mit dem leeren Satz konstruieren und zu versuchen, mehr Elemente hinzuzufügen, auf einer rekursiven Linie der Ausführung Aufgeben, wenn eine der Untergruppen (und damit alle seine Obermengen) nicht um die Bedingung zu erfüllen. Hier einige Pseudo-Code, einen Satz S, deren Zustand befriedigenden Teilmengen vorausgesetzt, Sie möchten aufzulisten. Der Einfachheit halber wird angenommen, dass die Elemente von S als x indiziert werden können (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)
            }
    }
}

Der erste Anruf mit T als leere Menge sein würde. Dann werden alle Untergruppen von S die Bedingung erfüllen würden gedruckt. Diese Strategie beruht entscheidend auf der Tatsache, dass eine Teilmenge von S, die nicht die Bedingung erfüllen, kann nicht in einem enthalten sein, der Fall ist.

Answer 3

Es gibt sicherlich Möglichkeiten, es zu tun, aber wenn man den Zustand irgendwie einschränken kann, es wird O (2 ^ n), Maßnahmen zu ergreifen. Wenn man bedenkt, zum Beispiel eine Bedingung auf 1-100, wo alle Untergruppen ausgewählt werden würden (zB Σ < i für i in 1- n ), dann würden Sie alle Untergruppen am Ende aufzählt.

Sie würden Blick auf

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

Sie können die Powerset der Set erhalten, indem einfach alle binären Zahlen von 0 bis s Erzeugung von n -1 und wähle Element i für die Teilmenge, wenn das Bit i 1 ist.

Answer 4

Ich habe etwas ähnliches für eine Klasse Zeitplan erzeugenden Algorithmus. Unser Zeitplan Klasse hatte zwei Elemente -. Eine Liste der Kurse, um den Zeitplan hinzugefügt, und eine Liste der Kurse zur Verfügung hinzuzufügen

Pseudocode:

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)

Die Idee ist, mit einem leeren Zeitplan und der Liste der verfügbaren Klassen zu starten, und den Baum für gültige Zeitplan suchen (gültige Bedeutung der Anforderungen paßt durch den Benutzer gegeben, keine Zeit Konflikte, etc). Wenn ein Zeitplan ungültig ist, wird es weggeworfen - wir nicht einen ungültigen Zeitplan gültig durch Hinzufügen von Klassen machen (dh Beschneiden des Baumes)

.

Es sollte ziemlich einfach sein, dies zu ändern, mit dem Problem zu arbeiten.

Answer 5

Hier ist ein konkretes Beispiel für akappa Antwort, eine rekursive Funktion mit den Untergruppen zu generieren:

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

ich im schlimmsten Fall denke, haben Sie immer noch alle Untergruppen zu erzeugen und die Summe jeden Satz zu berechnen, um zu bestimmen, ob es qualifizieren oder nicht. Asymptotisch ist es die Kosten für die Untergruppen zu erzeugen Verfahren.

Im Folgenden ist die Methode, die ich in Javascript für die gleiche Idee umgesetzt.

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