Discussion :

[Stéphane Nadry]

Voilà mon problème . J'aimerai obtenir simplement toutes les combinaisons possibles (de p éléments) parmi une liste de n éléments . par exemple : soit la liste [ 1, "machin", [0, 1] ] pour laquelle je souhaite avoir la liste des combinaisons de deux éléments . En retour j'obtiendrais [[1, "machin"], [1, [0, 1]], ["machin", [0, 1]]] .

Je suis débutant en python . Je fais du python pour un MOD d'un jeu (CivilisationIV) . De ce fait je n'ai pas accès aux extentions (bibliothèques) de python .

J'ai reussi à obtenir ce que je voulais en recupérant la liste des indexs des combinaisons . J'ai préféré ne pas implémenter une fonction reccursive pour éviter une erreur du nombre de reccursion maximum . Voilà la fonction (qui ne marche pas pour p=0 ou 1 mais c'est sans importance ) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def getCombi(p, n) :
        lResult = []
        lListPreCombi = []
        for iPass in range(n) :
                if iPass <= n - p : lListPreCombi += [[n - 1 - iPass]]
                for lPreCombi in lListPreCombi :
                        minVal = min(lPreCombi)
                        bResult = len(lPreCombi) == p-1
                        for i in range(n - 1 - iPass, minVal):
                                combiTemp = [i] + lPreCombi
                                if bResult :
                                        if not combiTemp in lResult : lResult.append(combiTemp)
                                else :
                                        if not combiTemp in lListPreCombi : lListPreCombi.append(combiTemp)
        return lResult

J'aimerai savoir s'il n'y a pas une fonction simple pour obtenir ce resultat ?

Merci d'avance !

Stéphane

[Guigui_]

tu peux regarder ce code ( http://python.developpez.com/sources...h#Combinatoire ) (mais je l'avais implémenter en récursif (y'a tout de même peu de chance de faire exploser la pile d'appel)

[Stéphane Nadry]

Ca m'apprendra a chercher un peu plus avant de poster , j'avais toujours reussi a trouver ce que je voulais depuis que je me suis inscrit sur ce forum . Magnifique fonction , Ce que j'imaginais comme fonction reccursive est loin de celle ci et aurait été probablement a la limite . Mais celle ci est parfaite !

Merci beaucoup

Stéphane

[tyrtamos]

Bonjour,

Il y a une solution plus simple, à défaut d'être élégante, rendue possible par les calculs en entier de Python (pas de limite sauf mémoire):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
def fact(n):
    """Factorielle n (version non récursive)."""
    x=1
    for i in xrange(2,n+1):
        x*=i
    return x
 
def permutation(n):
    """Permutation de n objets"""
    return fact(n)
 
def arrangement(n,k):
    """Arrangement de n objets pris p a p."""
    return fact(n)/fact(n-k)
 
def combinaison(n,k):
    """Combinaison de n objets pris p a p."""
    return fact(n)/(fact(k)*fact(n-k))

[Stéphane Nadry]

Merci tyrtamos pour ton aide mais ce que je cherchais a faire n'etait pas de calculer le nombre de combinaisons possibles mais d'en obtenir la liste .

Stéphane

[tyrtamos]

Effectivement, toutes mes excuses!

Tyrtamos

[GnuVince]

Il y a une façon assez simple d'obtenir les combinaisons d'une liste, regarde l'article de Wikipédia sur les powersets. Une fois que tu as ton powerset, tu peux simplement filtrer les élément de la longueur désirée.

[Stéphane Nadry]

Je ne connaissais pas cette méthode . Merci de m'avoir pointé là dessus , ca fait plaisir d'apprendre . Mais je ne pense pas que je vais implémenter cela . Le nombre d'éléments du powerset est de 2^n et cela risque de ralentir ma fonction ( ou j'appele getCombi dans une double boucle ) , voire de poser un problème de limite .

Merci ,

Stéphane