Discussion :

[divayht]

Salut à tous

Mon problème d'algorithme concerne les différentes combinaisons d'un tableau. J'ai déjà trouvé sur ce forum des topic qui en parlent, mais mon problème est un peu différent.

Admettons que j'ai 3 tableaux;

Code :

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

1
2
3
tab1 = [ 'a', 'b', 'c' ];
tab2 = [ 'd', 'e', 'f', 'g' ];
tab3 = [ 'h', 'i'];

Je dois trouver toutes les combinaisons possibles entre ces tableaux, sachant qu'une seule valeur par tableau est choisie.

Exemples:

aeh
cfi
bdh

Mais je ne peux pas faire:

afg
bch
iea

Sachant qu'en fait j'ai une dizaine de tableaux avec 3 ou 4 possibilités à chaque fois :s
Je n'ose imaginer le nombre de possibilités^^

En tout cas au niveau algorithmique je suis perdu, si vous avez une idée, un algo ou du code je suis preneur !

Merci d'avance

[Invité(e)]

Bonjour,

Commençons par compter les mots si on ne bouge pas les lettres :

première lettre : autant de choix que de lettre dans tab1 : 3
seconde lettre : autant de choix que de lettre dans tab2 : 4 x 3 = 12 possibilités
troisième lettre : autant de choix que de lettre dans tab3 : 2 x 12 = 24 possibilités


Ainsi de suite.

Donc pour un ensemble de tableaux de lettres donnés, le nombre de mots formable est :

Code :

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

1
2
 
NbMots = Produit(Card(Tab[i])), pour i de 1 à N

(Où Card est le nombre d'éléments dans un tableau).

Après, si l'ordre des lettres peut changer, il faux prendre un mot en particulier et compter les combinaisons qu'on peut y faire* : (je t'épargne la démonstration)

Code :

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

NbArrangements = N!

où N est le nombre de lettres dans le mot.

On est déduit :

Code :

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

NbMots = N! x Produit(Card(Tab[i]))

(attention, cette formule n'est valable que s'il n'y a pas de lettre doublée)

* c'est à dire, à partir de A et B on peut former AB et BA, à partir de A, B et C, on peut former ABC, ACB, BAC, BCA, CAB, CBA...

[divayht]

Salut et merci pour ta réponse

Je dois dire que je n'ai pas exactement tout compris^^

Les mots ne peuven pas changer de sens, par exemple, adh est valide mais pas hda .

Du coup je ne sais pas si les possibilités sont

Code :

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

Produit(Card(Tab[i]))

ou

Code :

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

N! *Produit(Card(Tab[i]))

J'ai bien compris pour trouver le nombre de toutes les combinaisons, mais pas pour les lister :s

Merci de votre aide

[Zavonen]

Voici un script python implémentant un algo récursif pour lister les éléments d'un produit cartésien d'une famille finie d'ensembles donnée sous forme de liste:

Code python :

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

1
2
3
4
5
6
7
8
def listeproduit(L):
    if len(L)==0: # produit vide
        return [[]]
    else:
        K=listeproduit(L[1:]) #appel récursif 
        return [[x]+y for x in L[0] for y in K] #ajouter tous les éléments du premier ensemble au produit cartésien des autres
 
print listeproduit([[1,2],['a','b'],['w','y']])

[divayht]

Merci beaucoup Zavonen, ça marche super

Si quelqu'un cherche à afficher le résultat dans un fichier (je partage car j'ai un peu lutté, ça fait un bout de temps que j'ai pas touché à python):

logfile = open('/home/divayht/liste_combinaisons_profil.txt', 'w')

resultat = listeProduit([visage, yeux, nez, bouche, modele, tonicite, etageDominant])
for i in resultat:
for j in i:
logfile.write(j + ", ")
logfile.write("\n")

logfile.close()