Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1900 connectés 

  FORUM HardWare.fr
  Programmation
  C

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

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

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

n°1889788
nlc
Le mieux est l'ennemi du bien
Posté le 30-05-2009 à 17:02:27  profilanswer
 

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++ );
mood
Publicité
Posté le 30-05-2009 à 17:02:27  profilanswer
 

n°1889820
Sve@r
Posté le 30-05-2009 à 19:41:37  profilanswer
 

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.
n°1889832
nlc
Le mieux est l'ennemi du bien
Posté le 30-05-2009 à 21:13:04  profilanswer
 

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++ );
n°1889867
Taz
bisounours-codeur
Posté le 31-05-2009 à 10:20:16  profilanswer
 

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

n°1889879
gilou
Modérateur
Modzilla
Posté le 31-05-2009 à 11:40:47  profilanswer
 

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é!  --
n°1889884
nlc
Le mieux est l'ennemi du bien
Posté le 31-05-2009 à 11:49:28  profilanswer
 

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++ );
n°1889904
Sve@r
Posté le 31-05-2009 à 13:41:35  profilanswer
 

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.
n°1889912
gilou
Modérateur
Modzilla
Posté le 31-05-2009 à 14:45:34  profilanswer
 

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é!  --

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C

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

 

Sujets relatifs
Servlet:Comment récuperer tous les élements qui ne sont pas selectionndéclencher le calcul d'un fichier excel avec VBA
Problème de calcul de Delta[batch] Calcul d'un fichier txt et envoi vers sql
Afficher le nom des éléments d'un tableauPHP : Calcul opération dans une variable
Calcul de difference entre 2 dates dans 1 fichier 'Batch'Calcul longueur d'une liste à liens multiples
Inserer feuille de calcul dans sujet d'un forumOrdonner un calcul de requetes SQL
Plus de sujets relatifs à : Factorielle et calcul de tous les ordres possibles de x éléments


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR