Discussion :

[clowny]

Bonjour à tous!

J'essaie de réaliser un algorithme me donnant les combinaisons possibles (sans répétition) de n éléments dans un ensemble correspondant à n éléments lui aussi.
Ce que je rechercherais est simplement un petit peu d'aide (pas la solution je voudrais la trouver moi-même) : j'essaie de réaliser la chose à la main sur un petit nombre n mais j'ai du mal.
Auriez vous des références, en langage accessible, sur le sujet?

Merci pour toute aide et j'espère ne pas trop vous déranger!

[pseudocode]

J'essaie de réaliser un algorithme me donnant les combinaisons possibles (sans répétition) de n éléments dans un ensemble correspondant à n éléments lui aussi.

Tu veux dire l'ensemble des permutations de n éléments ?

[clowny]

Oui voilà pardon je me suis mal exprimé

[pseudocode]

Dans ce cas, je te conseille de procéder par récurrence.

Soit un ensemble de taille "n" : {A,B,C,D,...}. Les permutations possibles commencent soient par A, soient par B, soient par C ... C'est à dire "n" choix possibles pour le 1er élément.

Pour chaque 1er élément choisi, il nous reste à "accoler" les permutations d'un ensemble de taille "n-1" = l'ensemble de départ dans lequel on a retiré le 1er élément choisi.

On réitère le procédé pour cet ensemble de taille "n-1", et ainsi de suite, jusqu'a ce que la la taille de l'ensemble soit un cas trivial (taille = 1 ou 0 éléments).

[clowny]

Merci beaucoup!

Ca m'a pris beaucoup de travail mais je pense être en train d'avancer!
Pourrais je te soumettre mon algo graphique par mp?

[pseudocode]

Merci beaucoup!

Ca m'a pris beaucoup de travail mais je pense être en train d'avancer!
Pourrais je te soumettre mon algo graphique par mp?

Pourquoi par MP et pas ici ? C'est secret ??

[clowny]

Non mais j'arrivais pas à mettre une image directement sur le sujet!
En pièce jointe j'espère que ça va marcher!
Tiens regarde (enfin si tu as le temps!).

[pseudocode]

Je vois que tu as compris le principe de cet algo.

Ton implémentation marche bien dans le cas de 3 éléments. Cependant, il va falloir ruser pour le généraliser car le nombre de boucles for() à imbriquer dépend de la taille de l'ensemble de départ.

[clowny]

OK merci beaucoup!!
Je débute donc faut que je travaille sur chacun, avec un peu d'aide, mais faut que je force dessus pour comprendre.
J'aimerais au moins implémenter ce modeste petit algo dans un langage : python te semblerait il bien choisi?

Merci de t'y être penché en tout cas!

[pseudocode]

J'aimerais au moins implémenter ce modeste petit algo dans un langage : python te semblerait il bien choisi?

Très bon choix. D'autant qu'on a un forum dédié a ce langage, et aussi un rédacteur/modérateur Algo qui adore ce langage.

[hydrolyre]

Coucou, si tu ne veux que compter le nombre de combinaison, il y une formule très simple.
Soit n le nombre d'élément total,
Soit p le nombre d'élément de chaque possibilités,
"p parmi n" vaut : (n!)/( (p!)(n-p)! )

n! équivaut à 1*2*3*...*n et s'appelle "factorielle n"

En C++ :

Code :

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

1
2
3
4
5
6
 
int n,p;
cin>>n>>p;
 
int Combi = Fact(n)/( Fact(p)*Fact(n-p) );
cout<<Combi<<endl;

Dans ce bout de code ::Fact(int) correspond à factorielle.

J'espère que ca va te servir