Algorithme de permutation

Algorithme de permutation - Algo - Programmation

Marsh Posté le 25-06-2004 à 11:25:49    

Bonjour,
 
Petit problème sur un algo de permutation.
 
J'ai un tableau de boolean, et j'aimerai sortir toute les solutions possible ? (recursivement)
 
Qqun a ca sous la main, j'ai les yeux trop pourri ce matin.
 
Thx
 
edit : en java ;)


Message édité par Shaman LizardKing le 25-06-2004 à 11:28:30

---------------
Le Smiley de la mort !! (8÷þ
Reply

Marsh Posté le 25-06-2004 à 11:25:49   

Reply

Marsh Posté le 25-06-2004 à 12:53:44    

v2
 
public static void trouveSolution(boolean[] tab, int pos)
 {  
   
  if(pos==10)
  {
   for(int j=0;j<10;j++)
   {
    System.out.print(tab[j] + " " ) ;
   }
   
   System.out.println(compteur) ;
   compteur++ ;
   
  }
 
  for(int i=pos; i<10; i++)
  {
   
   if(tab[i]==false)
   {
    tab[i] = true ;
    trouveSolution(tab, i+1) ;
   }
   else
   {  
    tab[i] = false ;
    trouveSolution(tab, i+1) ;
   }  
  }  
   
 }
 
 
mais la j ai que la moitié des solutions puisqu'en théroei il devrait en avoir 1024 et que j ai ai que 512

Reply

Marsh Posté le 25-06-2004 à 13:00:26    

c'est pas bon. fais une recherche sur le forum

Reply

Marsh Posté le 25-06-2004 à 13:05:03    

j'ai pas trouvé de solution après avoir fais une recherche... y a des questions restée sans réponse

Reply

Marsh Posté le 25-06-2004 à 13:10:34    

ben alors commence déjà par apprendre à rechercher : y a plein de topic dessus, et sur google et les faq d'algorithme, ça reviens en pagaille. et évidemment y a un chapitre la dessus dans le Knuth

Reply

Marsh Posté le 25-06-2004 à 14:34:27    

merci toi t'es un copain....

Reply

Marsh Posté le 25-06-2004 à 18:24:00    

En gros tu as un tableau de booléen et tu veux afficher toutes les solutions possible ?

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
...
1 1 1 1 1 1 1 1 1 1

J'ai bien compris ?
Si c'est ce que tu dois faire c'est super simple ! :D

Reply

Marsh Posté le 25-06-2004 à 18:54:20    

darkoli > compter en binaire est effectivement une solution, sauf qu'en c'est pas trivial à implémenter

Reply

Marsh Posté le 25-06-2004 à 22:25:35    

Taz a écrit :

darkoli > compter en binaire est effectivement une solution, sauf qu'en c'est pas trivial à implémenter

Oui mais il est aussi possible de compter simplement (0..1023) et de décomposer à chaque fois la valeur du compteur à l'aide de & et de >>. Il suffit de deux boucles imbriquées et c'est fait ! :D


Message édité par darkoli le 25-06-2004 à 22:26:49
Reply

Marsh Posté le 25-06-2004 à 22:28:11    

oui mais c'est lent pour rien ...

Reply

Marsh Posté le 25-06-2004 à 22:28:11   

Reply

Marsh Posté le 26-06-2004 à 12:23:41    

Taz a écrit :

darkoli > compter en binaire est effectivement une solution, sauf qu'en c'est pas trivial à implémenter


 
Je n'ai pas compris le problème, donc je risque de dire des bêtises, mais s'il faut juste générer :
 
0000
0001
0010
0011
....
 
Y'a rien de plus trivial pourtant :??:


---------------
Un matin je me lèverai et il fera beau.
Reply

Marsh Posté le 26-06-2004 à 21:33:36    

Taz a écrit :

oui mais c'est lent pour rien ...

En java ? (Je ne connais pas du tout java donc je n'en sais rien) ! :D

Reply

Marsh Posté le 27-06-2004 à 09:21:31    

Et récursivement c'est pas plus simple?

Reply

Marsh Posté le 27-06-2004 à 09:34:04    

pas si la séquence est longue


Message édité par Taz le 27-06-2004 à 09:34:40
Reply

Marsh Posté le 27-06-2004 à 10:27:26    

oui mais celui qui prend des séquences longues, c'est qu'il est pas pressé...

Reply

Marsh Posté le 27-06-2004 à 10:52:51    

m'en fiche bien en fait, y a des tas de bibliothèques qui font ça, du reste tant que ça fonctionne...

Reply

Marsh Posté le 27-06-2004 à 14:31:33    

Et tu t'es pas posé la question de savoir comment elles marchaient?

Reply

Marsh Posté le 27-06-2004 à 14:41:39    

oui. voir mes 2 premiers messages

Reply

Sujets relatifs:

Leave a Replay

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