Ensemble des parties en Perl

Ensemble des parties en Perl - Perl - Programmation

Marsh Posté le 29-04-2008 à 10:38:08    

Bonjour,
 
Je souhaite réaliser un petit programme permettant de trouver tout les mots contenus dans une suite de lettres (par exemple "ejuidcnnald" ), en enlevant successivement n lettres.
 
Finalement je me suis aperçu que cela revenait a construire l'ensemble des parties.
 
Je ne vois pas ce qui ne colle pas dans mon algorithme. La fonction appartient ne sert pas a grand chose pour le moment c'est pour plus tard. Cependant Je vois qu'il n'est pas correct puisque le mot atpmh n'est pas trouvé dans P(E).
 

Code :
  1. #/usr/bin/perl
  2. sub resoudre{
  3. my $mot=@_[0];
  4. my @mot2=split //,$mot;
  5. my $card=2**15;
  6. for(my $i=0;$i<$card;$i++)
  7. {
  8.  my @sousmot=();
  9.  for(my $l=0;$l<15;$l++)
  10.  {
  11.   (2**(15-$l) & $i) && push(@sousmot,$mot2[$l]);
  12.  }
  13.  appartient(@sousmot);
  14. }
  15. return;
  16. }
  17. sub appartient
  18. {
  19. my $mot=join(/-/ ,@_) ;
  20. my $cherche="atpmh";
  21. if($cherche eq $mot)
  22.  print $mot."\n";
  23. }
  24. return;
  25. }
  26. &resoudre("azertyuiopmlkjh" );


 
Une idée?


Message édité par exeed le 29-04-2008 à 18:16:00
Reply

Marsh Posté le 29-04-2008 à 10:38:08   

Reply

Marsh Posté le 29-04-2008 à 15:01:09    

c'est pas beau du tout comme code :o
Un petit conseil, rajoute un "use strict;" sous le shebang pour constater l'étendue du problème.
 
En dehors du problème d'écriture, tu te rends bien compte que avec 15 lettres tu as 32K mots possibles et que pour les obtenir "à la bourrin" tu vas être obliger de faire une tetra-chié d'itérations (2^(15*16/2) si je me trompes pas)?


---------------
Software and cathedrals are much the same - first we build them, then we pray.
Reply

Marsh Posté le 29-04-2008 à 17:48:33    

héhé désolé pour le code je ne connais pas bien perl :)
 
Et bien |P(E)|=2^|E], pourquoi ce *16/2 ?

Reply

Marsh Posté le 29-04-2008 à 17:54:23    

Ok donc toutes les erreurs sont les mêmes:
""n'importe quoi" requires explicit package name at ..."
 
Quel est ce fameux package?

Reply

Marsh Posté le 29-04-2008 à 18:00:44    

La manière "bourrin de base" pour que ton truc marche c'est de procéder récursivement et de calculer toutes les combinaisons possibles.
Dans ces combinaisons, énormément seront redondantes. Alors si au final tu as bien 2^15 réponses uniques, en gros tu auras effectué 2^15 * 2^14 * ... * 2^0 opérations ( ce qui fait 2^(15*16/2) )... enfin je crois :o
 


---------------
Software and cathedrals are much the same - first we build them, then we pray.
Reply

Marsh Posté le 29-04-2008 à 18:01:56    

exeed a écrit :

Ok donc toutes les erreurs sont les mêmes:
""n'importe quoi" requires explicit package name at ..."
 
Quel est ce fameux package?


C'est juste que pour déclarer une variable en perl, il faut mettre un perl devant.
C'est important car cela influe sur sa portée ( et à vue de nez j'ai pas l'impression que tu saches vraiment de quoi il s'agit )


---------------
Software and cathedrals are much the same - first we build them, then we pray.
Reply

Marsh Posté le 29-04-2008 à 18:13:29    

:) Si si je sais ce qu'est la portée mais je ne sais pas comment fonctionne tout ça en perl  
 
Aurais tu une idée du problème dans mon algo?

Reply

Marsh Posté le 29-04-2008 à 18:24:15    

En effet ça va faire beaucoup d'itérations mais je ne traiterais que les parties de plus de  4 éléments et de moins de 9, ça réduit déjà. (enfin pas le nombre d'itérations mais le temps global de traitement.

Reply

Marsh Posté le 30-04-2008 à 15:48:57    

Bon, j'ai corrigé les erreurs de syntaxe perl

Code :
  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;
  4. sub resoudre {
  5.     my $mot = $_[0];
  6.     my @mot2 = split //, $mot;
  7.     my $card = 2**15;
  8.     for (my $i = 0; $i < $card; $i++) {
  9.         my @sousmot=();
  10.         for (my $l = 0; $l < 15; $l++) {
  11.             (2**(15-$l) & $i) && push(@sousmot, $mot2[$l]);
  12.         }
  13.         appartient(@sousmot);
  14.     }
  15. }
  16. sub appartient {
  17.     my $mot = join('' , @_); #tu veux concatener les lettres si j'ai bien compris
  18.     #print $mot, "\n";   #a decommenter pour voir les valeurs successives
  19.     my $cherche = "atpmh";
  20.     if($cherche eq $mot) {
  21.         print $mot, "\n";
  22.     }
  23. }
  24. resoudre("azertyuiopmlkjh" );


Si tu regardes la sortie des mots, tu verras que la lettre a n'y apparait jamais, et donc que ton algo cense generer les parties, et que je n'ai pas compris, puisque tu n'expliques pas comment il est cense marcher, est foireux.
A+,


Message édité par gilou le 30-04-2008 à 15:49:58

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

Marsh Posté le 30-04-2008 à 18:33:30    

Ok merci pour la syntaxe.
 
Donc le principe de l'algo:
 
On commence a 000000000000000 , les 15 chiffres représentent le mot de 15 lettres.
Donc ici la boucle ne va rien mettre dans @sousmot.  
Puis on passera a 00000000000001, la, la boucle interne va mettre seulement la dernière lettre dans le mot.
Jusqu'à 111111111111111.
 
Je ne sais pas si c'est très clair. Je pense que la méthode est bonne cependant mon algo lui est surement faux.
 

Reply

Marsh Posté le 30-04-2008 à 18:33:30   

Reply

Marsh Posté le 30-04-2008 à 18:50:36    

Je crois avoir trouvé le problème :
 
ce n'est pas (2**(15-$l) & $i) && push(@sousmot, $mot2[$l]);
mais (2**(14-$l) & $i) && push(@sousmot, $mot2[$l]); sinon en effet a n'est jamais inclus.
 
Voici le code final qui je pense est correct:
 
   1. #!/usr/bin/perl
   2. use strict;
   3. use warnings;
   4.
   5. sub resoudre {
   6.     my $mot = $_[0];
   7.     my @mot2 = split //, $mot;
   8.     my $card = 2**15;
   9.     for (my $i = 0; $i < $card-1; $i++) {
  10.         my @sousmot=();
  11.         for (my $l = 0; $l < 15; $l++) {
  12.             (2**(14-$l) & $i) && push(@sousmot, $mot2[$l]);
  13.         }
  14.         appartient(@sousmot);
  15.     }
  16. }
  17.
  18. sub appartient {
  19.     my $mot = join('' , @_); #tu veux concatener les lettres si j'ai bien compris
  20.     #print $mot, "\n";   #a decommenter pour voir les valeurs successives
  21.     my $cherche = "atpmh";
  22.     if($cherche eq $mot) {
  23.         print $mot, "\n";
  24.     }
  25. }
  26.
  27. resoudre("azertyuiopmlkjh" );


Message édité par exeed le 30-04-2008 à 18:52:33
Reply

Marsh Posté le 30-04-2008 à 19:09:55    

Pour voir si c'est correct, tu generes tous les mots possibles dans un array, avec ton algo, tu tries et vires les doublons a tout hasard:

Code :
  1. @temp = sort { $a eq $b } @temp;  #tri de @temp
  2. my $prev = "not equal to $temp[0]";
  3. @result = grep($_ ne $prev && ($prev = $_, 1), @temp);


@result contient @temp sans doublons s'il arrive trié
puis tu regardes si tu as la bonne cardinalité, ie le bon nombre d'éléments dans ton array.
A+,


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