Wie finde ich alle Untermengen eines Satzes mit genau n Elementen?

Question

Ich bin ein Programm in Python zu schreiben, und ich erkannte, dass ein Problem, das ich lösen muss verlangt von mir, da ein Satz S mit n Elementen (| S | = n), eine Funktion auf alle möglichen Teilmengen einer bestimmten Reihenfolge zu testen m (dh mit m Anzahl der Elemente). Um die Antwort zu verwenden, um eine Teillösung zu erzeugen, und versuchen Sie es erneut mit der nächsten Ordnung m = m + 1, bis m = n.

Ich bin auf dem Weg, um eine Lösung der Form zu schreiben:

def findsubsets(S, m): 
    subsets = set([]) 
    ... 
    return subsets 

Aber Python zu wissen, erwartete ich eine Lösung schon da zu sein.

Was ist der beste Weg, dies zu erreichen?

Answer 1

itertools.combinations ist dein Freund, wenn Sie Python 2.6 oder höher haben. Andernfalls prüfen Sie den Link auf eine Implementierung einer äquivalenten Funktion.

import itertools 
def findsubsets(S,m): 
    return set(itertools.combinations(S, m)) 

Answer 2

Hier ist ein Einzeiler, die Sie alle Untergruppen der ganzen Zahlen [0..n], nicht nur die Teilmengen einer gegebenen Länge ergibt:

from itertools import combinations, chain 
allsubsets = lambda n: list(chain(*[combinations(range(n), ni) for ni in range(n+1)])) 

so z.B.

>> allsubsets(3) 
[(), (0,), (1,), (2,), (0, 1), (0, 2), (1, 2), (0, 1, 2)] 

Answer 3

Hier einige Pseudo-Code - Sie gleichen rekursiven Aufrufen von Speichern der Werte für jeden Anruf schneiden können, wie Sie die Überprüfung rekursiven Aufruf gehen und vor, wenn der Anruf Wert bereits vorhanden ist.

Der folgende Algorithmus wird alle Untergruppen mit Ausnahme der leeren Menge.

list * subsets(string s, list * v) { 

    if(s.length() == 1) { 
     list.add(s);  
     return v; 
    } 
    else 
    { 
     list * temp = subsets(s[1 to length-1], v); 
     int length = temp->size(); 

     for(int i=0;i<length;i++) { 
      temp.add(s[0]+temp[i]); 
     } 

     list.add(s[0]); 
     return temp; 
    } 
} 

So zum Beispiel, wenn s = "123" dann ausgegeben wird:

1 
2 
3 
12 
13 
23 
123 

Answer 4

die kanonische Funktion Mit den powerset von der the itertools recipe Seite zu erhalten:

from itertools import chain, combinations 

def powerset(iterable): 
    """ 
    powerset([1,2,3]) -->() (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3) 
    """ 
    xs = list(iterable) 
    # note we return an iterator rather than a list 
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1)) 

Gebraucht wie :

>>> list(powerset("abc")) 
[(), ('a',), ('b',), ('c',), ('a', 'b'), ('a', 'c'), ('b', 'c'), ('a', 'b', 'c')] 

>>> list(powerset(set([1,2,3]))) 
[(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] 

Karte setzt, wenn Sie wollen, so können Sie Vereinigung verwenden, Kreuzung, etc ...:

>>> map(set, powerset(set([1,2,3]))) 
[set([]), set([1]), set([2]), set([3]), set([1, 2]), set([1, 3]), set([2, 3]), set([1, 2, 3])] 

>>> reduce(lambda x,y: x.union(y), map(set, powerset(set([1,2,3])))) 
set([1, 2, 3]) 

Answer 5

Ohne Verwendung itertools:

In Python 3 Sie können yield from verwenden, um eine Teilmenge Generator Methode hinzufügen buit-in set Klasse:

class SetWithSubset(set): 
    def subsets(self): 
     s1 = [] 
     s2 = list(self) 

     def recfunc(i=0):    
      if i == len(s2): 
       yield frozenset(s1) 
      else:     
       yield from recfunc(i + 1) 
       s1.append(s2[ i ]) 
       yield from recfunc(i + 1) 
       s1.pop() 

     yield from recfunc() 

zum Beispiel unter Schnipsel wie erwartet funktioniert:

x = SetWithSubset({1,2,3,5,6}) 
{2,3} in x.subsets()   # True 
set() in x.subsets()   # True 
x in x.subsets()    # True 
x|{7} in x.subsets()   # False 
set([5,3]) in x.subsets()  # True - better alternative: set([5,3]) < x 
len(x.subsets())    # 32