Outils pour utilisateurs

Outils du site


parties_ensemble

Ensemble des parties d'un ensemble

Objectif

Exemple: soit une liste d'objets [1,2,3]:

  • on veut savoir en extraire tous les regroupements possibles, sans tenir compte de l'ordre: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]],
  • et on veut savoir combien il y en a.


Référence externe pour la définition: voir http://fr.wikipedia.org/wiki/Ensemble_des_parties_d%27un_ensemble

Nombre des parties d'un ensemble

Combien il en a? ⇒ si l'ensemble possède n objets, on peut constituer 2**n sous-ensembles.

def parties(n):
    return 2**n

On peut le retrouver d'une autre façon: le nombre total de sous-ensemble est égal à la somme des combinaisons:

sum{k=0}{n}{C^k_n}

Essayons avec un ensemble de 3 éléments:

  • Combinaison de 3 objets pris de 0 à 0 ⇒ 1 ([])
  • Combinaison de 3 objets pris de 1 à 1 ⇒ 3 ([1], [2], [3])
  • Combinaison de 3 objets pris de 2 à 2 ⇒ 3 ([1, 2], [1, 3], [2, 3])
  • Combinaison de 3 objets pris de 3 à 3 ⇒ 1 ([1, 2, 3])

Total = 8 = 2**3

Liste des parties d'un ensemble composé d'une liste

On voudrait maintenant construire automatiquement une telle liste dans le cas général. Comment on fait?

Pour résoudre ce genre de problème, il y a une solution que j'aime bien, qui n'est pas trop complexe à comprendre et qui n'est pas récursive: il s'agit de s'appuyer sur le comptage en binaire.

Avec une liste composée de n éléments, on va compter de 0 à 2**n-1, et pour chaque valeur de ce compteur, on va placer un élément de la liste à chaque 1 qu'on aura dans la représentation binaire du compteur.

Exemple:

liste = [1, 2, 3] donc n=len(liste)=3 éléments

On va donc compter de 0 à 2**3-1=7

0   000   []
1   001   [3]
2   010   [2]
3   011   [2, 3]
4   100   [1]
5   101   [1, 3]
6   110   [1, 2]
7   111   [1, 2, 3]

On voit bien dans cet exemple: pour une valeur du compteur, s'il y a un '1' en 2ème position du compteur binaire, alors on ajoute un 2 dans la liste correspondant à ce compteur.

Et pour n'avoir que les solutions à 2 éléments, par exemple, il suffit de n'ajouter la solution d'un compteur que si cette solution a exactement 2 éléments. On retrouvera bien entendu ainsi la liste des combinaisons de 3 objets pris 2 à 2.

Voilà un code qui fait tout cela. l'argument 'seq' est la liste des n objets. La fonction retourne la liste des parties de cet liste.

def partiesliste(seq):
    p = []
    i, imax = 0, 2**len(seq)-1
    while i <= imax:
        s = []
        j, jmax = 0, len(seq)-1
        while j <= jmax:
            if (i>>j)&1 == 1:
                s.append(seq[j])
            j += 1
        p.append(s)
        i += 1 
    return p

Vous voyez comment on teste s'il y a un '1' à la position j dans la représentation binaire de i: par un décalage binaire (opérateur '>>') et un 'or' logique (opérateur &).

Par exemple: i=8 ⇒ '00001000'. Pour savoir s'il y a un '1' à la position j=3 (compté de droite à gauche à partir de 0), on fera: (i>>j)&1==1 qui ici donnera True.

Exemple d'utilisation:

seq = [1,2,3]
 
print partiesliste(seq)
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

On se servira de ce code légèrement modifié pour calculer la liste des combinaisons, puisqu'il suffit d'extraire de la liste des parties toutes les listes ayant le nombre voulu d'éléments.

Liste des parties d'un ensemble composé d'une chaine de caractères

On a ici une chaine de caractère, et on veut obtenir la liste de toutes les parties de l'ensemble formé par cette chaine.

Par exemple: "ABC" => ['', 'A', 'B', 'AB', 'C', 'AC', 'BC', 'ABC']

On va utiliser la fonction qui traite les listes:

def partieschaine(ch):
    """Retourne la liste de toutes les parties de l'ensemble des caractères de la chaine ch"""
    return [''.join(z) for z in partiesliste(list(ch))]

Exemple d'utilisation:

print partieschaine("ABC")
['', 'A', 'B', 'AB', 'C', 'AC', 'BC', 'ABC']


Amusez-vous bien!

parties_ensemble.txt · Dernière modification: 2010/01/09 12:08 par tyrtamos

Outils de la page