Factorielle et calcul de tous les ordres possibles de x éléments

Factorielle et calcul de tous les ordres possibles de x éléments - C - Programmation

Marsh Posté le 30-05-2009 à 17:02:27    

Bonjour à tous  :hello:  
 
En admettant que j'ai 5 couleurs, jaune, bleu, rouge, vert, blanc, que je les code dans des char respectivement 'Y', 'B', 'R', 'G', 'W', comment faire pour afficher les 120 chaînes de caractères représentants les 120 combinaisons d'ordres différents (factorielle de 5) ?
 
Du style :  
"YBRGW"
"YBRWG"
"YBGRW"
"YBGWR"
etc...
 
Faire le programme en C ne me pose pas de souci, ce qui pose souci c'est de trouver un algo simple qui permet de calculer toutes les combinaisons de position de n élements, en l'occurence 5 ici. Je n'arrive pas trouver la logique qui me permettrait d'en déduire l'algo  :heink:  
 
Des idées !??  :bounce:


---------------
char table[] = {112,114,105,110,116,102,40,34,37,99,37,99,37,99,34,44,49,49,48,44,49,48,56,44,57,57,41,59,0}; char* tablePtr = table; while(*tablePtr) printf( "%c",*tablePtr++ );
Reply

Marsh Posté le 30-05-2009 à 17:02:27   

Reply

Marsh Posté le 30-05-2009 à 19:41:37    

C'est un algo d'anagramme.
Or les différents anagrammes de "YBRGW" sont
- Y + anagrammes("BRGW) plus
- B + anagrammes("YRGW) plus
- R + anagrammes("YBGW) plus
- G + anagrammes("YBRW) plus
- W + anagrammes("YBRG)
...


---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 30-05-2009 à 21:13:04    

Bon c'est bon, pas voulu me faire chier à trop réfléchir, j'ai fait la liste des 120 combinaisons à la main :D


---------------
char table[] = {112,114,105,110,116,102,40,34,37,99,37,99,37,99,34,44,49,49,48,44,49,48,56,44,57,57,41,59,0}; char* tablePtr = table; while(*tablePtr) printf( "%c",*tablePtr++ );
Reply

Marsh Posté le 31-05-2009 à 10:20:16    

Ca revient à compter de 0 à 120 en base 5, chaque chiffre correspondant à une de tes lettres.

Reply

Marsh Posté le 31-05-2009 à 11:40:47    

Sve@r a écrit :

C'est un algo d'anagramme.
Or les différents anagrammes de "YBRGW" sont
- Y + anagrammes("BRGW) plus
- B + anagrammes("YRGW) plus
- R + anagrammes("YBGW) plus
- G + anagrammes("YBRW) plus
- W + anagrammes("YBRG)
...

On peut aussi faire ca de manière efficace avec une boucle sur toutes les combinaisons, mêmes les mauvaises, et filtrer avec un test simple les bonnes combinaisons.
un exemple d'algo en perl pour le cas donné ici  (ca peut se traduire en C sans grosse difficulté):

Code :
  1. #!/usr/local/bin/perl
  2.  
  3. my %data = ('Y' => 1,   # valeur initiale
  4.            'B' => 6,   # 5*1   + 1
  5.            'R' => 31,  # 5*6   + 1
  6.            'G' => 156, # 5*31  + 1
  7.            'W' => 781, # 5*156 + 1
  8.        );  # un mot avec les 5 lettres correspondra a une somme de
  9.            # 1 + 6 + 31 + 156 + 781 = 975
  10. my @letter = (keys %data);
  11. foreach my $i (@letter) {
  12.    foreach my $j (@letter) {
  13.        foreach my $k (@letter) {
  14.            foreach my $l (@letter) {
  15.                foreach my $m (@letter) {
  16.                    if ($data{$i}+$data{$j}+$data{$k}+$data{$l}+$data{$m} == 975) {
  17.                        print $i, $j, $k, $l, $m, "\n";
  18.                    }
  19.                }
  20.            }
  21.        }
  22.    }
  23. }


A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 31-05-2009 à 11:49:28    

Oui, hier soir après avoir fait les combinaisons à la main, j'ai eu la même idée, mais c'était trop tard !! 5 boucles imbriquées, et affichage des bonnes combinaisons seulement (que des éléments différents)


---------------
char table[] = {112,114,105,110,116,102,40,34,37,99,37,99,37,99,34,44,49,49,48,44,49,48,56,44,57,57,41,59,0}; char* tablePtr = table; while(*tablePtr) printf( "%c",*tablePtr++ );
Reply

Marsh Posté le 31-05-2009 à 13:41:35    

Taz a écrit :

Ca revient à compter de 0 à 120 en base 5, chaque chiffre correspondant à une de tes lettres.


 
Là je ne pige pas. Je ne vois pas le lien entre la suite ['0', '1', '2', '3', '4', '10', '11', '12', '13', '14', '20', '21', '22', '23', '24', '30', '31', '32', '33', '34', '40', '41', '42', '43', '44', '100', '101', '102', '103', '104', '110', '111', '112', '113', '114', '120', '121', '122', '123', '124', '130', '131', '132', '133', '134', '140', '141', '142', '143', '144', '200', '201', '202', '203', '204', '210', '211', '212', '213', '214', '220', '221', '222', '223', '224', '230', '231', '232', '233', '234', '240', '241', '242', '243', '244', '300', '301', '302', '303', '304', '310', '311', '312', '313', '314', '320', '321', '322', '323', '324', '330', '331', '332', '333', '334', '340', '341', '342', '343', '344', '400', '401', '402', '403', '404', '410', '411', '412', '413', '414', '420', '421', '422', '423', '424', '430', '431', '432', '433', '434'] et les combinaisons de YRGVB...
 

gilou a écrit :

On peut aussi faire ca de manière efficace avec une boucle sur toutes les combinaisons, mêmes les mauvaises, et filtrer avec un test simple les bonnes combinaisons.
un exemple d'algo en perl pour le cas donné ici  (ca peut se traduire en C sans grosse difficulté):


 
Bien vu. Je me suis focalisé sur un cas général sans réfléchir que le problème ne concernait en tout et pour tout que ces 5 lettres. Evidemment faire un algo récursif pour ça serait du gaspillage...


---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 31-05-2009 à 14:45:34    

On peut aussi faire comme suit (ça doit pouvoir se récursiver) en perl, mais c'est par contre nettement moins transposable en code C:

 
Code :
  1. #!/usr/local/bin/perl
  2.  
  3. my @letter = ('Y', 'B', 'R', 'G', 'W');
  4.  
  5. foreach my $i (@letter) { #array avec toutes les lettres
  6.    foreach my $j (grep(!/$i/, @letter)) { #array sans la premiere lettre choisie
  7.        foreach my $k (grep(!/$i|$j/, @letter)) { #array sans les 2 premieres lettres choisies
  8.            foreach my $l (grep(!/$i|$j|$k/, @letter)) { #etc
  9.                foreach my $m (grep(!/$i|$j|$k|$l/, @letter)) { #etc
  10.                    print $i, $j, $k, $l, $m, "\n";
  11.                }
  12.            }
  13.        }
  14.    }
  15. }
 

A+,


Message édité par gilou le 31-05-2009 à 14:47:39

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed