2009-06-01 23 views
1

Angenommen, ich habe eine sortierte Liste von Elementen erhalten und möchte alle Teilmengen erzeugen, die eine Bedingung erfüllen, so dass, wenn eine gegebene Menge die Bedingung nicht erfüllt, dann eine größere Teilmenge wird es auch nicht befriedigen, und alle Sätze eines Elements befriedigen es.Ein Algorithmus zum Generieren von Teilmengen einer Menge, die certian Bedingungen erfüllt

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

Wie kann ich das (vorzugsweise in Python) tun?

Danke! :)

Antwort

4

Sie können alle Teilmengen mit einer Branch-and-bound-Technik generieren: Sie können alle Teilmengen inkrementell generieren (indem Sie eine Obermenge von bereits bestimmten Teilmengen generieren), indem Sie diese Verzweigung "nicht untersuchen" der Baum, wenn die Wurzel die Beschränkung nicht erfüllt ".

Wenn Sie bezüglich der Beschränkung generisch sein wollen, denke ich, dass dies die beste Strategie ist.

Achten Sie darauf, den Code korrekt zu schreiben, der die Subsets erzeugt, sonst erzeugen Sie viele Zeit die gleichen Subsets: um Memoization zu vermeiden, die aufgrund von Map-Lookups zeitraubend sein kann und Speicher Overhead einführt die Teilmengen in dieser Weise erzeugen:

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

in der Tat, die Teilmengen von dem ersten Aufruf von GetAllSubsets hinzugefügt nicht das erste Element des objectsToFix aufweisen, wobei die Teilmengen durch den zweiten Anruf (wenn die Bedingung hinzugefügt pruning ist nicht verletzt) ​​haben dieses Element, so ist der Schnittpunkt der beiden Gruppen von Untergruppen erzeugt leer.

1

Es gibt sicherlich Möglichkeiten, es zu tun, aber wenn Sie die Bedingung irgendwie beschränken können, wird es O (2^n) Schritte dauern. 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 aufzählt enden.

Sie bei

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

Sie können die Powerset der durch einfaches gesetzt bekommen alle binären Zahlen von 0 bis s Erzeugung n -1 und das Element der Wahl i für die Teilmenge, wenn das Bit i ist 1.

+0

Es macht keinen Sinn, über alle Mengen zu iterieren; Wenn die Summe von (x, y) größer als 100 ist, muss keine verbleibende Teilmenge mit x, y überprüft werden! (Zum Beispiel: (40,79,50) hat eine Summe von mehr als 100, es gibt also keine Notwendigkeit zu überprüfen (40,79,50,1), (40,79,50,66,1) etc ... – ooboo

+0

Aber das ist nur ein Beispiel der möglichen Bedingungen.Was ist, wenn die Bedingung ist, dass die Summe weniger als 5050 ist (was die Summe von 1 bis 100 ist)? Dann werden * alle * Untergruppen die Bedingung erfüllen. –

+0

Aber die Tatsache, dass Im schlimmsten Fall erhalten Sie eine O (2^n) Zeit Komplexität sollte uns nicht daran hindern, eine gute Heuristik zu suchen, um das Problem zu lösen – akappa

2

Sie könnten Ihre Sets rekursiv konstruieren, indem Sie mit dem leeren Set beginnen und versuchen, weitere Elemente hinzuzufügen, und auf eine rekursive Ausführungszeile verzichten, wenn eines der Subsets (und damit alle Supersets) die Bedingung nicht erfüllt. Hier ist ein Pseudocode, der eine Menge S annimmt, deren bedingungserfüllenden Teilmengen Sie auflisten möchten. Der Einfachheit halber sei angenommen, daß die Elemente als S x indexiert 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 würden alle Untermengen von S, die der Bedingung entsprechen, gedruckt. Diese Strategie beruht entscheidend auf der Tatsache, dass eine Teilmenge von S, die die Bedingung nicht erfüllt, nicht in einer enthalten sein kann, die dies tut.

+0

Dieser Pseudocode erzeugt viele Zeit die gleichen Teilmengen: diese zusätzliche Komplexität könnte der Optimierung des Beschneidens widersprechen Sie sollten Memoization hinzufügen, um das Problem zu beheben – akappa

+0

oops. Sie haben Recht Ich werde nach wo korrigieren rk. Vielen Dank. – PeterAllenWebb

+0

ok. sollte jetzt gut sein. – PeterAllenWebb

1

Ich habe etwas Ähnliches für einen Klassenplan-Generierungsalgorithmus getan.Unsere Stundenplanklasse bestand aus 2 Elementen - einer Liste mit Kursen, die dem Stundenplan hinzugefügt wurden, und einer Liste mit Kursen, die hinzugefügt werden konnten.

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 durch den Benutzer gegeben paßt, doesn habe keine Zeitkonflikte, etc). Wenn ein Zeitplan ungültig ist, wird er verworfen - wir können einen ungültigen Zeitplan nicht durch Hinzufügen von Klassen gültig machen (z. B. die Baumstruktur beschneiden).

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

1

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) 
0

ich im schlimmsten Fall denke, haben Sie immer alle Untergruppen zu generieren und die Summe jeden Satz berechnen Bestimmen Sie, ob es qualifiziert ist oder nicht. Asymptotisch sind es die Kosten für das Erzeugen von Teilmengen.

Folgendes ist die Methode, die ich in Javascript für die gleiche Idee implementiert.

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