• Publicidad

Búsqueda exhaustiva en Perl

¿Apenas comienzas con Perl? En este foro podrás encontrar y hacer preguntas básicas de Perl con respuestas aptas a tu nivel.

Búsqueda exhaustiva en Perl

Notapor Hamtaro » 2017-01-19 16:15 @718

Hola a todos.

Antes de nada, daros las gracias por el magnífico trabajo que estáis haciendo. Cuando aprenda bien Perl me gustaría también ayudar por aquí... Mientras tanto, aquí dejo mi duda.

Resulta que estoy con búsqueda exhaustiva en Perl... y tengo este código realizado por el profesor:

Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1. sub variaciones {
  2.         # Parámetros
  3.         my($inicio, $fin, $longitud) = @_;
  4.        
  5.         # Variables locales
  6.         my @resultado = ();
  7.         my @semilla = ();
  8.         my $fin_generacion = 0; # falso
  9.        
  10.         # 1. Inicializa la semilla, es decir, el tamaño de la lista.
  11.         for (my $i = 0; $i < $longitud; $i++) {
  12.                 push @semilla, $inicio;
  13.         }
  14.  
  15.         # 2. Genera las variaciones
  16.         while ($fin_generacion == 0) {
  17.                
  18.                 # Almacena la variación (copia de semilla)
  19.                 my @variacion = @semilla;
  20.                 push @resultado, \@variacion;
  21.                
  22.                 # Intenta incrementar la semilla
  23.                 my $incremento = 0;     # falso
  24.                 my $i = 0;
  25.                 while ($i < $longitud and not $incremento) {
  26.                        
  27.                         if ($semilla[$i] == $fin) {
  28.                                 $semilla[$i] = $inicio;
  29.                         }
  30.                         else {
  31.                                 $semilla[$i]++;
  32.                                 $incremento = 1; # verdadero
  33.                         }
  34.                         $i++;
  35.                 }
  36.                 if (not $incremento) {
  37.                         $fin_generacion = 1; # verdadero       
  38.                 }
  39.         }
  40.  
  41.         # 3. Retorna el resultado
  42.         return @resultado;
  43. }
  44.  
  45.  
  46. my @resultado1 = variaciones(0, 9, 2);
  47.  
  48. foreach my $variacion_ref (@resultado1) {
  49.  
  50.         my @variacion = @{$variacion_ref};
  51.         print "(", join(", ", @variacion), ") ";
  52. }
  53.  
Coloreado en 0.003 segundos, usando GeSHi 1.0.8.4


El código lo entiendo perfectamente, más o menos, lo que no entiendo es la parte del bucle while(), es decir, no entiendo el "not" que incluye.

Hasta donde tengo entendido el bucle while() se ejecuta siempre que la condición sea TRUE, entonces... traduciéndolo al español, sería: Mientras que no sea $fin_generacion... Cosa que no entiendo porque no se ejecutaría.

Tampoco entiendo el segundo while con el not $incremente. Para mi es... Mientras que $i sea menor que longitud y no sea $incremento, es decir, y no sea 0. Por lo tanto aqui tampoco se cumpliría el TRUE.

Muchas gracias por todo y buen foro.
Avatar de Usuario
Hamtaro
Perlero nuevo
Perlero nuevo
 
Mensajes: 4
Registrado: 2015-11-19 17:34 @773

Publicidad

Re: Búsqueda exhaustiva en Perl

Notapor explorer » 2017-01-19 17:41 @778

No sé muy bien a qué while() te refieres porque nombras elementos de los dos. No importa, te detallo el significado de los dos.

En efecto, el bucle while() se ejecuta mientras la condición que pongamos dé un valor verdadero.

Antes de seguir, hay que aclarar que en Perl, un valor verdadero es aquel que no es falso. Esto parece una tontería, pero resulta que es más fácil describir los valores de verdad o falsedad empezando por los falsos. Sacado de perldoc perlsyn:
Sintáxis: [ Descargar ] [ Ocultar ]
Using text Syntax Highlighting
Verdad y falsedad

        El número 0, las cadenas '0' y "", la lísta vacía "()" y el "undef" son
        todos falsos en contexto booleano. Todos los demás valores son verdaderos.
        La negación de un valor verdadero, por medio de "!" o "not" devuelve un
        valor falso especial. Cuando se evalúa como cadena, se le trata como "",
        pero como número, se le trata como 0. La mayor parte de los operadores que
        devuelven verdadero o falso se comportan de esta manera.
Coloreado en 0.000 segundos, usando GeSHi 1.0.8.4

El primer while() es:
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1.         while ($fin_generacion == 0) {
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4

Literalmente, dice: "haz el bucle mientras $fin_generación sea 0".

La variable $fin_generacion es en realidad un indicador (bandera), que se inicializa en la línea 8, y se modifica en la línea 37 para indicar que el bucle while() debe terminar. En ese línea se establece $fin_generacion a 1, por lo que al volver a probar la condición de la línea 16, ya no se cumple (1 no es igual a 0), y el bucle while() termina.

Del segundo while():
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1.                 while ($i < $longitud and not $incremento) {
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4

La condición dice: "haz el bucle mientras que a) $i sea inferior a $longitud, y b) no-$incremento sea verdadero".

La primera parte está clara: usamos $i como un índice, y no queremos sobrepasar la $longitud de los arrays. El tema complicado puede estar en la segunda parte. Desarrollándolo mejor:

"no-$incremento sea verdadero" es lo mismo que "$incremento sea falso".

Estamos en el mismo caso que el primer while(): $incremento se usa como bandera, y se inicializa a 0. De esa manera, entra en el bucle while. "not $incremento" resuelve a verdadero, por lo que se cumple esa parte de la condición, y entra. Cuando, más tarde, en la línea 32, la variable $incremento se pone 1, al llegar de nuevo a la condición, resuelve en "not 1", es decir, "falso", y como se trata de un "and", toda la condición es falsa, y el bucle termina.

Hoy en día se recomienda dar mejores nombres a este tipo de variables. Por ejemplo, la primera $fin_generacion, yo le cambiaría el nombre a $estamos_generando, y la inicializaría a 1, para luego ponerla a 0 en mitad del programa. Y para $incremento, la llamaría $hay_incremento.

Esta es mi propia versión. Aunque veas en el código cosas muy raras, te aseguro que no hay nada de "magia".
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1. #!/usr/bin/env perl
  2. use utf8;
  3. use strict;
  4. use warnings;
  5.  
  6. sub variaciones {
  7.         # Parámetros
  8.         my($inicio, $fin, $longitud) = @_;
  9.        
  10.         # Variables locales
  11.         my @resultado;
  12.        
  13.         # 1. Inicializa la semilla
  14.         my @semilla = ($inicio) x $longitud;
  15.  
  16.         # 2. Genera las variaciones
  17.         my $hay_incremento;                                             # nos avisa de si se incrementó @semilla o no
  18.  
  19.         do {
  20.                 $hay_incremento = 0;                                    # de momento, no lo hay
  21.  
  22.                 # Almacena la variación actual (una copia de la semilla que tenemos en este momento)
  23.                 push @resultado, [ @semilla ];
  24.                
  25.                 for (my $i = 0; $i < $longitud; $i++) {                 # por toda la $longitud de la @semilla
  26.                        
  27.                         if ($semilla[$i] == $fin) {                     # si el elemento llegó a $fin
  28.                                 $semilla[$i] = $inicio;                 # lo ponemos al valor $inicio
  29.                                                                         # y el bucle continúa con el siguiente
  30.                                                                         # elemento de @semilla
  31.                         }
  32.                         else {
  33.                                 $semilla[$i]++;                         # incrementamos el elemento
  34.                                 $hay_incremento = "sí, lo hay";                # y lo marcamos
  35.                                 last;                                   # terminamos el bucle, no hay que hacer más
  36.                         }
  37.                 }
  38.  
  39.         } while ($hay_incremento);
  40.  
  41.         # 3. Retorna el resultado
  42.         return \@resultado;
  43. }
  44.  
  45.  
  46. my $resultado_ref = variaciones(0, 4, 2);
  47.  
  48. for my $variacion_ref (@$resultado_ref) {
  49.  
  50.     print "(", join(", ", @$variacion_ref), ") ";
  51. }
  52.  
  53. print "\n";
  54.  
  55.  
Coloreado en 0.002 segundos, usando GeSHi 1.0.8.4

Como puedes ver, siempre se intenta que el código sea legible, casi como si fuera algo literario, como el caso de
Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1.         } while ($hay_incremento);
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14486
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España

Re: Búsqueda exhaustiva en Perl

Notapor Hamtaro » 2017-01-21 10:42 @488

Vale, vale... me ha quedado un poco más claro...

Te puse el ejemplo que había modificado yo para hacer una prueba, cuando el original del profesor es este, con los dos while() usando la parte "not":

Sintáxis: [ Descargar ] [ Ocultar ]
Using perl Syntax Highlighting
  1. sub variaciones {
  2.         # Parámetros
  3.         my($inicio, $fin, $longitud) = @_;
  4.        
  5.         # Variables locales
  6.         my @resultado = ();
  7.         my @semilla = ();
  8.         my $fin_generacion = 0; # falso
  9.        
  10.         # 1. Inicializa la semilla
  11.         for (my $i = 0; $i < $longitud; $i++) {
  12.                 push @semilla, $inicio;
  13.         }
  14.  
  15.         # 2. Genera las variaciones
  16.         while (not $fin_generacion) {
  17.                
  18.                 # Almacena la variación (copia de semilla)
  19.                 my @variacion = @semilla;
  20.                 push @resultado, \@variacion;
  21.                
  22.                 # Intenta incrementar la semilla
  23.                 my $incremento = 0;     # falso
  24.                 my $i = 0;
  25.                 while ($i < $longitud and not $incremento) {
  26.                        
  27.                         if ($semilla[$i] == $fin) {
  28.                                 $semilla[$i] = $inicio;
  29.                         }
  30.                         else {
  31.                                 $semilla[$i]++;
  32.                                 $incremento = 1; # verdadero
  33.                         }
  34.                         $i++;
  35.                 }
  36.                 if (not $incremento) {
  37.                         $fin_generacion = 1; # verdadero       
  38.                 }
  39.         }
  40.  
  41.         # 3. Retorna el resultado
  42.         return @resultado;
  43. }
  44.  
  45.  
  46. my @resultado1 = variaciones(0, 9, 2);
  47.  
  48. foreach my $variacion_ref (@resultado1) {
  49.  
  50.         my @variacion = @{$variacion_ref};
  51.         print "(", join(", ", @variacion), ") ";
  52. }
Coloreado en 0.001 segundos, usando GeSHi 1.0.8.4


Entonces, a ver si me he aclarado... Esa condición es verdadera porque estás negando una variable que tiene valor 0, ya que según perl doc, el número 0, las cadenas '0' y "", la lísta vacía "()" y el "undef" son todos falsos en contexto booleano, por lo tanto podríamos decir que negativo y negativo = positivo.

¿Es así o estoy liado todavía?
Avatar de Usuario
Hamtaro
Perlero nuevo
Perlero nuevo
 
Mensajes: 4
Registrado: 2015-11-19 17:34 @773

Re: Búsqueda exhaustiva en Perl

Notapor explorer » 2017-01-22 09:50 @451

En efecto, not niega el sentido de verdad de una expresión, así que not de un valor falso da como resultado un valor verdadero.
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
Avatar de Usuario
explorer
Administrador
Administrador
 
Mensajes: 14486
Registrado: 2005-07-24 18:12 @800
Ubicación: Valladolid, España


Volver a Básico

¿Quién está conectado?

Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 0 invitados

cron