[Programación] Re: [Programación] Re: [Programació n] Transformar algoritmo en pseudolenguaje a perl (aca me doy...)

[Nicolás Aimetti]

Pequeño error ...

#5) Ordenar con qsort A lexicográficamente por el campo "a2" ahora

@A = sort { $a->[1] <=> $b->[1] }  @A; #mal!!!

@A = sort { $a->[1] cmp $b->[1] }  @A; #ahí es lexicograficamente...

Saludos,
         Nicolás.

Nicolás Aimetti wrote:
> Bueno... aca me puse a ver el algoritmo...
> 
> Faltaría el paso 7, al que se lo ve más peludo...(y el 6.1)
> 
> #!/usr/bin/perl -w
> 
> use strict;
> 
> my @A = ( #una simple lista, que contiene otras listas...
>         [ 1, undef],   #A[0].a1 = 1, A[0].a2 = indefinido aun
>         [ 4, undef],   #A[1].a1 = 4, A[1].a2 = indefinido aun
>         [ 8, undef],   #etc...
>         [ 10, undef],
>         [ 12, undef],
>         [ 3, undef],
>         [ 4, undef],
>         [ 12, undef],
> );
> 
> #supongo una  F / F(x) = x*x  , o sea, tomo como que F es x al cuadrado.
> 
> @A = map { [ $_->[0], $_->[0]**2 ] } (sort { $a->[0] cmp $b->[0] } @A);
> 
> #ahora A es nuestro vector de entrada...
> 
> #empezamos con el agoritmo...
> 
> #1) ya esta ordenada lexicograficamente segun a1, aunque esto no es 
> #necesario por como esta implementado el paso 2.
> 
> #2) Busca la cantidad de elementos lexicográficamente diferentes en el
> #   campo "a1"
> 
> #en perl esto se hace asi, es mas comodo, y lo recomienda larry wall...
> 
> my %diferentes = ();
> @diferentes{ map { $_->[0] } @A } = ();
> my $cont2  = scalar keys %diferentes; #esto tampoco es necesario 
> #estrictamente.
> 
> #3) Crear T1[1..cont2] // para guardar todos los "a1" diferentes... con
> #   el TAD {a1,f} donde f es la frecuencia de apariciones de a1... se 
> inicia
> #   siempre T1[k].f<-0
> 
> # lo hago ala perl...
> my @T1 = map { my $actual=$_ ;  [ $_ , scalar (grep { $_->[0] == $actual 
> } @A ) ] } (keys %diferentes);
> 
> #4) Ordenar con qsort T1 numéricamente por el campo "f"
> #   (no especifica si descendiente o ascendiente)
> 
> @T1 = sort { $a->[1] <=> $b->[1] }  @T1;
> 
> #5) Ordenar con qsort A lexicográficamente por el campo "a2" ahora
> 
> @A =sort { $a->[1] <=> $b->[1] }  @A;
> 
> #6) Crear la matriz binaria A[1..2*cont2] inicada en cero.
> # Entiendo que debe ser una matriz de esta forma>
> # | 0 1 0 0 1 |
> # | 0 0 0 1 0 |
> # para cont2 = 5, o sea una matriz de 2x5 con solo ceros y unos.
> # de esto no estoy seguro así que paro acá... no se bien que significa 
> el 1..2
> # de todas formas lo dejoimplementado.
> # llamo a A con la letra M para no confundirlo con el A anterior.
> 
> my @M = ( ([(0) x $cont2]) x 2 );
> 
> #mostramos lo que tenemos hasta ahora...
> 
> print "A = (\n";
> print "\t",join(',',@$_),$/  for @A ;
> print ")\n";
> 
> print "T1 = (\n";
> print "\t",join(',',@$_),$/  for @T1 ;
> print ")\n";
> 
> print "M = (\n";
> print "\t",join(',',@$_),$/  for @M ;
> print ")\n";
> 
> _END_
> 
> 
> Saludos,
>         Nicolás.
> 
> Horacio Castellini wrote:
> 
>> Holas.... Pido una ayuda para transformar el siguiente algoritmo escrito
>> en pseudo código a lenguaje perl... ya que hay cosas que desconozco...
>> como que debo cargar antes de usar qsort y otras funciones de
>> biblioteca...
>>
>> Entrada el vector vectores A[1..N]  donde los elementos son un TAD 
>> {a1,a2} (estructura de datos) tal que A[i].a2=F(A[i].a1), pude haber
>> elementos repetidos y la función no es inyectiva... Salida una matriz
>> binaria (en representación vector), donde solo imprimo los elementos no
>> nulo, se inicia toda con ceros. (si ya sé que es complejo y no le
>> estudié la complejidad para sacarle el N**p... pero no es relevante eso)
>> ===================================================================
>> 1) Ordenar lexicográficamente A[1...N] de acuerdo al campo "a1".
>> 2) Busca la cantidad de elementos lexicográficamente diferentes en el
>> campo "a1"
>>
>> cont2<-0
>> para i<-1 hasta N-1 hacer
>>     si A[i].a1!=A[i+1].a1 entonces cont2<-cont2+1 finsi
>> finpara
>>
>> 3) Crear T1[1..cont2] // para guardar todos los "a1" diferentes... con
>> el TAD {a1,f} donde f es la frecuencia de apariciones de a1... se inicia
>> siempre T1[k].f<-0
>>
>> 3.1) para i<-1, j<-2,T1[1]=A[1].a1 hasta N-1 hacer
>>     si A[i].a1!=A[i+1].a1 entonces         T1[j]<-A[i+1].a1         
>> j<-j+1
>>     sino
>>         T1[j-1].f<-T1[j-1].f+1
>>     finsi
>> finpara
>>
>> 4) Ordenar con qsort T1 numéricamente por el campo "f"
>>
>> 5) Ordenar con qsort A lexicográficamente por el campo "a2" ahora
>>
>> 6) Crear la matriz binaria A[1..2*cont2] inicada en cero.
>> 6.1) crear bandera auxiliar p[1..2]
>>
>> 7)
>>
>> para i<-1 hasta N-1 hacer
>>     si A[i].a2=A[i+1].a2 entonces
>>         para j<-1 hasta cont2 hacer
>>             si A[i].a1=T1[j].a1 entonces
>>                 p[1]=j
>>                 parar_bucle_j
>>             finsi
>>         finpara
>>         para j<-1 hasta cont2 hacer
>>             si A[i+1].a1=T1[j].a1 entonces
>>                 p[2]=j
>>                 para_bucle_j
>>             finsi
>>         finpara
>>         si p[1]!=p[2] entonces
>>             B[N1*p[1]+p[2]]<-1
>>             B[N1*p[2]+p[1]]<-1
>>         finsi
>>     finsi
>> finpara
>>
>> listo la salida es la matriz (en representación vector) B simétrica...
>> =====================================================================
>>
>> Alguna sugerencia para llevarlo a código perl... se agradece...
>>
>> Horacio.
>>
>>
>>     
>>
>>     
>>        
>> ___________________________________________________________ 1GB 
>> gratis, Antivirus y Antispam Correo Yahoo!, el mejor correo web del 
>> mundo http://correo.yahoo.com.ar
>> _______________________________________________
>> Programacion mailing list
>> Programacion@lugro.org.ar
>> http://www.lugro.org.ar/mailman/listinfo/programacion
>>
> 
> _______________________________________________
> Programacion mailing list
> Programacion@lugro.org.ar
> http://www.lugro.org.ar/mailman/listinfo/programacion
>