Partie d'un ensemble

Alban_ · January 2018

Bonjour, en voulant vérifier en Python un exercice de combinatoire, je me suis demandé comment générer les parties d'un ensemble. Dans mon exercice, il s'agissait des mains de 5 cartes d'un jeu à 32 cartes, mais cela revient au même de savoir générer les parties à $k$ éléments d'un ensemble à $n$ éléments.

Je veux donc faire une fonction qui prend en paramètre une liste $L$ sans répétition (je pourrais éventuellement le type ensemble de Python, mais je commence avec le type dont j'ai le plus l'habitude) et un entier naturel $k$ compris entre $0$ et la la longueur de la liste $L$. Comme je n'avais aucune idée de comment faire cela, j'ai cherché quelque chose de ressemblant et je suis tombé sur http://python.jpvweb.com/python/mesrecettespython/doku.php?id=parties_ensemble : le problème n'est pas le même puisqu'il cherche à construire les parties d'un ensemble, mais cela y ressemble un peu. La solution à base de comptage en binaire me plait bien, mais elle est inopérante directement pour mon problème : il n'est pas question de générer tous les nombres à 32 chiffres en binaire et de sélectionner ceux qui ont $k$ fois le chiffre $1$ pour construire mes parties à $k$ éléments.

J'imagine qu'il y a une solution pour faire cela, mais je suis complètement bloqué. Le seul truc un peu idiot qui me vient, c'est de sélectionner $k$ nombres dans la liste $L$, de trier la liste obtenue et vérifier s'il est déjà dans la liste de mes parties. Ça marche pas trop mal si je cherche les parties à 5 éléments dans un ensemble à 10 éléments, beaucoup moins bien si mon ensemble de départ a 32 éléments.

Je mets les fonctions pas très utiles que j'ai faites :

def parties(L, k):
    M = []
    limite = combinaison(len(L), k)
    while len(M) < limite:
        liste = random.sample(L, k)
        liste.sort()
        if liste not in M:
            M.append(liste)
    return(M)

Avec combinaison qui fait ce qu'on pense :

def combinaison(n, k):
    produit = 1
    for j in range(1, k + 1):
        produit = produit*(n - k + j)/j
    return(produit)

gerard0 · January 2018

Bonjour.

Soient $x_1, x_2, ...x_n$ les éléments de ton ensemble.
Tu peux commencer par les parties qui contiennent $x_1$, qui s'obtiennent en prenant $x_1$ puis une partie à k-1 éléments de $x_2, ...x_n$ (récursion), puis tu complètes par les parties qui ne contiennent pas $x_1$ qui sont justement les partie à k éléments de $x_2, ...x_n$ (récursion).
Si k est très grand, il y a intérêt à "dérécursiver" le programme, car il y a quand même $2^k$ appels récursifs.

Cordialement.

bisam · January 2018

La méthode "classique" :
1) Tu numérotes les éléments de l'ensemble $E$ dont tu veux décrire les parties.
2) Tu mets en bijection les parties de $E$ avec les décompositions en binaire de entiers de 0 à $2^n-1$.
3) Tu énumères dans l'ordre lexicographique toutes les listes contenant $k$ fois 1 et $n-k$ fois 0... et tu en déduis les parties correspondantes.

La méthode "je ne réinvente pas la roue" :

import itertools

for C in itertools.combinations(my_list, k):
    print(C)

Attention, la fonction "combinations" renvoie un générateur et non une liste (et elle peut aussi s'appliquer à un générateur... même s'il est infini !)

john_john · January 2018

On peut aussi utiliser le code de Gray C'est ici que l'on fabrique récursivement mais qui engendre, une fois établi, une liste itérative des parties d'un ensemble à $n$ éléments. Il a l'avantage de ne basculer qu'un chiffre binaire à la fois.

Cordialement, j__j

Alban_ · January 2018

Bonjour et merci pour vos réponses.

J'ai pensé à itertoools que j'utilise si je veux faire des produits cartésiens, mais je ne suis bêtement pas allé voir s'il disposait de la fonction que je voulais.

Même si la fonction de Bisam fait exactement ce que je veux, je regarde tout de même les méthodes "en réinventant la roue" quand j'aurai un peu de temps. Je ferai moins rapide que la fonction de Python, mais ce n'est pas très grave.

J'ai déjà tenté d'implémenter la méthode de Gérard, sans réussite. Mais il faut que j'y passe un peu plus de temps avant de venir poser des questions. Par contre, dans la méthode basique de Bisam, j'ai l'impression que le temps d'exécution va être monstrueux (dans mon exemple, je voulais construire les parties à 5 éléments dans un ensemble à 32 éléments) : si je comprends bien, on utilise un procédé pour construire toutes les parties de mon ensemble puis on construit explicitement uniquement celles qui ont 5 éléments. Même si on ne construit pas réellement toutes les parties, on va devoir lire une liste de $2^{32}$ éléments.

bisam · February 2018

J'avais un peu oublié ton message... et je n'ai pas répondu.

Non, on n'est pas obligé d'énumérer toutes les parties pour ensuite ne garder que celles ayant k éléments.
J'ai bien dit que l'on n'énumérait que celles qui ont k éléments.

On peut le faire ainsi :

def combi(E, p):
    """Renvoie une liste des p-combinaisons de E.
    La liste pos décrit dans l'ordre croissant les indices des éléments choisis dans E"""

    n = len(E)
    rep = []
    pos = list(range(p))             # au départ, on prend toutes les positions les plus à gauche
    
    while pos[0] <= n - p:           # le dernier cas est donc pos=[n-p,n-p+1,...n-1]
        # pour voir les indices des positions choisies au fur et à mesure, décommenter la ligne suivante
        # print(pos)
        
        # on ajoute la combinaison trouvée à la liste réponse
        rep.append(tuple(E[a] for a in pos)) 
        
        # on cherche la combinaison suivante
        j = p - 1                    # on part de la position la plus à droite
        while pos[j] == n - p + j:   # tant que la j ème position est la plus à droite possible
            j -= 1                   # on diminue j
        pos[j] += 1                  # ensuite, on décale la j ème position vers la droite
        for k in range(j, p - 1):    # et on colle les autres immédiatement à sa gauche.
            pos[k + 1] = pos[k] + 1
            
    return(rep)

Alban_ · February 2018

Merci bisam de ton retour, j'avais un peu oublié ces tentatives après quelques échecs. Je vais regarder ce que tu proposes.

Partie d'un ensemble

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 24