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

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:

<m>sum{k=0}{n}{C^k_n}</m>

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

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.

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!