Comment puis-je trouver tous les sous-ensembles d'un ensemble, avec exactement n éléments?

Je suis en train d'écrire un programme en Python, et j'ai réalisé qu'un problème j'ai besoin pour résoudre exige de moi, étant donné un ensemble S avec n éléments (|S|=n), pour tester une fonction sur tous les sous-ensembles possibles d'un certain ordre m (c'est à dire avec m nombre d'éléments). Pour utiliser la réponse à produire une solution partielle, et puis essayez à nouveau avec la commande suivante m=m+1, jusqu'à ce que m=n.

Je suis sur ma façon d'écrire une solution de la forme:

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

Mais sachant Python je m'attendais à une solution pour être déjà là.

Quelle est la meilleure façon d'accomplir cette?

scipy.misc.comb(S, m) donne le nombre de sous-ensembles que vous obtiendrez. Vous devriez vérifier avant de vous exécuter votre code comme le nombre de m-taille des sous-ensembles de S devient très grand, très rapide.
Littéralement eu le même problème, mis à code moi-même, et alors rendu compte qu'il doit exister une bibliothèque Python pour cela!

InformationsquelleAutor Pietro Speroni | 2008-12-17

python

121

itertools.combinaisons est votre ami si vous avez la version 2.6 de Python ou plus. Sinon, vérifiez le lien pour une mise en œuvre d'une fonction équivalente.
```
import itertools
def findsubsets(S,m):
    return set(itertools.combinations(S, m))
```
S: Le jeu pour lequel vous souhaitez trouver des sous-ensembles

m: Le nombre d'éléments dans le sous-ensemble
- je ne serais pas de retour ensemble, mais il suffit de retourner l'itérateur (ou simplement utiliser des combinaisons() sans la définition d'un findsubsets()...)
- Merci, je viens de testé et il fonctionne parfaitement.
- l'OP particulièrement demandé pour les ensembles. L'omission de l'ensemble en fonte permet de répétitions dans des ordres différents, par exemple: (1,2,3), (2,3,1), (3,1,2)...
- Je suis désolé, je ne comprends pas ce que tu veux dire. Êtes-vous confus avec cette permutations?
InformationsquelleAutor recursive

À l'aide de la fonction canonique pour obtenir le powerset de la le itertools recette page:

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

Utilisé comme:

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

carte de jeux si vous le souhaitez, vous pouvez utiliser de l'union, l'intersection, 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])

reformater pour la norme d'espacement (4 espaces)?

InformationsquelleAutor brice

22

Voici un one-liner qui vous donne tous les sous-ensembles des entiers [0..n], et pas seulement les sous-ensembles d'une longueur donnée:
```
from itertools import combinations, chain
allsubsets = lambda n: list(chain(*[combinations(range(n), ni) for ni in range(n+1)]))
```
si par exemple la
```
>> allsubsets(3)
[(), (0,), (1,), (2,), (0, 1), (0, 2), (1, 2), (0, 1, 2)]
```
- Utile formule, mais l'utilisation chain.from_iterable à la place de l'étoile-l'expansion peut être très long. Et quel est le point de réitérer les combinaisons dans une liste ([ ... ]), star-l'expansion, enchaînant dans un itérateur (chain), et puis de le transformer en une liste de nouveau? PS. une meilleure recette est dans le itertools de la documentation, et dans l'autre (plus tard) de réponse ici.
InformationsquelleAutor

Voici quelques pseudocode - vous pouvez couper même les appels récursifs en stockant les valeurs pour chaque appel que vous allez et avant l'appel récursif de vérifier si l'appel de la valeur est déjà présente.

L'algorithme suivant, disposera de tous les sous-ensembles à l'exclusion de l'ensemble vide.

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

Ainsi, par exemple, si s = "123" puis la sortie est:

InformationsquelleAutor kofhearts

Sans l'aide de itertools:

En Python 3, vous pouvez utiliser yield from pour ajouter un sous-ensemble générateur méthode de buit-dans set classe:

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

Pour l'exemple ci-dessous l'extrait de code fonctionne comme prévu:

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

grande utilisation de la yield from et avec une algorithmique explication

InformationsquelleAutor Amin Azarbadegan

Voici une manière simple, facile à comprendre algorithme.

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

Il devrait être k.append(n) au lieu de k.extend(n)

InformationsquelleAutor darxtrix

0

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

InformationsquelleAutor lidaobing

Vous devez vous connecter pour publier un commentaire.