Combinaison de n éléments dans un ensemble de n éléments sans répétition

Version imprimable

21/12/2008, 14h57
clowny

Combinaison de n éléments dans un ensemble de n éléments sans répétition

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!
21/12/2008, 16h31
pseudocode

Citation:

Envoyé par clowny

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 ? :koi:
21/12/2008, 19h42
clowny

Oui voilà pardon je me suis mal exprimé :oops:
21/12/2008, 20h29
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).
22/12/2008, 22h30
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?
22/12/2008, 22h37
pseudocode

Citation:

Envoyé par 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?

Pourquoi par MP et pas ici ? C'est secret ??
22/12/2008, 23h50
clowny

1 pièce(s) jointe(s)

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!).
23/12/2008, 11h42
pseudocode

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

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. ;)
23/12/2008, 11h47
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!
23/12/2008, 12h07
pseudocode

Citation:

Envoyé par clowny

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.
03/01/2009, 12h06
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:

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 :)