potencia - operaciones set python

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

Question

Estoy escribiendo un programa en Python, y me di cuenta de que un problema que necesito resolver me exige, dado un conjunto S con n elementos (| S | = n), probar una función en todos los subconjuntos posibles de 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 m = n.

Estoy en camino de escribir una solución de la forma:

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

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

Cuál es la mejor manera de lograr esto?

Answer 1

Aquí hay un pseudocódigo: puede cortar las mismas llamadas recursivas almacenando los valores de cada llamada sobre la marcha y antes de la comprobació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<length;i++) {
            temp.add(s[0]+temp[i]);
        }

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

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

1
2
3
12
13
23
123

Answer 2

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

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

Answer 3

Usando la función canónica para obtener el powerset de powerset desde la página de recetas 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))

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

mapea a los conjuntos si quieres para que puedas 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])

Answer 4

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: la cantidad de elementos en el subconjunto

Answer 5

Sin usar itertools :

En Python 3 puede usar 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, a continuación, el fragmento funciona como se espera:

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