¿Cómo puedo encontrar todos los subconjuntos de un conjunto, con exactamente n elementos?

Estoy escribiendo un progtwig en Python, y me di cuenta de que un problema que necesito resolver me requiere, dado un conjunto S con n elementos (| S | = n), para probar una función en todos los subconjuntos posibles de un cierto orden m ( es decir, con m número de elementos). Para usar la respuesta para producir una solución parcial, y luego intente nuevamente con el siguiente orden m = m + 1, hasta que m = n.

Estoy en camino de escribir una solución del formulario:

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

Pero conociendo Python, esperaba que una solución ya estuviera allí.

Cuál es la mejor manera de lograr esto?

itertools.combinations es tu amigo si tienes Python 2.6 o superior. De lo contrario, verifique el enlace para una implementación de una función equivalente.

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

S: El conjunto para el que desea buscar subconjuntos.
m: el número de elementos en el subconjunto

Uso de la función canónica para obtener el conjunto de potencias de la página de recetas de itertools :

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

Utilizado como

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

asigna a conjuntos si quieres, así puedes usar unión, intersección, 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]) 

Aquí hay una sola línea que le da todos los subconjuntos de los enteros [0..n], no solo los subconjuntos de una longitud dada:

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

así que por ejemplo

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

Aquí hay algunos pseudocódigo: puede cortar las mismas llamadas recursivas almacenando los valores de cada llamada a medida que avanza y antes de la verificación recursiva de llamadas si el valor de la llamada ya está presente.

El siguiente algoritmo tendrá todos los subconjuntos excluyendo el conjunto vacío.

 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 

Entonces, por ejemplo, si s = "123" entonces la salida es:

 1 2 3 12 13 23 123 

Sin usar itertools :

En Python 3, puede usar el yield from para agregar un método de generador de subconjuntos a la clase de set buit-in:

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

Por ejemplo, el siguiente fragmento de código funciona como se esperaba:

 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 

$ python -c "import itertools; a=[2,3,5,7,11]; print sum([list(itertools.combinations(a, i)) for i in range(len(a)+1)], [])" [(), (2,), (3,), (5,), (7,), (11,), (2, 3), (2, 5), (2, 7), (2, 11), (3, 5), (3, 7), (3, 11), (5, 7), (5, 11), (7, 11), (2, 3, 5), (2, 3, 7), (2, 3, 11), (2, 5, 7), (2, 5, 11), (2, 7, 11), (3, 5, 7), (3, 5, 11), (3, 7, 11), (5, 7, 11), (2, 3, 5, 7), (2, 3, 5, 11), (2, 3, 7, 11), (2, 5, 7, 11), (3, 5, 7, 11), (2, 3, 5, 7, 11)]

Aquí hay una forma clara con un algoritmo fácil de entender.

 import copy nums = [2,3,4,5] subsets = [[]] for n in nums: prev = copy.deepcopy(subsets) [k.append(n) for k in subsets] subsets.extend(prev) print(subsets) print(len(subsets)) # [[2, 3, 4, 5], [3, 4, 5], [2, 4, 5], [4, 5], [2, 3, 5], [3, 5], [2, 5], [5], # [2, 3, 4], [3, 4], [2, 4], [4], [2, 3], [3], [2], []] # 16 (2^len(nums))