S.P.O.K
Versión Actual: v1.0.4
Simple Production Of Keys es una herramienta de cracking de contraseñas la cual implementa un algoritmo altamente eficiente para la generación de diccionarios de palabras formadas a partir de un alfabeto personalizable. La tool ha sido codeada en C++11 en GNU/Linux Fedora 24 x86_64, pero es multiplataforma.
ANTES DE NADA: Recomiendo leer el paper de mi investigación sobre este ámbito, ya que podreís encontrar ideas muy positivas y vanguardistas a parte de ver las entrañas de mi herramienta como son: las definiciones matemáticas, implementación y diseño, benchmark, coste operacional, escenarios de cracking, ahorro y comparativas con métodos tradicionales. Os invito a meteros en mi cabeza por unos minutos ;) (El paper está en Inglés y consta de 16 páginas).
Una vez invitados a leer el paper, si aún no lo habeís leído, el método de S.P.O.K ahorra un 6% comparado con el método tradicional de generación de palabras de longitud i,j generándo todas las palabras entre i y j usando sólo las de longitud j. En la sección de ideas futuras un metodo del 94% de ahorro es comentado. La versión Release en este mismo momento genera 2.5 mil millones de palabras por minuto en mi pc al escribir en fichero.
Ahora veremos que funcionalidades aporta la herramienta:
- Modo Verbose para imprimir el total de palabras por minuto, segundo y el tamaño escrito sobre el tamaño final del diccionario (ver fórmulas matemáticas en el paper).
- Modo de generación de palabras escritas a un diccionario. Por defecto genera todas las palabras de longitud 1 hasta 5 (utilizando sólo las palabras de longitud 5 (ver paper)). Si no se especifica se imprimen las words por pantalla (para uso de pipe por ejemplo).
- Modo customizable de alfabeto. Por defecto es abcdefghijklmnopqrstuvwxyz.
- Modo customizable de intervalo de generación de palabras. Permite especificar la longitud i,j de las palabras a generar utilizando sólo las palabras de máxima longitud.
- Modo de hasheado de palabras escritas a un diccionario. Si se especifica este parámetro y el modo verbose esta presente, se utilizará la fórmula matemática correspondiente para calcular el tamaño del diccionario. La herramienta permite hashear cada palabra con 1, 2 o 3 primitivas siendo estas: MD5, SHA-1 y SHA-256.
- Modo de guardado y carga de sesiones. Esta joyita os permite cerrar la herramienta durante su ejecucción sin preocupaciones guardando todo el input especificado y la última palabra generada. Al volverla abrir se retomará el progreso anterior. Tampoco generará palabras repetidas que ya hayan sido guardadas (ver paper).
Si después de emplear la herramienta o leer el paper quereís colaborar escribid aquí. También para reportar bugs: kub0x@elhacker.net
Cualquier duda sobre uso -> leer el paper ya que tiene su propia sección de uso aunque la misma herramienta incluye un apartado de help al no introducir ningún parametro.
Link al PAPER -> https://github.com/FreeJaus/gea-PRISM/blob/master/Research/spok_v.1.0.3.pdf (falta upgradear a 1.0.4, coming soon)
Link al SOURCE -> https://github.com/FreeJaus/gea-PRISM/tree/master/Programming/SPOK
Link descarga PROYECTO+SOURCES+EJECUTABLE GNU/LINUX -> https://github.com/FreeJaus/gea-PRISM/releases/tag/v.1.0.4
USUARIOS DE WINDOWS: Lo he compilado satisfactoriamente en 32bit pero al ser incapaz de encontrar las librerías y .lib de OpenSSL para x64, la versión para Windows tendrá que esperar.
Linkar con librerías: libssl, libcrypto, libpthread (En Linux). En Windows con las de OpenSSL bastaría.
Saludos, disfrutadlo y sed buenos ;)
Cita de: kub0x en 26 Abril 2017, 08:41 AM
Hola NEBIRE,
quisiera saber que tan eficiente es tu algoritmo para generar diccionarios, para comparar tiempos con el mío y eso.
Me he tomado la molestia de crear un pequeño Snippet en C++11 basado en conversión a base-n donde n es la longitud del charset. Me parece infeciente tener que iterar todo el keyspace en forma de long pero bueno.
Ten en cuenta que le he añadido un hilo para escribir el buffer en el fichero, sino se quedaría esperando hasta escribir todo el contenido. Escribir en el fichero en cada iteracción es un waste de syscalls.
.....
Generar todas las palabras formadas por el alfabeto (26 chars) de longitud 6.
real 0m19.649s
user 0m18.579s
sys 0m2.722s
Donde el mio tarda entre 10s y 12s aproximadamente:
real 0m11.876s
user 0m10.819s
sys 0m2.803s
Si tienes algo de tiempo pásame un code definitivo que guarde las palabras en un fichero, lo testeare en Fedora a ver si difiere mucho del benchmark que te acabo de presentar.
P.D= Luego esta el maskprocessor que lo hace en 6-7 segs, para mí el más rápido que existe en CPU.
Un saludo!
Bueno, yo separé en efecto la parte de generar las permutaciones del hecho de escribirlo a fichero.
De hecho es ineficiente (e inútil, si el propósito no es otro que probarlo) escribirlo a fichero... siempre sería preferible escribir una API, a la que se pueda llamar y pedir generar (por ejemplo), 1millón de claves a partir de la siguiente (recibida) y que entregue el array por referencia en memoria... Hablamos de que la idea final, sería lógicamente usar las claves en algún programa. Por tanto el coste de escribir a fichero, leer de fichero y espacio ocupado es nulo. Esto sólo debería hacerse con propósitos de prueba... supongo que me tniende sperfectamente.
Tengo varias versiones, ya que me fascina idear soluciones diferentes para un mismo problema. Pero te hablaré de dos versiones básicas... bueno 3...
--------------------------------------
A - En esta la idea básica es la simplicidad del algoritmo.
Y en ella se genera cada clave por completo, simplemente convirtiendo un número decimal (base numérica 10) en la base numérica x, siendo x el tamaño del diccionario (pongamos 26, si el alfabeto fuere por ejemplo A-Z). Es decir esta es la misma que tu has descrito más arriba y que veo en el código...
--------------------------------------
B - En esta otra, la idea básica es buscar velocidad, por supuesto tampoco debe ser muy complejo, ya que sino queda reñido también con la velocidad´.
Así la complejidad subyace sólo en la dificultad de enteder el algoritmo (a pelo, si no se dieran explicaciones).
Entonces para el caso, ni se genera un array de claves. Es la forma más eficiente para usarlo en el propio programa (destinado a probar las claves 'donde fuere').
Esto es, se genera una sola clave y es esa misma la que se va modificando. Ya que en efecto, la diferencia entre una clave y la siguiente solo es (casi siempre) 1 sólo carácter es superfluo generar de nuevo el resto de caracteres de la clave. Por lo tanto generar la nueva clave, cambia casi siempre 1 sólo carácter, lo que dispara la velocidad de cálculo respecto del anterior por 6 (para un tamaño de clave de 6)... algo más al tener en cuenta que tampoco lo almacenamos en un array de claves, aunque por simplicidad en vez de tomarlo como string, es un array de bytes/chars.
-----------------------------------------------------
C - El tercer algoritmo, es más simplificado aún y más veloz que cualquiera de los otros. En realidad usa cualquiera previo, pero éste está diseñado para claves muy largas...
La idea básica es que: 4+4=8: 4+3=7; 5+4=9, o 6+6=12...
Pongamos el caso de una clave de largo 8 caracteres... Luego si generamos pongamos un array para las claves de 4 caracteres (26^4= 456.976) tan sólo algo menos de medio millón, esto se puede generar en apenas una décima de segundo...
Así el paso 1º de este algoritmo es llamar a otro algoritmo, para que genere un array de claves manejable.
El segundo paso, es doble bucle, en ambos se usa el array generado, y la clave generada no se almacena como array (26^8= unos 208mil millones), tal como pasa en el algoritmo B, es para velocidad.
Este doble bucle, simplemente concatena las dos partes actuales.
Inicio bucle Externo:
Por cada ClaveExt en ArrayClaves
Inicio bucle Interno:
Por cada claveInt en ArrayClaves
ClaveActual = claveExt concat claveInt
// Usar desde aquí la clave que se acaba de generar para lo que se precisa...
Llamada a funcionX(Claveactual)
Fin bucle
fin bucleComo se ve en este tercer algoritmo, generar una clave, se reduce a concatenar dos medias partes. Puede optimizarse mucho, si se usan funciones de copia de memoria, también evitando la creacción y destrucción de strings, o arrays...
Así ClaveActual debería ser una instancia que se crea una sola vez en todo el algoritmo y que se reutiliza una y otra vez. De hecho podemos ver que si ArrayClaves tiene un tamaño de medio millón (500.000), entonces claramente se veque en el bucle interno, siempre estamos concatenando (copiando ClaveExt, a pesar de que sabemos que no va a variar en el próximo medio millón de veces),
Entonces una varicación mejorada del algoritmo sería:
Inicio bucle Externo:
Hacer sitio a claveActual para que sea del tamaño requerido
Por cada ClaveExt en ArrayClaves
Inicio bucle Interno:
Copiar a Izqierda de ClaveActual, ClaveExt
Por cada claveInt en ArrayClaves
Copiar a Derecha de ClaveActual, ClaveInt
// Usar desde aquí la clave que se acaba de generar para lo que se precisa...
Llamada a funcionX(Claveactual)
Fin bucle
fin bucleEs decir ahora hacemos una concatenación diferida en dos veces...
Otra variación si hacemos una API, que debiera entregar un array de claves de tamaño 8, conllevaría generar el array de claves de solo 4 caracteres, en claves de tamaño 8, dejando así hueco 4 caracteres (a derecha por ejemplo, y que son reutilizados en cada ciclo del bucle Interno), para rellenar en este doble bucle, y donde el bucle interno, sería una adaptación del algoritmo "B" (o sea encajarlo aquí, para hacer la variación de 1 sólo carácter en cada ciclo para generar una clave, en vez de copiar en cada cuiclo los x caracteres de la derecha.
Este algoritmo "C", tien su complejidad, sólo en la forma de adaptación, para hacerlo versátil y que pueda por tanto generar claves de tamaño X, partiendo siempre de la generación de arrays de largo 2,3,4 y 5, desde 2+2, hasta 5+5 y separado si la clave es mayor de 10, para 3+4+4 hasta 5+5+5, etc....
Es decir separando si se quiere hacer doble bucle, triple, bucle, cuádruple bucle, etc...
Si tamañoClaves es menor que 11 luego
doble bucle
O si tamañoClaves es menor que 15 luego
Triple Bucle
O si Tamañoclaves es menor que 20 luego
cuadruple Bucle
en otro caso
mesanje: no se ha previsto para claves demás de 20 caracteres
fin si----------------------------------
Ahora mismo, no puedo hacer una prueba de velocidad, ya que tengo algunas operaciones calculando y le llevarán parte de la noche (las pruebas no reflejarían el rendimiento real si el procesador está trabajando al 80%), pero mañana, hago las pruebas que me reclamas y al efecto, limpio el código y cambio nombres de variables para facilitar su entendimiento...
(si creo recordar, de memoria, que poco tiempo atrás, quizás un mes o así, probé a generar con un alfabeto de 26 caracteres (A-Z), para un tamaño de clave de 7 caracteres... lo que proporciona algo más de 8 mil millones y tardó prácticamente unos 5 minutos, es decir aprox. 1.600.000.000 claves por minuto. (en un equipo del 2008, y con una versión hecha en VB6, al caso lo reharé en VB-2010, que es lo que tengo en casa). Dado que el algoritmo anunciado como "A", es la idea básica que tu has hecho, y que el algoritmo "C", está suficientemente descrito, pondré el código del algoritmo "B"...
Saludos...
Hola NEBIRE gracias por tu tiempo y compartir las tres opciones.
En mi proyecto utilizo la el 2º ya que parto de una cadena donde los caracteres son iguales (primer caracter del charset) y luego permuto el último hasta que llega al caracter final del charset, así reinicio el último y permuto el anterior. Obviamente infinitamente mejor que la primera.
Sin embargo me ha llamado el interés la opción 3 que comentas. Hace tiempo estuve pensando en ella, pero la descarte por la facilidad con la que visualizaba en 2ndo. ¿Básicamente se trata de concatenar dos keyspace iguales para hacer su doble?
Y sobre todo el benchmark 1.6*10^9 por min esta genial para un equipo de ese año, pero en tal caso, ¿las claves estaban siendo escritas al disco? Dudo que sea tan rapido con un disco que es una tartana. Mi mejor benchmark son 1.2*10^9 por min con más de 10GB de escritura por minuto en un SSD semi decente con un i5 ya viejuno.
Para acabar, mi tool es capaz de guardar secuencias de longitud inferior es decir si le pongo 3,7 a partir de la secuencia de 7 genero el resto. Así no tengo que hacer las de 3, luego 4 (como se verá en el 2ndo benchmark). El alg de subsecuencias esta ultra optimizado, vamos que respeta una fórmula matematica iterativa para no gastar en ciclos. Anteriormente en la v.1.0.1 me daba igual que ciclara siempre pero porque tenía otras cosas en mente.
Ayer compartí contigo unos tiempos de ejecucción de la herramienta maskprocess VS mi herramienta SPOK. Bueno después del port a C y muchas otras optimizaciones, lo vuelvo a repetir:
Palabras de longitud 6 con charset [a-z]:
Spok:
real 0m6.884s
user 0m5.101s
sys 0m2.226s
maskprocessor:
real 0m6.478s
user 0m2.224s
sys 0m2.010s
Ahora viene lo bueno, maskprocessor también genera secuencias basadas en intervalos de length, es decir secuencias desde 4 hasta 7. Pero SPOK le gana pues con las de 7 hace el resto de sub secuencias:
time ./mp64.bin -i 4:6 ?l?l?l?l?l?l -o 1.txt
real 0m9.672s
user 0m2.324s
sys 0m2.183s
time ./spok -g 1.txt -i 4,6
real 0m7.019s
user 0m5.245s
sys 0m2.603s
Con secuencias de length 8 y usando charset hexadecimal (36GB):
time ./mp64.bin --custom-charset1=0123456789ABCDEF ?1?1?1?1?1?1?1?1 -o 1.txt
real 2m13.783s
user 0m37.507s
sys 0m41.316s
time ./spok -g 1.txt -i 8,8 -c 0123456789ABCDEF
real 2m10.155s
user 1m24.198s
sys 0m40.658s
Vamos que SPOK ha resultado ser tan bueno como maskprocessor, herramienta del team de HashCat en CPU. Estoy contento de que la tool esté preparada para competir.
Si quieres pasáme un code en C o C++ te lo compilo bajo Linux y vemos que tal corre escribiendo en mi disco. Ahora mismo en Windows me sería imposible :/ Sigo teniendo curiosidad por si el benchmark que hiciste lo hiciste logeando en disco o solo haciendo bruteforce.
Saludos!
Tengo pendiente mirar lo que hiciste y subiste en GitHub...
Esta mañana antes de marcharme al trabao, hice la prueba y tardaba solo 187segundos, básicamente eleva a 2.666millones de claves por segundo...
Y sí, es sin escribir claves a disco. Ya he mencionado, que es estéril guardar un diccionario a disco, el tiempo necesario para ello es gigantesco comparado con el cálculo, además del espacio gigante que requieren. Cuando se precisa usar un diccionario, y más tarde se interrumpe, basta guardar la secuencia actual (última usada) y luego es relativamente fácil volver a ese punto y continuar. Esto hace inútil tener que requerir un diccionario en disco (un diccionario gigantesco, tampoco pasa nada por tener alguno de unos pocos cientos de Mb.)
Es común ver a alguien 'presumir' de tener un diccionario de nosecuantos GB. Yo cuando oigo decir eso, me apena, por que de lo que está presumiendo (sin saberlo) es de ignorancia.
Los dicionarios en fichero tienen un uso muy restringido, mejor dicho, si quien lo hace lo entiende debería saber que su uso debe restringirse a probar la validez del algoritmo y a casos como: "Diccionarios con las 10.000 claves más usadas en internet.txt", "dicionarios con las claves por defecto de los router 1990-2020.txt", etc... es decir donde no existe una secuencia combinatoria, sino que directamente son conocidas y 'misteriosamente' siguen siendo útiles...
No te preocupes, el código entre VB y C es apenas insignificante, de todos modos con los comentarios que adjunte, podrás entenderlo sin problemas y migrarlo a tu propio código...
Cita de: NEBIRE en 27 Abril 2017, 16:25 PM
Y sí, es sin escribir claves a disco. Ya he mencionado, que es estéril guardar un diccionario a disco, el tiempo necesario para ello es gigantesco comparado con el cálculo, además del espacio gigante que requieren. Cuando se precisa usar un diccionario, y más tarde se interrumpe, basta guardar la secuencia actual (última usada) y luego es relativamente fácil volver a ese punto y continuar. Esto hace inútil tener que requerir un diccionario en disco (un diccionario gigantesco, tampoco pasa nada por tener alguno de unos pocos cientos de Mb.)
Así es, en la herramienta SPOK puedes guardar el estado donde dejaste la ejecucción resumiendo la composición del diccionario desde la última palabra generada. Esto se hace después de introducir el buffer al fichero, se coge la última palabra del buffer (la de mayor longitud). Para no repetir subsecuencias (cuando i < j) idee una comprobación para la señalización.
Estoy contigo, hay que crear particionados de los diccionarios o crear una regla de composición que no sea muy masiva. ¿Tu programa printea las secuencias solamente entonces por pantalla?
El tema es que logear words en SPOK no es muy costoso debido al multi thread para que la copia del buffer pasada por referencia se escriba en el file mientras se siguen permutando los caracteres. El algoritmo de permutaciones si quito la parte de logear pues es ultra rápido, quizá edite este post para poner esta parte, ahora ando liado :/.
Saludos!
Sí, saco por pantalla los resultados. Cuando creo o modifico un algoritmo, lo que hago es volcar parcialmente a un listbox para verificar que está operando correctamente. Estando seguro de que funciona bien, deja de ser necesario visualizarlo.
Yo de tí (ya que te has tomado la molestia de hacr toda la operatoria para volcar a fichero), lo dejaría opcional y limitando la cantidad... por ejemplo, para un tamaño de clave de hasta 5 caracteres, y si las claves son más largas, limitarlas a x millones de claves a partir del intérvalo que el usuario decida... así si prefiere volcarlo todo a fichero es cosa suya, y la pérdida de tiempo que experimente será decisión suya propia.
--------------------------
Ahora me pongo a pasarlo a VB-2010, no usaré ningún método que resulte extraño, ni palabras clave que hagan inentendible a alguien que no conozca el entorno de Visual Studio... aunque seguramente me extienda en facilidades (generalmente superfluas, pero que siempre se agradecen).
He establecido un nuevo record, el modo verbose está claro que interfiere en los cálculos por minuto así que quitándolo se ve mucha mejoría.
Palabras de longitud 8 con charset hexadecimal:
time ./spok -g 1.txt -i 8,8 -c 0123456789ABCDEF
real 2m12.130s
user 1m29.713s
sys 1m0.373s
Es decir 1.950.337.075 palabras por minuto escritas al .txt usando solo un buffer, para que no se solapen al pasar al thread y no haya una reserva de memoria significante. Ganando a maskprocessor por un par de segundos en este contexto. Que decir que el paper ya ha quedado obsoleto en términos de diseño, programación y benchmark.
Como bien dices, dejaré la opción de guardar diccionarios opcional así con la de printear y un pipelina ya puedes hacer cosillas. Para particionar diccionarios se puede especificar una palabra de comienzo o cargar la sesión anterior.
EDIT: Liberada versión v1.0.3
Ejemplo de multibuffer:
real 2m8.108s
user 1m31.130s
sys 0m59.931s
Palabras por minuto: 2.011.568.658. He añadido un comando nuevo para especificar si el usuario quiere usar multi buffer o no. En los SSD tiene sentido usarlo ya que si se usa mono buffer tendrá que esperar a que la copia este vacia. Notese que el buffer principal siempre estará siendo llenado independientemente de si se necesita escribir en disco o no.
También he mejorado el verbose posicionándolo en el apartado de escritura de buffer, para no abusar las calls y ya por fin muestra los resultados reales de palabras por minuto 2.10^9, interesante sin duda. Optimizaciones varias (cambio de crono, ahorro de verificación parametro hash por cada ciclo etc..) y limpieza de código.
Saludos
Yo no me planteo guardarlos a disco. Algún diccionario con claves de 3-5 caracteres, y sólo para verificar que es correcto, es más que suficiente. Ya no te cuento, lo lento que sería sobre un disco duro...
Es estupendo... Seguramente puedas mejorarlo más, al menos la parte de generar las claves (que es en la que yo me centro y la que me importa... no veo práctico escribir a disco diccionarios muy grandes ni tampoco pretender usarlos (desde fichero) en algún programa, para tratar por fuerza bruta romper una contraseña).
Me falta por pasar un ejemplo con el tercer método que te explicaba, a ver si esta noche tengo un tiempito y puedo pasarlo y lo subo mañana...
Con las pruebas que he hecho, hasta el momento, para el 2 método, obtengo los siguientes resultados (las pruebas siempre sobre un diccionario completo de claves de 7 caracteres (el alfabeto de ejemplo, siempre es A-Z)), es decir: 8.031.810.176 claves:
- Implementado con bucles FOR: 53 segundos.
Esta implementación adolece de varios problemas y una ventaja:La ventaja es que permite operar con claves desde 1 hasta 16 caracteres.
Los problemas: Los bucles FOR, siempre son más lentos (especialmente cuando están anidados, para uno solo no importa demasiado). Es complejo establecer un punto inicial, de hecho aquí se considera como inicio siempre la clave más baja.
- Implementado con clases de modo recursivo: 155 segundos.
Esta implementación tiene la particularidad de que el código es más 'elegante'. enseña algo que mucha gente quizás no emplee o del que tenga nula noción; usar clases de forma recursiva (tal y como se haría con una función). Permite establecer de forma sencilla el estado inicial de comienzo (en cualquier clave deseada). En contra es más lento, fruto de la recursividad frente a la iteración. Otra ventaja es que el código es muy escueto.
Esta implementación no está limitado a un tamaño de clave, podría perfectamente señalarse una clave de 5000 caracteres, sin otro problema que el tiempo de procesado... (sin tener que cambiar absolutamente nada en el código, ni problemas de desbordamientos, ni nada).
- Implementado con bucles DO: 35 segundos. esto supone 229'5millones de claves por segundo, ó 13.700 millones de claves por minuto. Ya te adelanto que con el algoritmo3, esta cifra aumenta aún más...
El código es el equivalente al del bucle FOR, pero desde aquí, permite de un modo sencillo establecer el estado inicial (la clave desde la que empezar/continuar enumerando).
Recuerda que los valores siempre son para generar las claves (y teniendo en cuenta lo viejo de mi equipo: 9 años), no para escribir a disco. También hay que señalar que solo se usa un núcleo del procesador, desisto de crear un algoritmo que trabaje en paralelo con más de un núcleo, a fin de cuentas mi propósito no es llegar a usar los diccionarios, sino, solo dejar 'exangüe' al algoritmo generador...
Una particularidad muy interesante en todas estas implementaciónes del algoritmo2, es que cada carácter obtiene su propio alfabeto (de forma indirecta, tal como se explica a continuación)... aunque por defecto uno ponga A-Z, en realidad hay tres parámetros:
Valor minimo, ejemplo: AAAAAA
Valor Máximo, ejemplo: ZZZZZZ
Valor Inicial, ejemplo: GDAXCA
Esto permite que pueda indicar el valor mínimo y máximo de formas distintas, por ejemplo así:
Posiciones: 543210
------------------------------
Valor Minimo: A0ZD9A
Valor Máximo: ZZAK0Z
Entonces, implica que, tiene definido un alfabeto (en estos casos siempre basado en el ASCII)
El carácter '0': A-Z ---> 26 caracteres, incremento
El carácter '1': 9-0 ---> 10 caracteres (numéricos), decremento
El carácter '2': D-K ---> 13 caracteres incremento
El carácter '3': Z-A ---> 26 caracteres decremento
El carácter '4': 0-Z ---> 43 caracteres 0-9, 9-A, A-Z (10+7+26 si no he contado mal)
El carácter '5': A-Z ---> 26 caracteres.
La implementación del bucle FOR, no admite el parámetro "Valor Inicial", en los otros dos casos a la entrada garantiza (chequea y corrige), que el caracter en cada posición esté en el rango Min-Max del alfabeto que admite...
Antes de nada, acabo de publicar la v1.0.4 y pufff cada día me supero a mi mismo :D Podemos decir que SPOK gana a maskprocessor en performance. He portado la lógica de buffering y write a C teniendo MUY en cuenta los tamaños de buffer para escritura en disco y caché de CPU.
He eliminado el multi-threading para I/O en fichero ya que eligiendo sabiamente el tamaño de buffer es innecesario, oye no te irás a la cama sin aprender nada nuevo. Al parecer con un tamaño de entre 4KB - 2MB approx. existe un balance entre overhead en syscalls aprovechando cache y bloques de página del disco duro. A parte por cada sub secuencia completa re-calculo el tamaño de buffer, todo al milímetro.
[kub0x@prism maskprocessor-0.73]$ time ./mp64.bin ?l?l?l?l?l?l -o 1.txt
real 0m5.614s
user 0m2.333s
sys 0m2.153s
[kub0x@prism Release]$ time ./spok -g 1.txt -i 6,6
Using default charset.
Total storage needed: 2062.24 MB
All words of length 6,6 have been generated.
real 0m5.470s
user 0m3.351s
sys 0m1.612s
[kub0x@prism Release]$ time ./spok -g 1.txt -c 0123456789ABCDEF -i 8,8
Total storage needed: 36864 MB
All words of length 8,8 have been generated.
real 2m03.121s
user 1m0.428s
sys 0m33.678s
Vamos que ni multi buffer ni gaitas. Escritura síncrona con tamaño de buffer estrictamente basado en hardware
__________________________________________________________________________________________________
@NEBIRE: Buenos benchmarks, supongo que será el tiempo que tarda el algoritmo en generar sin printear, ya que I/O en stdin/out es costoso, ni maskprocessor lo handlea bien (tarda mucho mas que escribir en disco).
Me he animado a hacer el benchmark con tu ejemplo de charset A-Z y length fija de 7:
[kub0x@prism Release]$ time ./spok -g 1.txt -i 7,7
Using default charset.
Total storage needed: 61277.8 MB
All words of length 7,7 have been generated.
real 0m20.817s
user 0m20.764s
sys 0m0.010s
Ojo sin printear ni logear en disco, sólo ver cuanto tarda el método en generar todas las secuencias (unos 401.10^6 / sec). También hay que tener en cuenta la CPU que utilizo. He añadido la opción de printear sin logear en disco, basta con quitar el parametro -g o --generate del input, todo esto siguiendo tu consejo.
Por cierto me ha gustado tu enfoque sobre:
Cita de: NEBIRE en 1 Mayo 2017, 17:49 PM
Una particularidad muy interesante en todas estas implementaciónes del algoritmo2, es que cada carácter obtiene su propio alfabeto (de forma indirecta, tal como se explica a continuación)... aunque por defecto uno ponga A-Z, en realidad hay tres parámetros:
Valor minimo, ejemplo: AAAAAA
Valor Máximo, ejemplo: ZZZZZZ
Valor Inicial, ejemplo: GDAXCA
Esto permite que pueda indicar el valor mínimo y máximo de formas distintas, por ejemplo así:
Posiciones: 543210
------------------------------
Valor Minimo: A0ZD9A
Valor Máximo: ZZAK0Z
Entonces, implica que, tiene definido un alfabeto (en estos casos siempre basado en el ASCII)
El carácter '0': A-Z ---> 26 caracteres, incremento
El carácter '1': 9-0 ---> 10 caracteres (numéricos), decremento
El carácter '2': D-K ---> 13 caracteres incremento
El carácter '3': Z-A ---> 26 caracteres decremento
El carácter '4': 0-Z ---> 43 caracteres 0-9, 9-A, A-Z (10+7+26 si no he contado mal)
El carácter '5': A-Z ---> 26 caracteres.
Tengo pensado implementar cositas así tras optimizar todo, siempre me acuesto diciendo ya está optimizado pero cada vez saco algo :P Estaría bien que me sugirierás alguna característica más, he pensado en máscaras o combinaciones de múltiples diccionarios. Para ello hay que pensar que contraseñas elige la gente. Me molaría probar tus algoritmos también, sobre todo el algoritmo 3, ya que repito que el mio tiene pinta de algoritmo 2.
Algunos consejos para mejorar la velocidad de escritura a la unida de almacenamiento:
- El buffer siempre debería ser multiplo de 64, de hecho mucho mejor si es múltiplo exacto del tamaño de 1 sector de disco.
- También puedes lograr mejor velocidad de escritura, si desactivas la caché. Dado que solo es 1 única escritura y no lectura, si puedes desactivar (o hay alguna función específica en el lenguaje), que deshabilita la caché del S.O. no pierde tiempo en ello. A veces el S.O. (en win2 al menos), se empeña en hacer uso de la caché, aún cuando tú solo vayas a leer o escribir una única vez (por ejemplo porque vas a hashear uno o varios ficheros).
- Y deberías probar si lo admite la escritura síncrona, la asíncrona a veces conlleva un retraso por defecto. Aunque en un SSD este comportamiento, podría resultar diferente.
- Por último, para aumentar aún un poco la velocidad de escritura, yo te recomendaría que precalcularas el tamaño total en bytes que va a tener el fichero, y generar de antemano el fichero (en win2, esto es tan fácil como escribir el último byte del fichero (basta poner un 0), y actoseguido retornar el puntero de escritura al comienzo del fichero)... entonces se busca el espacio libre de una sola vez y trata de encontrarlo contiguo... si tiene que andar buscando espacio libre a medida que vas escribiendo, se demora más en buscar sectores libres, además es una búsqueda constante para 1 sector más... cuando se sabe el tamaño del fichero, es mejor siempre reservarlo al completo de una sola vez. Así hace una sola búsqueda, y si se da el caso de que ese tamaño existe contiguo, es muy, muy rápido.... si solo se reclama sector a sector, el S.O. te va asignando sectores libres entre medias de otros ficheros, aunque esto último en un SSD no tiene impacto, todavía la búsqueda de sectores libres (uno a uno), sigue teniendo un costo que se reduce notablemente cuando hay espacio suficiente y se le pide por completo, ya qe entonces trata de localizarlo contiguo...
Cita de: NEBIRE en 2 Mayo 2017, 17:34 PM
- El buffer siempre debería ser multiplo de 64, de hecho mucho mejor si es múltiplo exacto del tamaño de 1 sector de disco.
- También puedes lograr mejor velocidad de escritura, si desactivas la caché. Dado que solo es 1 única escritura y no lectura, si puedes desactivar (o hay alguna función específica en el lenguaje), que deshabilita la caché del S.O. no pierde tiempo en ello. A veces el S.O. (en win2 al menos), se empeña en hacer uso de la caché, aún cuando tú solo vayas a leer o escribir una única vez (por ejemplo porque vas a hashear uno o varios ficheros).
Antes de nada yo hago uso de dos buffers, bueno realmente visible es 1, es decir, el buffer principal que varía su tamaño (si hay subsecuencia desde i hasta j, i incrementa recordemos), todo esto recalculando para no hacer overflow cada vez que finaliza una subsecuencia. Con longitud fija pues chupado. Y luego tenemos el buffer del descriptor del fichero el cual es múltiplo de 64KB o 64 KB depende del OS. La primera opción la he tenido en cuenta a la hora de lidiar con el buffer del descriptor de fichero. En C++ no había forma más que heredando y haciendo mi propia implementación así que use la interfaz de I/O de C.
Así que cuando el buffer principal ha llegado a casi el límite se guarda en chunks de 64 al fichero. Aquí entra en juego el punto número 2, pues también probe que el descriptor no usara buffer, es decir, escribe al file lo más pronto posible, con setbuf es posible desactivar el buffer del stream. ¿Es esto a lo que te refieres con quitarnos la cache de en medio (creo que no)? Tampoco noté mucha mejoría. Otra idea con sentido que tuve fue apuntar el stream del fd al buffer principal y hacer un flush (escribir al device y limpiar), pero sigo sin saber porque eso no funciona, si tan loca la idea no es y usaría solo un buffer, pero bueno parece que solo las primitivas estilo fputs o fwrite funcionan.
Y sobre la tercera, bueno de las primeras cosas que hice antes de meterme a la progamación son los cálculos matemáticos (como queda retratado en el paper) del storage con hashing y de words, por lo tanto tengo acceso al tamaño en bytes del fichero destino, claro que para secuencias grandes será descomunal, en esto si que no había caído y gracias por la recomendación sin duda lo probaré.
Un saludo!
Esta semana he estado bastante ocupado (y el fin de semana con la familia), peor a ver si logro sacar tiempo y al menos expongo, de una u otra manera el código y comentarios y quizás al final, algo más...
p.d.: La caché de disco, son los búfferes que el S.O. puede mantener ocultos en memoria para subsecuentes (supuestos) accesos al fichero. Es muy posible que el propio S.O. detectando que se trata de un SSD, lo desactive dada su alta velocidad de acceso.
Aparte el propio hardware de la unidad puede mantener sus propios búfferes, tal que si se solicita una lectura/escritura de nuevo de un sector que no ha cambiado, lo entrega/ofrece desde/hacia el búffer en vez de desde/hacia la unidad. Es más habitual que existan búfferes de lectura que de escritura, por que es más habitual leer más de una vez el mismo sector que escribir sobre el mismo sector. Si se usa una cahcé hardware, mejor no desactivarlo (si fuera le caso que lo admitiera). Ése queda perfectamente claro que será eficiente, o de impacto nulo para nuestros propósitos (toda vez que opera en paralelo), no así con la cahcé software que comerá recursos en tiempo y para el propósito de una sola única lectura/escritura, supone un retraso.
Voy a ir poniendo código, aunque sea cada día un algoritmo... y los comentarios pertinentes.... al final, comprimo el proyecto y lo subiré a una pagina de descarga...
Tal como dije me he ceñido estrictamente a no usar clases o métodos complejos, que haga inentendible el código para alguien no versado en Net...
De entrada paso a explicar, que en cad algoritmo he tratado de desarrollarlo de la forma que me ha parecido más adecuada, para traerlo aquí y explicar detalles... esto supone que por ejemplo en alguno habrá muchos detalles previos al algoritmo, y en otros apenas nada, en unos las claves vendrás con 2 bytes por carácter y en otro con uno, en unos con un tipo de datos y en otro con otros... debe quedar claro en todo momento, que al final hablamos siempre de bytes y solo bytes, luego nadie debiera tener dificultad alguna (si conoce adecuadamente el lenguaje que acostumbra a usar), para convertirlo al tipo de datos que precise según el uso al que se destine. Por ejemplo, si alguien se empeña guardarlo a disco, guardar los caracteres con 1 solo byte por carácter ocupará la mitad de espacio que si lo guarda con 2 bytes por caracter... del mismo modo, si lo guarda a disco, prescindir de saltos de línea también ahorra espacio... Después de todo abrir un fichero de pongamos 1Gb. para leerlo, carece de sentido y por lo mismo, da igual que no sea legible y no se abara con un visor de texto o se use un editor hexadeciaml....
Dicho lo cual, vamos con el primero, el algoritmo-A.
El algoritmo-A, es el más simple de todos en cuanto a líneas de código y como dije es solo un cambio de base de numeración a la base cuyo tamaño representa el alfabeto usado. Es el algoritmo al que todo el mundo (que sepa un mínimo de programación debiera llegar...
- Su fuerte, la extrema sencillez de entenderlo... (y programarlo).
- Su defecto, que no es el más óptimo en cuanto a velocidad. Aún así, para pequeños diccionarios de hasta 5 caracteres (o incluso 6, dada la velocidad de los equipos de hoy día es suficientemente rápido si nios limitamos a un alfabeto de por ejemplo A-Z (entiéndase A-Z, como el rango de caracteres entre ellos dos: "A,B,C,D,E,F...,X,Y,Z").
Dado que este algoritmo es sencillo, me he parado en detalles extras, de los que he prescindido en los otros. También está profusamente lleno de comentarios sobre el código, en los demás he prescindido de tanto detalle.
Aquí una imagen de la interfaz, muy sencilla. Puede verse el selector de tamaño de las claves, el selector del conjunto de caracteres que formarán el alfabeto a permutar y el botón para realizar la tarea.
El conjunto de caracteres puede optarse por todo el ASCII (o una parte definiendo un punto de inicio y una cantidad de caracteres), o restringido a los caracteres: 0-9, A-Z, a-z, o cualquier combinación de ellas (pero siempre en el orden en que aparecen. También permite recibir un alfabeto personalizado (básicamente un array con los caracteres que se desee y en el orden que se quiera). Para el propósito de este texto es suficiente (me parece), pero cada cual que modifique a su gusto...
(http://i63.tinypic.com/1enzb6.png)
El código para este algoritmo, se resume en el código asociado a los eventos de la interfaz de usuario y una clase. Esta clase tiene otra interna (anidada), dedicada a generar el alfabeto. Se deja anidada solo por encapsulación, si un lenguaje no admite crear clases anidadas, igualmente se puede dejar fuera...
Vamos pués primero con el código de esta clase anidada:
Esta clase se la ha llamado: AlfabetoToUse
#Region "clase para generar el alfabeto"
''' <summary>
''' Facilitador para crear el alfabeto a usar.
''' </summary>
''' <remarks></remarks>
Public Class AlfabetoToUse
Private p_Alfabeto(0 To 255) As Byte ' 08 bits
Private p_Sizealfabeto As Short ' 16 bits
''' <summary>
''' Facilita la generación automática del alfabeto, basado en un valor que identifica claramente el conjunto que se toma.
''' </summary>
''' <remarks></remarks>
Public Enum CaracteresUsadosEnAlfabeto
''' <summary>
''' Este valor o inferior es un valor ilegal.
''' </summary>
''' <remarks></remarks>
ALFABETO_VALOR_ILEGAL_MENOR = -2
''' <summary>
''' El cliente pasa el array con el alfabeto que desea usar.
''' </summary>
''' <remarks></remarks>
ALFABETO_CUSTOM = -1
''' <summary>
''' El alfabeto es todo el espacio ASCII.
''' </summary>
''' <remarks></remarks>
ALFABETO_ASCII = 0
''' <summary>
''' El alfabeto contiene los números.
''' </summary>
''' <remarks></remarks>
ALFABETO_09 = 1
''' <summary>
''' El alfabeto contiene las mayúsculas (no 'Ñ' ni otros caracteres extendidos).
''' </summary>
''' <remarks></remarks>
ALFABETO_AZ_UPPERCASE = 2
''' <summary>
''' El alfabeto contiene las minúsculas (no 'ñ' ni otros caracteres extendidos).
''' </summary>
''' <remarks></remarks>
ALFABETO_AZ_LOWERCASE = 4
''' <summary>
''' El alfabeto es tomado parcialmente del ASCII
''' </summary>
''' <remarks></remarks>
ALFABETO_OFFSET = 8
''' <summary>
''' Este valor o superior es un valor ilegal.
''' </summary>
''' <remarks></remarks>
ALFABETO_VALOR_ILEGAL_MAYOR = 9
End Enum
Public ReadOnly Property Alfabeto() As Byte() ' 8 bits
Get
Alfabeto = p_Alfabeto
End Get
End Property
Public ReadOnly Property SizeAlfabeto As Short ' 16 bits
Get
SizeAlfabeto = p_Sizealfabeto
End Get
End Property
''' <summary>
''' Por defecto, el alfabeto es el ASCII y el tamaño 256.
''' </summary>
''' <remarks>Si las claves han de ser imprimibles como texto, se perderán aquellos caracteres no imprimibles. en tal caso definir el alfabeto a usar.</remarks>
Public Sub New()
'Me.New(0)
p_Sizealfabeto = 256
Call ConstruyeAlfabeto(CaracteresUsadosEnAlfabeto.ALFABETO_ASCII)
End Sub
''' <summary>
''' Facilita la construcción del alfabeto basado en un valor de enumeración.
''' </summary>
''' <param name="Tipo">Pueden unirse entre sí los conjuntos: 0-9, A-Z y a-z (pero será en ese orden)</param>
''' <remarks>Aunque el valor 'custom' consta en la enumeración, es el cliente qien debe expresar en ese caso el conjunto de caracteres que se emplea.</remarks>
Public Sub New(ByVal Tipo As CaracteresUsadosEnAlfabeto)
If (ConstruyeAlfabeto(Tipo) = False) Then
Err.Raise(-1, , "El 'tipo' recibido, no consta en la enumeración y/o no permite deducir el conjunto de caracteres a tomar para generar el alfabeto. Introduzca un valor en el rango admitido.")
End If
End Sub
''' <summary>
''' Permite declarar un alfabeto parcialmente indicando un desplazamiento sobre la tabla ASCII
''' </summary>
''' <param name="Comienzo">Punto de comienzo desde donde se toma el alfabeto.</param>
''' <param name="SizeAlfabeto">Cantidad de caracteres que se toman del alfabeto. Si es preciso se trunca.</param>
''' <remarks>Ejemplo: para generar un alfabeto que use solo las mayúsculas se llamaría con New(65,26)</remarks>
Public Sub New(ByVal Comienzo As Byte, Optional ByRef SizeAlfabeto As Byte = 255)
If (Comienzo < 255) Then
If (SizeAlfabeto + Comienzo > 255) Then
SizeAlfabeto = (255 - Comienzo)
End If
p_Sizealfabeto = (SizeAlfabeto + 1)
Call ConstruyeAlfabeto(CaracteresUsadosEnAlfabeto.ALFABETO_OFFSET, Comienzo)
Else
Err.Raise(-1, , "Si el comienzo es el byte 255, el tamaño del diccionario es 1 y solo genera una clave. ...¿qué sentido tiene???")
End If
End Sub
''' <summary>
''' Permite al usuario introducir su propio alfabeto.
''' </summary>
''' <param name="AlfabetoCustom">Array con el alfabeto del usuario.</param>
''' <remarks>OJO: No se verifica la validez del alfabeto, se supone correcto.</remarks>
Public Sub New(ByRef AlfabetoCustom() As Byte)
p_Alfabeto = AlfabetoCustom
p_Sizealfabeto = p_Alfabeto.Length
If (p_Sizealfabeto = 0) Then
Err.Raise(-1, , "El alfabeto del usuario no puede estar vacío, o tener solo 1 elemento. ...¿con qué fin???")
End If
End Sub
''' <summary>
''' Recrea el alfabeto basado en la enumeración recibida
''' </summary>
''' <param name="Tipo">Enumeración que señala qué caracteres se tomarán para el alfabeto. Los conjuntos 0-9, A-Z y a-z, pueden aunarse entre sí.</param>
''' <returns>Devuelve True si el tipo recibido es existente o subyacente en la enumeración</returns>
''' <remarks>No se debe invocar el tipo 'custom'</remarks>
Friend Function ConstruyeAlfabeto(ByVal Tipo As CaracteresUsadosEnAlfabeto, Optional ByVal Offset As Byte = 0) As Boolean
Dim k As Short, n As Short
n = 0 ' por claridad
If (Tipo > CaracteresUsadosEnAlfabeto.ALFABETO_CUSTOM) And (Tipo < CaracteresUsadosEnAlfabeto.ALFABETO_VALOR_ILEGAL_MAYOR) Then
Select Case Tipo
Case CaracteresUsadosEnAlfabeto.ALFABETO_ASCII, CaracteresUsadosEnAlfabeto.ALFABETO_OFFSET
For k = Offset To (p_Sizealfabeto + Offset) ' 0 to 255, si es ASCII
p_Alfabeto(n) = k
n += 1 ' n=k si offset=0
Next
Case Else
p_Sizealfabeto = 0
' Intervienen los números?
If ((Tipo And CaracteresUsadosEnAlfabeto.ALFABETO_09) = CaracteresUsadosEnAlfabeto.ALFABETO_09) Then
For k = 48 To 57
p_Alfabeto(n) = k
n += 1
Next
End If
' intervienen las mayúsculas?. Si sí, añadirlas (tras lo previo)
If ((Tipo And CaracteresUsadosEnAlfabeto.ALFABETO_AZ_UPPERCASE) = CaracteresUsadosEnAlfabeto.ALFABETO_AZ_UPPERCASE) Then
For k = 65 To 90
p_Alfabeto(n) = k
n += 1
Next
End If
' Intervienen las minúsculas?. Si sí, añadirlas (tras lo previo)
If ((Tipo And CaracteresUsadosEnAlfabeto.ALFABETO_AZ_LOWERCASE) = CaracteresUsadosEnAlfabeto.ALFABETO_AZ_LOWERCASE) Then
For k = 97 To 122
p_Alfabeto(n) = k
n += 1
Next
End If
p_Sizealfabeto = n
End Select
Return True
Else
Return False ' el tipo recibido no permite deducir el conjunto de caracteres a tomar para generar el alfabeto.
End If
End Function
End Class
#End Region
- En dicho código, aparece primero la declaración de variables a nivel de clase, luego una enumeración, que define que tipo de alfabeto se va a construir (si se ha de construir).
- Luego aparecen de propiedades de solo lectura (El alfabeto y el tamaño del alfabeto), ambas propiedades serán las que se lean cuando se use el algoritmo.
- Luego hay 4 constructores de clase, para permitir invocar el tipo de alfabeto de que se quiere generar en base a las opciones que permite.
- Finalmente hay un método que construye el alfabeto.
La idea de esta clase, es que el alfabeto sea definido una sola vez y pueda ser usada como parámetro para enumerar. Así se evita que mientras se enumere se modifique el alfabeto (o el tamaño del mismo) y dé lugar a errores durante la ejecución. Ya que se construye y luego es de solo lectura, no puede modificarse mientras se usa.
Pasamos ahora al código de la clase (llamada cBaseNum) que hospeda a ésta recién descrita (AlfabetoToUse):
''' <summary>
''' Clase: Combinatoria-Alfabeto-Diccionario. Crea diccionario (in situ), mediante combinatoria.
''' </summary>
''' <remarks>No se ha previsto en ningún momento almacenar a fichero el diccionario creado</remarks>
Public Class cBaseNum
' siempre contiene 256 bytes, aunque luego no se usen todos.
Private p_Alfabeto(0 To 255) As Byte ' 08 bits sin signo
Private p_Sizealfabeto As Short ' 16 bits con signo
Private s_LargoClaves As Byte
Private s_MaxPermutaciones As UInt32 ' 64 bits sin signo
#Region "clase para generar el alfabeto"
''' <summary>
''' Facilitador para crear el alfabeto a usar.
''' </summary>
''' <remarks></remarks>
Public Class AlfabetoToUse
'... AQUI: va el código d ela clase anterior (que está anidada). Si un lenguej no permite anidar clases, dejarla fuera al mismo nivel y listo.
End Class
#End Region
Public Structure PermutarDatosImprescindibles
Public Charset As AlfabetoToUse
Public LargoClaves As Byte
Public PermutacionInicialStr As String
Public PermutacionInicialLng As Long
End Structure
''' <summary>
''' Enumera todas las permutaciones.
''' </summary>
''' <param name="Datos">Alfabeto que se va a usar, Tamaño de las claves a generar y valor inicial.</param>
''' <remarks>El método usado en este algoritmo es la conversión entre sistemas de numeración.</remarks>
Public Sub Enumerar(ByRef Datos As PermutarDatosImprescindibles)
Dim Clave() As Byte
Dim k As UInt32, n As Short ' contadores de bucle
Dim v As UInt32, x As Byte, Numchars As Short
Dim Crono As Single
Crono = TimeOfDay.Ticks ' ticks a la hora actual
With Datos
p_Alfabeto = .Charset.Alfabeto
p_Sizealfabeto = .Charset.SizeAlfabeto
s_LargoClaves = .LargoClaves
s_MaxPermutaciones = (p_Sizealfabeto ^ s_LargoClaves)
Numchars = ((s_LargoClaves * 2) - 2)
ReDim Clave(0 To Numchars + 1)
If (.PermutacionInicialLng < 0) Then .PermutacionInicialLng = 0
If (.PermutacionInicialStr.Length > 0) Then
' FALTA: código para convertir la clave a la enésima permutación.
' es el proceso inverso al seguido en el algoritmo y debiera facilitarse como una función pública.
' k= EnesimaPermutacion(.PermutacionStr)
Else
k = .PermutacionInicialLng
End If
Do
v = k
n = Numchars
Do
x = (v Mod p_Sizealfabeto)
Clave(n) = p_Alfabeto(x) ' convertir el byte a char.
v \= p_Sizealfabeto ' división entera.
n -= 2
Loop While (n >= 0)
' USAR la clave desde aquí
' llamada a FuncionX(Clave)
k += 1
Loop While (k < s_MaxPermutaciones)
End With
Crono = ((TimeOfDay.Ticks - Crono) / 10000000) ' ticks a la hora actual, menos los de comienzo= ticks invertidos en la tarea.
MessageBox.Show(Crono.ToString & vbCrLf & s_MaxPermutaciones.ToString)
End Sub
End Class
- La clase es bien sencilla, al inicio la declaración de variables, el alfabeto y el tamaño del mismo, por razones de rendimiento es preferible copiarlos a esta... Para que quede claro se deja constancia del tipo de datos que VB.NET son, para facilitar la conversión a otro lenguaje (tal como allí se designe el tipo equivalente).
- Luego viene la clase anidada (para generar el alfabeto).
- Detrás viene definida una estructura con los siguientes 4 elemntos:
----- La instancia de clase del alfabeto creado previamente y que se usará. éste contiene dos cosas, el alfabeto (charSet) a usar y el tamaño de dicho alfabeto).
----- El tamaño de las claves que queremos generar
----- Un posible punto de inicio, para enumerar las claves (en forma de una clave (string). Esta parte no se ha implementado...
----- Un posible punto de inicio, para enumerar las claves (en forma de la enésima clave (número)).
- Finalmente el método para Enumerar (generar las permutaciones). Recibe como único parámetro, la estructura que se acaba de explicar.
Inicia el crono 8para calcular el tiempo invertido en generarlo) y acto seguido toma de la clase AlfabetotoUse, tanto el alfabeto como su tamaño, así una posterior modificación de dicha clase, mientras se está permutando, no afecta al trabajo en curso evitando errores...
Luego unas asignaciones y cáclulos elementales, tras lo cual viene finalmente el bucle de la enumeración.
Las permutaciones se consiguen cambiando la base numérica desde un valor decimal (base 10), a la base numérica cuyo valor es el tamaño del alfabeto... dicho valor se usa como el desplazamiento dentro del alfabeto para seleccionar el carácter con que se representa en dicha base numérica.
Y eso es todo lo que respecta a la clase... al término de la enumeración indica el tiempo transcurrido.
Queda el código de la interfaz de usuario... Se ha omitido en la interfaz la designación tanto de un alfabeto custom, como un alfabeto basado en el ASCII, definido por un punto de inicio y una cantidad de caracteres... (queda al esfuerzo de los interesados, modificar y/o ampliar características).
Dado lo sencillo de la interfaz, las explicaciones dadas y el código a continuación creo superfluo extenderme más... pero si alguien tiene alguuna duda, que pregunte.
Public Class frm1 ' la ventana, formulario...
Dim alfa As cBaseNum.AlfabetoToUse
Dim SizeAlfabeto As Short
Dim TipoAlfabeto As cBaseNum.AlfabetoToUse.CaracteresUsadosEnAlfabeto
''' <summary>
''' Por defecto, al inicio el alfabeto es A-Z (26 caracteres)
''' </summary>
''' <param name="sender"></param>
''' <param name="e"></param>
''' <remarks></remarks>
Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
TipoAlfabeto = cBaseNum.AlfabetoToUse.CaracteresUsadosEnAlfabeto.ALFABETO_AZ_UPPERCASE
SizeAlfabeto = 26
End Sub
''' <summary>
''' Selección del tipo de alfabeto a usar
''' </summary>
''' <param name="sender"></param>
''' <param name="e"></param>
''' <remarks>Se han ligado los eventos de todos los checkbox a este método</remarks>
Private Sub CheckBox1_CheckedChanged(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles CheckBox1.CheckedChanged, CheckBox2.CheckedChanged, CheckBox3.CheckedChanged
TipoAlfabeto = 0 : SizeAlfabeto = 0
If (CheckBox1.Checked = True) Then
TipoAlfabeto = cBaseNum.AlfabetoToUse.CaracteresUsadosEnAlfabeto.ALFABETO_09
SizeAlfabeto = 10
End If
If (CheckBox2.Checked = True) Then
TipoAlfabeto = (TipoAlfabeto Or cBaseNum.AlfabetoToUse.CaracteresUsadosEnAlfabeto.ALFABETO_AZ_UPPERCASE)
SizeAlfabeto += 26
End If
If (CheckBox3.Checked = True) Then
TipoAlfabeto = (TipoAlfabeto Or cBaseNum.AlfabetoToUse.CaracteresUsadosEnAlfabeto.ALFABETO_AZ_LOWERCASE)
SizeAlfabeto += 26
End If
' si se deseleccionó todo, por defecto será todo el rango ASCIIasigna
If TipoAlfabeto = 0 Then SizeAlfabeto = 256
GroupBox1.Text = "Tamaño del diciconario: " & SizeAlfabeto.ToString
End Sub
''' <summary>
''' Reunir todos los datos y llamar a la enumeración.
''' </summary>
''' <param name="sender"></param>
''' <param name="e"></param>
''' <remarks></remarks>
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim datos As cBaseNum.PermutarDatosImprescindibles
Dim cad As New cBaseNum
' Reunir los parámetros en una estructura, único parámetro del método enuerar de la clase...
With datos
.Charset = New cBaseNum.AlfabetoToUse(TipoAlfabeto) ' construir el alfabeto
.LargoClaves = NumericUpDown1.Value ' tamaño de las claves a generar.
.PermutacionInicialLng = -1 ' cambiar si se quiere iniciar en una secuencia distinta de la primera.
.PermutacionInicialStr = "" ' no se ha implmenetado en la clase el inicio dado una clave concreta...
End With
cad.Enumerar(datos)
MessageBox.Show("Finalizada la enumeración.")
End Sub
End Class
Como se puede apreciar, no se incluído ningún método complejo, ni nada especial que impida entender el código aún sin tener idea de VB.NET.
--------------------
Mañana saco un tiempito, y paso con el algoritmo-2, hice 3 versiones (piondré uno de cada vez), cada uno con sus características, para dar riqueza de experiencia y aprendizaje...
Continuamos...
El segundo algoritmo, es básicamente un esquema de revólver, exactamente tal y como es un cuentakilómetros.
La idea básica detrás de ello, es que hay un bucle por cada carácter. Y ese bucle se encarga de iterar exclusivamente ese carácter, al final del mismo (o antes de entrar) se pone el valor inicial de nuevo (esto es automático en los bucles for, ya que en ellos se declara explícitamente dichos valores de inicio y fin).
En cada bucle, por tanto se establece el valor actual en la posición que ocupa en el término permutado.
Cuando se alcanza el bucle interior, en cada iteración de éste, se obtiene ya la permutación completa.
La ventaja de este algoritmo (genérico), sobre el declarado en el mensaje previo, es que no requiere con cada permutación generar cada vez todos sus caracteres. La forma más clara de visualizar este algorimo, se refleja en un cuentakilómetros...
De este algoritmo expondré tres variaciones, la primera basada en un bucle for.
- La ventaja de éste algoritmo sobre el anterior es la velocidad gracias a evitar, la continua generación de caracteres que no cambia en la siguiente iteración.
- Su desventaja (como bucle for), la dificultad de establecer el punto inicial desde el que comenzar si no es, el comienzo de la permutación. Las variantes posteirores para este algoritmo solventan este problema.
Ahora ya vayamos con el código, para el mismo se ha provisto también una ventana y una clase que realiza el trabajo. Si bien la ventana será la misma para las tres variantes del algoritmo.
Aquí una vista de la interfaz, muy sencilla y el resultado tras la ejecución.
(http://i65.tinypic.com/2mcbyc1.png)
El código de la interfaz, es bien sencillo, básicamente se instancia la clase, y se invoca el método enumerar con los parámetros que aparecen en los textos. En esta versión, no se usa el valor de estado inicial, o dicho de otra manera, el valor de comienzo está fijado al comienzo de la iteración.
Public Class frm2 ' la ventana, formulario
Private buc As New cBucAni ' instancia a la clase usada
Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
Dim Min() As Byte, Max() As Byte
Dim z As Decimal
Min = StringToByteArray(TextBox2.Text) ' Valor mínimo: Ejemplo: "AAAAZ"
Max = StringToByteArray(TextBox3.Text) ' Valor final, Ejemplo: "ZWZZA
z = buc.EnumerarFor(Min, Max)
End Sub
Private Function StringToByteArray(ByRef Txt As String) As Byte()
Return System.Text.Encoding.Unicode.GetBytes(Txt)
End Function
End Class
- El código, primero se crea una instancia de la clase (llamada: "cBucAni", son bucles anidados, no me he complicado con el nombre).
- Luego el código del botón. Primero llama a una función para obtener los bytes (2 bytes por carácter) respectivos a los textos de límite de la enumeración. Luego invoca el método enumerar.
- La función devuelve la cantidad de permutaciones (aunque luego no usamos ese valor para nada). El tipo de datos Decimal, es un tipo de 96bits, + 1 bit de signo... Puede ponerse un tipo de bytes (64bits), después de todo, no es estrictamente necesario devolver la cantidad de permutaciones.
Vayamos con el código de la clase para esta variante del algortimo-B:
Public Class cBucAni
Public Function EnumerarFor(ByRef sMin() As Byte, ByRef sMax() As Byte) As Decimal
Dim a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p As short ' 16bits con signo
Dim Max(0 To 15) As Short
Dim Min(0 To 15) As Short
Dim Inc(0 To 15) As Short
Dim SizeClave As Short ' Tamaño de las claves (cantidad de caracteres que contienen)
Dim ClavePermutada() As Byte ' Clave generada en bytes.
Dim t As Byte
Dim z As Decimal, Crono As Single
Dim txt As String
Crono = TimeOfDay.Ticks ' ticks desde medianoche hasta la hora actual
z = CalcularNumPermutaciones(sMin, sMax)
If (z < 0) Then
Return -1
Exit Function
Else
SizeClave = sMin.Length
ReDim ClavePermutada(0 To SizeClave - 1)
For t = 0 To (SizeClave - 2) Step 2
Max(n) = sMax(t)
Min(n) = sMin(t)
n += 1
Next
For t = 0 To n - 1 '((SizeClave \ 2) - 2)
If (Max(t) > Min(t)) Then
Inc(t) = 1
ElseIf (Max(t) < Min(t)) Then
Inc(t) = -1
End If
Next
For t = n To 15 'SizeClave To 15
Inc(t) = 256
Min(t) = -1
Max(t) = -1
Next
End If
For p = Min(15) To Max(15) Step Inc(15)
If (p >= 0) Then
ClavePermutada(30) = p
End If
For o = Min(14) To Max(14) Step Inc(14)
If (o >= 0) Then
ClavePermutada(28) = o
End If
For n = Min(13) To Max(13) Step Inc(13)
If (n >= 0) Then
ClavePermutada(26) = n
End If
For m = Min(12) To Max(12) Step Inc(12)
If (m >= 0) Then
ClavePermutada(24) = m
End If
For l = Min(11) To Max(11) Step Inc(11)
If (l >= 0) Then
ClavePermutada(22) = l
End If
For k = Min(10) To Max(10) Step Inc(10)
If (k >= 0) Then
ClavePermutada(20) = k
End If
For j = Min(9) To Max(9) Step Inc(9)
If (j >= 0) Then
ClavePermutada(18) = j
End If
For i = Min(8) To Max(8) Step Inc(8)
If (i >= 0) Then
ClavePermutada(16) = i
End If
For h = Min(7) To Max(7) Step Inc(7)
If (h >= 0) Then
ClavePermutada(14) = h
End If
For g = Min(6) To Max(6) Step Inc(6)
If (g >= 0) Then
ClavePermutada(12) = g
End If
For f = Min(5) To Max(5) Step Inc(5)
If (f >= 0) Then
ClavePermutada(10) = f
End If
For e = Min(4) To Max(4) Step Inc(4)
If (e >= 0) Then
ClavePermutada(8) = e
End If
For d = Min(3) To Max(3) Step Inc(3)
If (d >= 0) Then
ClavePermutada(6) = d
End If
For c = Min(2) To Max(2) Step Inc(2)
If (c >= 0) Then
ClavePermutada(4) = c
End If
For b = Min(1) To Max(1) Step Inc(1)
If (b >= 0) Then
ClavePermutada(2) = b
End If
For a = Min(0) To Max(0) Step Inc(0)
ClavePermutada(0) = a
' Usar Permutación desde aquí:
'txt = System.Text.Encoding.Unicode.GetString(ClavePermutada)
' call FuncionX(ClavePermutada)
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
Next
' Devolver resultados
Crono = ((TimeOfDay.Ticks - Crono) / 10000000) ' ticks hasta la hora actual, menos los de comienzo= ticks invertidos en la tarea.
txt = System.Text.Encoding.Unicode.GetString(ClavePermutada)
MessageBox.Show("Tiempo: " & Crono.ToString & vbCrLf & "Permutaciones: " & z.ToString & vbCrLf & "Ultima clave Permutada: " & txt)
Return z
End Function
' ....
End Class
Como se ve la clase contiene exclusivamente un metodo (EnumerarFor), que admite dos parámetros. El comienzo de la iteración para cada carácter y el final de iteración para cada carácter.
Una particularidad extra de este algoritmo (en las 3 variantes), es que se ha modificado la forma del alfabeto que utiliza (ya vimos en el algoritmo previo diferentes formas de expresar un alfabeto). Con sólo esos dos parámetros, en realidad estamos definiendo un alfabeto exclusivo para cada carácter, además de dejar claro, el largo de las claves que se van a generar (tan largas como caracteres tienen ambos parámetros. De hecho es requisito que ambos parámetros sean igual de largos.
Esto hace popsible que si deseamos generar claves en la forma:
AAAA-000-xx:QQQQ
ZZZZ-999-pp:DDDD
Puede entenderse que para los 4 primeros caracteres (a la izquierda), el rango del alfabeto está en: A-Z, luego viene un guión fijo, los dos siguientes caracteres fijan su alfabeto al rango x-p, el siguiente carácter está fijo al carácter ":" y los 4 últimos caracteres usan un alfabeto en el rango Q-D (nótese que es decreciente)...
Partiendo de esta funcionalidad, es fácil deducir, otra donde delimitamos la entrada de un texto circunscrito a determinado rango de valores, para cada carácter y declaramos no válidos el resto.
Esto facilita enormemente la definición de alfabetos para cada carácter, al no exigir explicítamente un array por cada carácter, y en cuanto al código, implementar esto en el algoritmo, del mensaje previo (el definido como algoritmo A), sería complejo y la cantidad de comparaciones para delimitarlo, lo harían extremadamente lento, en éste en cambio, no existe penalización alguna (salvo una verificación inicial prácticamente sin coste en realción al tiempo empleado en la enumeración) ni exige arrays de alfabetos...
Eso sí, la definición de este alfabeto, establece el orden ASCII, es decir si definimos un inicion y fin como:
00000000
ZZZZZZZ
En realidad estamos definiendo un rango entre los caracteres ASCII '0' y 'Z', no del 0-9 y A-Z... y justamente se suceden en el orden en que aparecen en el ASCII... si no fuera el caso, sería necesario un Array que defina los caracteres y el orden que ocupan (o varios si cada carácter tuviera su propia evolución).
- Tras acceder a la enumeración, lo primero es contar las permutaciones resultantes, y una verificación de validez de los parámetros. Para ello se invoca una función que está en un módulo privado del proyecto pero común a todo el proyecto. Se explica más abajo dicha función, aquí baste decir que si los parámetros no son consecuentes, devuelve un valor negativo que fuerza la salida de la función y que debe interpretarse como error...
- Luego se genera un array de bytes (2 por cada carácter) del mismo tamamo que los parámetros, que será donde se deposite el resultado de la enumeración... y que se irá sobrescribiendo una y otra vez...
- Lo siguiente es establecer los valores adecuados para el inicio, final del bucle y dirección de avance (puede ir tanto desde A-Z, como desde Z-A, por tanto el bucle puede aumentar o reducir en unidades.
- Lo siguiente, si se mira bien, es que hay 16 bucles, esto implica que con la misma función, sin cambios, podríamos generar claves de largo entre 1 y 16. Las claves se generan en los bucles más internos, y quedan sin usar los bucles más externos, para estos se fijan Min, Max e Incremento a valores que hacen que el bucle se ejecute una sola vez y por tanto no alteran ni se cae en errores.
- Finalmente vienen los bucles, extreamadamente sencillos y que puede verse cómo actúan exactamente como los cuentakilómetros.
Se ha recurrido a señalar cada bucle, como a,b,c,d,e...p, el bucle 'a', es el más interno y sobre la clave produce el carácter 0, el más externo (el bulce 'p'), produce el último carácter (si usan claves de 16 caracteres.
A continuación adjunto el código de la función que se invoca a al entrada de la función enumerar... y que tiene por objeto contar el número de permutaciones que se van a generar y verificar un par de cosas: que ambos parámetros tienen el mismo tamaño de caracteres (podría añadirse una verificación de delimitación del tamaño mínimo (1) y máximo (16) caracteres, que no se realiza), puede ocurrir un error si el número de permutaciones sobrepasa el rango de 96 bits (12 bytes, pués se ha declarado la cuenta con un tipo de datos
Decimal). Nótese que los bucles no generarán error por desbordamiento, opera simplemente con 8 y 16 bits (byte y short) y el tamaño, simplemente es tiempo que tarda. Si se prefiere evitardesbordamiento incluso para 96 bits, puede omitirse la cuenta de permutaciones y devolverlo en formato de string en la forma X a la Y (26^7), (36^5), (256^16), etc...
''' <summary>
''' Calcula el número de permutaciones totales.
''' </summary>
''' <param name="Min">Define el valor mínimo para cada carácter.</param>
''' <param name="Max">Define el valor máximo para cada carácter.</param>
''' <returns>El número de permutaciones totales. Un valor negativo, si hubo errores.</returns>
''' <remarks>Cada carácter tiene su propio alfabeto, circunscrito al rango Min-Max, para el índice que ocupa.</remarks>
Friend Function CalcularNumPermutaciones(ByRef Min() As Byte, ByRef Max() As Byte) As Decimal
Dim k As Short, j As Short, n As Decimal, v As Short
k = Min.Length
If (k <> Max.Length) Then
MsgBox("Los 2 arrays deben ser del mismo tamaño: Min y Max.")
Return -2
Exit Function
End If
Try
n = 1
For j = 0 To k - 2 Step 2
v = Max(j) ' impide que la resta entre dos bytes (a continuación), de error por desbordamiento, si el resultado es menor de 0.
v = (v - Min(j))
n = (n * (Math.Abs(v) + 1)) ' ABS= Valor absooluto del número (esto es, ignora el signo y lo toma como positivo).
Next
Return n
Catch ' de ocurrir un error se espera que sea desbordamiento... (de n).
Return -1
End Try
End Function
Finalmente comentar que el código (el del algoritmo de permutación, no esta última función), pero resuelve el caso y es más rápido que el algortimo presentado anteriormente (en el mensaje previo), en contra tiene que no es cómodo establecer un punto de inicio distinto al inicio de las permutaciones, y también que el código no es muy elegante.
Y eso es todo por hoy...
En el próximo mensaje proveeré una variante que resuelve ambas cosas a costa de una pérdida de eficiencia en velocidad, debida a que recurro a un modelo recursivo, frente a este iterativo, además la recursividad será sobre una clase, no sobre un método.
---------------------
p.d.: Un tick en NET es la diezmillonésima parte de 1 sg. por ello al final se divide entre 10 millones, para tener el tiempo en segundos.
Voy con la siguiente entrega...
En esta ocasión, trato las permutaciones con una clase que se llama recursivamente.
Otra clase (padre de ésta), hace la vez de bucle principal y es la que el cliente invoca externamente.
Como en el caso previo, se opera con cada carácter de una vez, por lo que igualmente aquí, cada carácter puede tener su propio alfabeto, exactamente en la smismas condiciones que el código del algoritmo previo.
En este caso además se provee la capacidad de establecer un estado inicial distinto del comienzo de la permutación. El código también resulta algo más elegante (que un montón de bucles FOR), sin embargo el rendimiento es menor, ya que la recursividad siempre es más lenta que la iteración, dado que con cada llamada, debe almacenarse en la pila el estado previo de la función de la que se sale.
En esta ocasión el código se muestra en 4 apartados:
- El de la interfaz del usuario (como respuesta a pulsar el botón). La ventana
- El de la clase instanciada desde la interfaz. clase cPermut
- El código en un módulo (compartido con el proyecto). módulo mComun
- El de la clase instanciada desde la clase pública. clase Ciclos
Respecto de la interfaz, es la misma que aparece en el mensaje previo (ver la imagen), solo que aquí se expone el código relativo al botón que aparece en el centro...
Public Class frm2 ' la ventana, formulario
Private perm As New cPermut
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
Dim ClaveActual() As Byte, Min() As Byte, Max() As Byte
Dim z As Decimal
ClaveActual = StringToByteArray(TextBox1.Text) ' Valor inicial: "ABXFD"
Min = StringToByteArray(TextBox2.Text) ' Valor mínimo: Ejemplo: "AAAAZ"
Max = StringToByteArray(TextBox3.Text) ' Valor final, Ejemplo: "ZWZZA
z = perm.Enumerar(ClaveActual, Min, Max)
End Sub
End Clasee
El código es muy simple.
Una referencia a la clase que alberga la funcionalidad, y luego el trabajo del botón, donde convierte a un array de bytes los 3 textos que la función encargada de permutar requiere como parámetros: El valor inicial, el valor mínimo y el valor máximo (de las permutaciones, respectivamente). Finalmente se llama a a la función enumerar de la clase. Devuelve el número de permutaciones y como se decía en el mensaje previo, no es estrictamente necesario... podría devoverse simplemente un buleano.
Ahora vamos por el código de la clase cPermut:
Esta clase es pública y contiene a la otra anidada, así es privada para esta clase. Si un lenguaje no admite clases anidadas, no importa, basta ponerla al mismo nivel que esta clase, pero dejarla privada, para ser instaciada sólo a nivel de proyecto y listo...
El código d ela clase anidada, se pone aparte, para facilitar entender cada parte y por si uno tiene que ponerlo como clases sueltas e independientes (o hacer cambios cómodamente).
Public Class cPermut
Public Enum ValoresDeIncremento
VALOR_DECREMENTO = -1
VALOR_INCREMENTO = 1
End Enum
#Region "Accesible para las clases 'Ciclo'. "
Private Shared Fin As Boolean ' Control de fin de la enumeración (mejor que forzar una comparación).
Private Shared SizeClave As Short ' Tamaño de las claves (cantidad de caracteres que contienen)
Private Shared ClavePermutada() As Byte ' Clave generada en bytes.
Private Shared Max() As Byte ' En cada índice se deja el valor máximo.
' Ejemplo: 78,78,78,78,78,78,78,78 --> Todos iguales.
' Ejemplo: 45,37,22,65,90,90,90,90 --> Cada uno distinto.
Private Shared Min() As Byte ' En cada valor se deja el valor mínimo.
' Ejemplo: 00,00,00,00,00,00,00,00 --> Todos iguales.
' Ejemplo: 00,18,05,22,12,12,00,08 --> Cada uno distinto.
' Establece datos operativos.
' Establecer un tamaño, no necesariamente borra el previo.
Private Shared Sub EstablecerPuntoInicial(ByRef Abc() As Byte, ByRef vMax() As Byte, ByRef vMin() As Byte, Optional ByVal SinRepeticion As Boolean = False)
SizeClave = (Abc.Length - 2)
ClavePermutada = Abc
Max = vMax : Min = vMin
Fin = False
End Sub
#End Region
Private p_Ciclos As New Ciclos ' Crea una instancia de la clase anidada (privada)
Private Alfabeto As String
Private vMin() As Byte
Private vMax() As Byte
Private UltimaPalabra As String
' Enumera todas las permutaciones desde la combinación de entrada con los límites establecidos.
' Devuelve el número de permutaciones totales
Public Function Enumerar(ByVal ClaveActual() As Byte, ByVal Min() As Byte, ByVal Max() As Byte) As Decimal
Dim z As Decimal, Crono As Single
Crono = TimeOfDay.Ticks ' ticks a la hora actual
z = CalcularNumPermutaciones(ClaveActual, Min, Max)
If (z < 0) Then
Return -1
Exit Function
End If
' Establece el estado inicial y final de las permutaciones
Call EstablecerPuntoInicial(ClaveActual, Max, Min) ', SinRepeticion)
' Prepara los valores iniciales en cada clase 'ciclo'
p_Ciclos.SetEstadoInicial()
' Iniciar las permutaciones de entre los límites fijados
Do
p_Ciclos.Mutar()
' Usar Permutación desde aquí:
' call FuncionX(Permutacion)
Loop While (Fin = False)
' Devolver resultados
Enumerar = z
Crono = ((TimeOfDay.Ticks - Crono) / 10000000) ' ticks a la hora actual, menos los de comienzo= ticks invertidos en la tarea.
MessageBox.Show("Tiempo: " & Crono.ToString & vbCrLf & "Permutaciones: " & z.ToString)
End Function
Comentando el código:
- Primero aparece una enumeración, básicamente sirve para saber si el alfabeto para un carácter es creciente o decreciente, es decir, puede indicarse el alfabeto para un carácter tanto A-Z, como Z-A, en cuyo caso debe ser decrementado.
- Después delimitado en una region (una región no es código, solo es de carácter informativo, para agrupar código e indicar que está relacionado (por el comentario que se acompaña), aparecen varios campos "Private Shared", que señala que no son accesibles fuera d ela clase, pero que si son compartidos con las clases anidad que 'ésta' tuviere (de hecho tiene una, Ciclos...si se traduce a otro lenguaje y la clase ciclos debe quedar fuera, también este código debe quedar fuera y ser accesible tanto desde esta clase, como de cualquier instancia de Ciclos.
- En la misma región se ha incluído una función que establece el valor de esos campos. El detalle de esos valores se verá en la clase ciclos, ya que desde aquí sólo se establecen, no se opera con ellos.
- Luego llegamos a la función enumerar:
---- Como ya se explicó en el algoritmo previo (mensaje previo), pasando como parámetros los límites de la enumeración para cada carácter, es posible de forma sencilla delimitar el alfabeto, además para cada carácter (ver mensaje previo), en este además se adjunta un terce rparámetro, la claveActual desde donde continuar la permutación. Esto implica que podemos empezar donde queramos parar en la parte señalada como final, y en otra ocasión continuar desde donde se dejó y marcar otro punto como final...
---- Tras acceder a la función enumerar, lo primero es verificar que los parámetros son congruentes entre si, llamando a la función CalcularNumPermutaciones(,,,), aunque ya la vimos más arriba esta es ligeramente distinta, es una sobrecarga de la otra... De entrada se exige que tengan el mismo tamaño (que define el tamaño de las claves que se generan, así:
Actual: CCC
Minimo: AAA
Maximo: ZZZ
Declara que se van a generar claves de 3 caracteres, que para cada carácter su alfabeto será A-Z, y que la clave Inicial será CCC, por tanto se permutará desde esa clave.
Otro ejemplo:
Actual: C0CCXXCC
Minimo: A0AAZZAA
Maximo: Z9ZZAAZZ
Declara que se van a generar claves de 8 caracteres, que cada carácter tiene su propio alfabeto, para algunas es de A-Z, para otras de Z-A y para otra es de 0-9
Además, dicha función verifica (y trunca si procede) que la clave actual está en el rango fijado para el alfabeto de cada carácter, si no es así, se trunca (se fuerza), al valor límite... es decir si se pone estos parámetros como entrada:
Actual: AAA
Minimo: DDX
Maximo: ZZD
Dado que, inicio para los dos caracteres a la izquierda sean DD, trunca la clave actual para esos caracteres a DD, ya que AA, es menor que DD. Igualmente para el carácter a la derecha de la clave actual es Z, queda fuera de rango, pués empieza en X y finaliza en D, y A es menor, pasa a valer truncada 'D', así la clave actual finalmente sería: DDD
El código de esta función va debajo de estos comentarios...
---- Una vez validado los parámetros, se establecen los valores a los campos sobre los que la clase Ciclos, va a operar. Función: EstablecerPuntoInicial
---- Luego invoca a la clase ciclos, para establecer el estado inciial. Esto se explica más abajo al describir la clase Ciclos. (SetEstadoInicial)
---- Finalmente viene el bucle de enumeración, invocando un método de la clase Ciclos.Mutar , que hace la Permutación. Con cada llamada se genera una clave. Tras la vuelta, puede usarse la clave generada, luego si alcanzó el final de la permutación el bucle finaliza y se sale de la función.
Viene ahora el código de la sobrecarga de la función que verifica los parámetros de enumerar... se acaba de describir suficientemente ya el código de esta función:
Module mComun
' nota: ya hay una función del mismo nombre muy similar, pero con solo dos parámetros, cuyo código está más arriba, en otro mensaje...
''' <summary>
''' Calcula el número de permutaciones totales. Y garantiza que la clave actual esté dentro del rango, truncándolo cuando sea preciso.
''' </summary>
''' <param name="ClaveActual">Fija la clave actual de comienzo, dentro del rango.</param>
''' <param name="Min">Define el valor mínimo para cada carácter.</param>
''' <param name="Max">Define el valor máximo para cada carácter.</param>
''' <returns>El número de permutaciones totales. Un valor negativo, si hubo errores.</returns>
''' <remarks>Cada carácter tiene su propio alfabeto, circunscrito al rango Min-Max, para el índice que ocupa.</remarks>
Friend Function CalcularNumPermutaciones(ByRef ClaveActual() As Byte, ByRef Min() As Byte, ByRef Max() As Byte) As Decimal
Dim k As Short, j As Short, n As Decimal, v As Short
Dim x As Short, y As Short, z As Short
k = ClaveActual.Length
If ((k <> Min.Length) Or (k <> Max.Length)) Then
MsgBox("Los 3 arrays deben ser del mismo tamaño: Palabra, Min y Max.")
Return -2
Exit Function
End If
Try
n = 1
For j = 0 To k - 2 Step 2
x = ClaveActual(j)
y = Min(j)
z = Max(j)
v = (z - y)
If (v > 0) Then
If (x > z) Then
ClaveActual(j) = z
ElseIf (x < y) Then
ClaveActual(j) = y
End If
ElseIf (v < 0) Then
If (x > y) Then
ClaveActual(j) = y
ElseIf (x < z) Then
ClaveActual(j) = z
End If
End If
n = (n * (Math.Abs(v) + 1))
Next
Return n
Catch ' de ocurrir un error se espera que sea desbordamiento... sucederá si ponemos demasiados caracteres y un rango de alfabeto para ellos muy grande... depende de tales valores que se llegue a un desboramiento o no.
Return -1
End Try
End Function
End Module
Solo queda por comentar que al truncar un carácter se comprueba que límite supera, si supera el límite 'Max', se fija con el carácter 'Máx', si supera el límite 'Min', se fija el carácter con el carácter'Min'. Máx y Min, como extremos del alfabeto para ese carácter.
Finalmente vamos con el código de la clase Ciclos, que es quien realiza todo el trabajo 'sucio'...
'Public Class cPermut
' Se crean tantas instancias de esta clase como caracteres ha de tener la clave +1.
''' <summary>
''' Esta clase representa un sólo carácter en una posición dada de la clave. Y retiene los valores máximo y mínimo que puede alcanzar.
''' </summary>
''' <remarks>La clase se encadena al siguiente carácter a través de p_Next.</remarks>
Private Class Ciclos
Private p_Valor As Byte ' El valor actual del byte/carácter
Private p_Min As Byte ' El valor mínimo que puede alcanzarse (en el rango 0-255)
Private p_Max As Byte ' El valor máximo que puede alcanzarse (en el rango 0-255)
Private p_PosicionChar As Byte ' La posición que registra el 'Valor' de esta clase en el alfabeto.
Private s_Inc As Short ' el valor que se aumenta: -1 si es regresivo (Min mayos que Max), sino, es +1.
Private p_Next As Ciclos ' Referencia a la instancia que opera sobre el carácter á la izquierda de éste.
''' <summary>
''' Prepara los valores de inicio, fin e incremento para el 'carácter x' del alfabeto.
''' </summary>
''' <remarks>Se reinvoca a sí mismo, hasta asignar una instancia de la clase a cada carácter del alfabeto. Tras el carácter más a la izquierda asocia una instancia 'fin'.</remarks>
Public Sub SetEstadoInicial()
Dim niM As Byte, xaM As Byte
If (SizeClave >= 0) Then ' C - Examina Size y si es mayor o igual a cero:
p_PosicionChar = SizeClave ' A - se asigna el índice actual.
' B - Con el índice actual, tomar:
' el 'valor' actual y los límites 'Max' y 'Min'.
p_Valor = ClavePermutada(p_PosicionChar)
niM = Min(p_PosicionChar)
xaM = Max(p_PosicionChar)
s_Inc = Math.Sign(xaM - niM) ' esto devuelve = 0, -1, +1
If (s_Inc = 0) Then
p_Valor = niM : p_Min = niM : p_Max = niM ' El carácter es fijo en la clave.
Else
p_Max = xaM : p_Min = niM
End If
SizeClave -= 2 ' Z - Decrementa Size en 1
If (p_Next Is Nothing) Then ' Y - Si no existe,
p_Next = New Ciclos ' crea otra clase anidada 'Next' (que será las decenas, centenas, etc...)
End If
Call p_Next.SetEstadoInicial() ' X - Invoca su método 'Nuevo'.
' W - vuelve a sumar el size... para compararlo con 'fin'.
Else ' Si es menor que cero:
' Es el dígito a la izquierda del último reclamado,
' Su función es detectar el final de la enumeración.
' Se ponen los valores en la clase que intercepta el final de la enumeración.
p_PosicionChar = 255 ' Este valor detecta el final.
p_Min = 0 : p_Max = 0 : p_Valor = 0 ' necesario, porque si ya exisitía esta clase antes, podría tener valores...
p_Next = Nothing ' Z - Elimina (si existe) la clase anidada 'Next' y subsiguientes.
End If
End Sub
' Sumar ó restar 1.
''' <summary>
''' Incrementar ó decrementa el valor en una unidad y lo actualiza en la posición asignada. Si no alcanza el límite
''' </summary>
''' <remarks></remarks>
Friend Sub Mutar()
If (p_Valor = p_Max) Then
p_Valor = p_Min
If (p_PosicionChar < 255) Then ' se llegó a un dígito/carácter más alla del tamaño de la clave?
p_Next.Mutar()
Else
Fin = True
Exit Sub ' porque noo existe ese index en permutacion
End If
Else
p_Valor += s_Inc ' s_inc puede valer: +1, ó -1
End If
ClavePermutada(p_PosicionChar) = p_Valor
End Sub
' Elimina las clase anidadas de nivel superior (existentes previamente y no usadas en esta enumeración)... y aquélla elimina a la siguiente, etc... (dígitos).
Protected Overrides Sub Finalize()
p_Next = Nothing
MyBase.Finalize()
End Sub
End Class
'End Class
---- La clase registra un sólo carácter y nada más que uno, y guarda la info especifica para ello. Esto es: el valor actual, el valor Max, El Min, el incremento (+1
ó -1, en realidad +2, -2, pués manejamos 2 bytes por carácter).
---- p_PosicionChar, indica la posición que este carácter (ésta instancia de la clase ciclos) ocupa en la clave que se está generando.
---- p_Next, es una instancia a la clase que amneja el siguiente carácter. Recuerdo, que se opera como un cuentakilómetros, solo se mueve un dígito, y cuando alcanza su tope, fuerza-arrastra al siguiente al tiempo, que este regresa a su valor mínimo.
---- El método, SetEstadoInicial, en realidad recrea el 'cuentakilómetros, ya que recursivamente va generando una clase por cada carácter y luego se le cede el control, con cada 'carácter' coloca los valores asociados al carácter, valor actual límites Maxy Min, el valor de incremento... Cuando se llega al último carácter (el de la izquierda), se crea una última instancia con datos específicos, que luego son entendidos como: fin, ya no hay más caracteres, y sirve para retroceder en las devoluciones de llamdas en recursividad.
Si una llamada previa hubiere generado 2 caracteres, y por tanto 20 instancias, y la de ahora solo 6, asociar p_Next, para la clase final a Nothing, tiene por objeto destruir toda la estructura por encima de ella, es decir las instancias de clases, para los caracteres 7 a 21, serían eliminadas y la 6ª haría las veces de clase límite.
--- Cuando desde el bucle del metodo "Enumerar" de la clase cPermut, se invoca Ciclos.Mutar, se esta pidiendo generar una clave cada vez. el método Mutar (de Permutar), realiza un incremento-decremento (según la dirección del alfabeto), al valor actual. Pero si ya se alcanzó el límite, entonces se coloca el valor mínimo y luego invoca a la siguiente clase, para mutar su valor. Se reconoce, cuantas veces puede invocarse Mutar, porque tras el último carácter, se invoca la instancia que actúa de límite, la cual tiene establecido como posición en el array 255, y por tanto se avisa de que ha llegado al final (Fin = True), valor que detecta el bucle iterador principal de la clase padre, tras cada permutación.
En la práctica, asignar el valor de psoición del carácter como 255, implica que se podría permutar (sin cambios en el código), claves de hasta 254 caracteres de largo, ya que la instancia con valor 255, actúa de límite.
Finalmente, la instancia 'mutada' coloca el valor actual en la clave generada.
- El último método (finalize), es para liberar la memoria, cuando ya no se requiera el objeto... Esto en cad alenguaje debe hacerse tal como sea preciso en el lenguaje.
Y eso es todo. El código es más elegante y más corto que para el algortimo de los bucles FOR, pero mucho más lento, por usar recursividad, también porque constantemente se verifica que posición de carácter ocupa esa instancia. La recursividad no es la misma función, si no a la misma función de otra clase.
Mañana o pasado, más...
Nueva entrega... Esta vez hacemos el mismo algoritmo, ya visto, 3ª versión.
Realizada con bucles Do, como la versión con bucles For, es sencilla de entender y más rápida que las dos versiones previas, y al igual que la 2ª versión, admite un estado inicial de trabajo distinto a la primera secuencia del alfabeto.
Igualmente que en las predecores, admite un alfabeto propio por cada carácter, que es la particularidad más interesante de este 2º algoritmo.
Comparte con los otras 2 versiones de este algoritmo 2º, la interfaz del usuario... es decir las 3 cajas de texto, donde se introducen, el estado inicial del alfabeto, el estado mínimo y máximo de cada carácter del alfabeto y un botón específico para realizar la tarea. Por tanto de esa parte, solo se pondrá el cóodigo relativo al botón, a continuación:
Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click
Dim ClaveActual() As Byte, Min() As Byte, Max() As Byte
Dim z As Decimal
ClaveActual = StringToByteArray(TextBox1.Text) ' Valor inicial: "ABXFD"
Min = StringToByteArray(TextBox2.Text) ' Valor mínimo: Ejemplo: "AAAAZ"
Max = StringToByteArray(TextBox3.Text) ' Valor final, Ejemplo: "ZWZZA
z = bucl.EnumerarDo(ClaveActual, Min, Max)
End Sub
La función StringToBytearray, ya se puso el código de ella en un mensaje anterior.
El objeto Bucl, ya fue definido para la versión del algoritmo usando FOR, y en esa misma clase, se aloja la función EnumerarDo. Podría haber sido una sobrecarga, pero así queda más claro que función se asocia con cada algoritmo.
Y respecto de la interfaz, no requiere más comentarios...
Vamos con el algoritmo. Primero el código y luego los comentarios, si bien, la mayor parte ya ha sido comentado en los anteriores mensajes... aquí por tanto solo se señala lo específico de esta versión.
' Esta clase ya está creada en el mensaje del algoritmo FOR.
Public Class cBucAni
Public Function EnumerarFor(ByRef sMin() As Byte, ByRef sMax() As Byte) As Decimal
' esta función ya se puso más arriba, se comenta por claridad...
End Function
' Permite enumerar todas las permutaciones, para claves de largo entre 1 a 16 caracteres
Public Function EnumerarDo(ByVal ClaveActual() As Byte, ByRef sMin() As Byte, ByRef sMax() As Byte) As Decimal
Dim Max(0 To 15) As Byte
Dim Min(0 To 15) As Byte
Dim Inc(0 To 15) As Short
Dim Ini(0 To 15) As Byte ' Para establecer valores iniciales.
Dim valA, valB, valC, valD, valE, valF, valG, valH, valI, valJ, valK, valL, valM, valN, valO, valP As Byte ' podríasn desbordar si min o máx llegan a 0 ó 255... (en tal caso cambiarlo a short).
Dim minA, minB, minC, minD, minE, minF, minG, minH, minI, minJ, minK, minL, minM, minN, minO, minP As Byte
Dim maxA, maxB, maxC, maxD, maxE, maxF, maxG, maxH, maxI, maxJ, maxK, maxL, maxM, maxN, maxO, maxP As Byte
Dim incA, incB, incC, incD, incE, incF, incG, incH, incI, incJ, incK, incL, incM, incN, incO, incP As Short
Dim SizeClave As Short ' Tamaño de las claves (cantidad de caracteres que contienen)
Dim ClavePermutada() As Byte ' Clave generada en bytes.
Dim t As Short, n As Short
Dim z As Decimal, Crono As Single
Dim txt As String = ""
txt = ""
Crono = TimeOfDay.Ticks ' ticks a la hora actual
z = CalcularNumPermutaciones(ClaveActual, sMin, sMax)
If (z < 0) Then
Return -1
'Exit Function
Else
SizeClave = ClaveActual.Length
ReDim ClavePermutada(0 To SizeClave - 1)
' Espacio usado por ClaveActual
' para invertir las claves generadas, invertir el recorrido en este bucle
For t = 0 To (SizeClave - 2) Step 2 ' (SizeClave - 2) To 0 Step -2
Max(n) = sMax(t)
Min(n) = sMin(t)
Ini(n) = ClaveActual(t) ' inicializa (parcialmente) los valores iniciales d ela clave.
ClavePermutada(t) = Ini(n)
n += 1
Next
' Definiendo el avance por cada carácter.
For t = 0 To n - 1 '((SizeClave \ 2) - 2)
If (Max(t) >= Min(t)) Then
Inc(t) = 1
ElseIf (Max(t) < Min(t)) Then
Inc(t) = -1
End If
Next
' Espacio no usado por ClaveActual (hasta 15 caracters).
For t = n To 15 'SizeClave To 15
Inc(t) = 255 'Min(t) = 255 : Max(t) = 255 :
Next
End If
' Establece los valores Iniciales del array Ini, a las variables sueltas (es más rápido)
valP = Ini(15) : valO = Ini(14) : valN = Ini(13) : valM = Ini(12) : valL = Ini(11) : valK = Ini(10) : valJ = Ini(9) : valI = Ini(8)
valH = Ini(7) : valG = Ini(6) : valF = Ini(5) : valE = Ini(4) : valD = Ini(3) : valC = Ini(2) : valB = Ini(1) : valA = Ini(0)
' Establece los valores de Incremento del array Inc, a las variables sueltas (es más rápido)
incP = Inc(15) : incO = Inc(14) : incN = Inc(13) : incM = Inc(12) : incL = Inc(11) : incK = Inc(10) : incJ = Inc(9) : incI = Inc(8)
incH = Inc(7) : incG = Inc(6) : incF = Inc(5) : incE = Inc(4) : incD = Inc(3) : incC = Inc(2) : incB = Inc(1) : incA = Inc(0)
' Establece los valores Minimos del array Min, a las variables sueltas (es más rápido)
minP = Min(15) : minO = Min(14) : minN = Min(13) : minM = Min(12) : minL = Min(11) : minK = Min(10) : minJ = Min(9) : minI = Min(8)
minH = Min(7) : minG = Min(6) : minF = Min(5) : minE = Min(4) : minD = Min(3) : minC = Min(2) : minB = Min(1) : minA = Min(0)
' Establece los valores Máximos del array Max, a las variables sueltas (es más rápido)
maxP = Max(15) + incP : maxO = Max(14) + incO : maxN = Max(13) + incN : maxM = Max(12) + incM
maxL = Max(11) + incL : maxK = Max(10) + incK : maxJ = Max(9) + incJ : maxI = Max(8) + incI
maxH = Max(7) + incH : maxG = Max(6) + incG : maxF = Max(5) + incF : maxE = Max(4) + incE
maxD = Max(3) + incD : maxC = Max(2) + incC : maxB = Max(1) + incB : maxA = Max(0) + incA
' La enumeración finaliza con un error, al tratar de escribir en una posición del array fuera de posición (desbordamiento).
' No es nada elegante pero funciona y no lo ralentiza con una solución más elegante que exija más código.
Try
Do
Do
Do
Do
Do
Do
Do
Do
Do
Do
Do
Do
Do
Do
Do
Do
ClavePermutada(0) = valA
' Usar Permutación desde aquí:
'txt = System.Text.Encoding.Unicode.GetString(ClavePermutada)
' call FuncionX(ClavePermutada)
valA += incA
Loop While (valA <> maxA)
valA = minA
ClavePermutada(2) = valB
valB += incB
Loop While (valB <> maxB)
valB = minB
ClavePermutada(4) = valC
valC += incC
Loop While (valC <> maxC)
valC = minC
ClavePermutada(6) = valD
valD += incD
Loop While (valD <> maxD)
valD = minD
ClavePermutada(8) = valE
valE += incE
Loop While (valE <> maxE)
valE = minE
'If (SizeClave = 10) Then GoTo salida
ClavePermutada(10) = valF
valF += incF
Loop While (valF <> maxF)
valF = minF
ClavePermutada(12) = valG
valG += incG
Loop While (valG <> maxG)
valG = minG
ClavePermutada(14) = valH
valH += incH
Loop While (valH <> maxH)
valH = minH
ClavePermutada(16) = valI
valI += incI
Loop While (valI <> maxI)
valI = minI
ClavePermutada(18) = valJ
valJ += incJ
Loop While (valJ <> maxJ)
valJ = minJ
ClavePermutada(20) = valK
valK += incK
Loop While (valK <> maxK)
valK = minK
ClavePermutada(22) = valL
valL += incL
Loop While (valL <> maxL)
valL = minL
ClavePermutada(24) = valM
valM += incM
Loop While (valM <> maxM)
valM = minM
ClavePermutada(26) = valN
valN += incN
Loop While (valN <> maxN)
valN = minN
ClavePermutada(28) = valO
valO += incO
Loop While (valO <> maxO)
valO = minO
ClavePermutada(30) = valP
valP += incP
Loop While (valP <> maxP)
Catch
z = z
End Try
salida:
' Verificando la última clave.
txt = System.Text.Encoding.Unicode.GetString(ClavePermutada)
' Devolver resultados
Crono = ((TimeOfDay.Ticks - Crono) / 10000000) ' ticks a la hora actual, menos los de comienzo= ticks invertidos en la tarea.
MessageBox.Show("Tiempo: " & Crono.ToString & vbCrLf & "Permutaciones: " & z.ToString & vbCrLf & "ültima permutación: " & txt)
Return z
End Function
End Class
Lo primero que vemos es un chorro de variables... vamos a explicar a que se debe.
Puesto que cada carácter tiene definido su propio alfabeto, es preciso que para cada uno se provean 5 cosas: El estado inicial del carácter, el estado actual del bucle, el valor mínimo que puede alcanzar el alfabeto para ese carácter, el estado máximo que puede alcanzar el alfabeto para ese carácter y la dirección de avance sobre el alfabeto.
Bien dado que la propia función tiene capacidad para operar con claves de hasta 16 caracteres, se necesitan 5 variables por cada una. Sin embargo, el hecho de facilitar la entrada a la función con solo 3 parámetros, implica que para asginar los valores de una forma rápida recurrimos a una fase preparatoria mediante bucles y arrays. Una vez que cada valor está en su sitio, se hace una asignación unitaria desde los arrays a variables sueltas, la razón?.
Hay dos razones:
- La 1ª es que siempre es más ra´pido acceder a la dirección de una variable que a una dentro de un array, ya que a esas debe llegarse como un desplazamiento del acceso al array, luego es más rápido solo por eso.
- la segunda es más d elo mismo, pero con una razón más poderosa... Cada vez que se accede a un array, se verifica si el índice reclamado existe dentro dle array, y si no es así arrojar un error "fuera de límites", etc... La sobrecarga de que cada vez que se tome el valor procedente de un array, deba vigilarse si el índice está fuera de límites, supone un retraso enorme... así matamos ese retraso también, junto al previo, si cambiamos los arrays por variables sueltas....
Finalmente para evitar un popurrí de variables, todas tienen nombres similares, alfabetizadas... así es fácil saber en que bucle estamos o qué variables es (útil con tantas como hay).
La partefea del algoritmo, es que acaba siempre con un error. La razón?. Hay 16 bucles anidados, comprobar al final de cada uno de ellos si la tarea terminó, es una sobrecarga inutíl. Cuando llegue a un bucle que esté fuera de curso, saltará un error porque intentará escribir en el array que contiene la clave permutada.
Aunque tratar un error puede conllevar la llamada (transaprente desde el código), unas 8-12 rutinas adicionales para localizar todos los datos del error y luego vaciarlo todo, esto es enormemente más rápido que poner en cada bucle un interceptor de fin de permutaciones.
Al final de la función, podría saberse si de verdad acabó o hubo un auténtico error no esperado, si al comienzo se establece que bucle no debe llegar a alcanzarse y luego al cazar el error se verifica si en efecto el valor del contador en ese bucle varió... se ha omitido cualquier comprobación al respecto.
El código de la función es sustancialmente idéntico al del bucle for, excepto que como el bucle DO, permite hacer las comprobaciones tanto al principio (Do while condicion... loop) como al final (do.... loop while condicion), haciéndolo al final, podemos reastaurar el contador del bucle al vamor minimo aceptado en el alfabeto para el carácter en ´juego en dicho bucle... pudiendo por tanto asignar fácilmente antes del inicio de los bucles como contador el valor del estado desde el que se quiere empezar la enumeración de las permutaciones.
Las comprobaciones que debe hacer antes de iniciar el bucle, ya han sido comentadas, en los dos mensajes previos.
Y resta decir que de las tres variaciones de este algoritmo 2, ésta e sla más rápida (los bucles do, son más rápidos que los bucles for).
Respeto de este algoritmo, decir que todavía se pueden optimizar, pero habría que acudir al ensamblador... algo que comentaremos en la siguiente entrega.
----------------------------
En la sigiente entrega veremos otro algoritmo de naturaleza algo diferente. El alfabeto, vuelve a ser fijo para todas las claves (es decir todos los caracterestienen el mismo y único alfabeto). Es un algoritmo generado con concatenación...
cualquier duda, preguntad :o
Nos vemos... en la sigiente entrega.
dices que en tu maquina hace 2,500,000,000 claves por minuto guauu
una duda que maquina tienes de ram y procesador?
y dices que no tienes la versión para windows ya que lo quería probar en mi maquina pero tengo windows
saludos Flamer y si mis cálculos son correctos tardarías como casi 2 horas para hacer un diccionario con el abecedario que son 27 dígitos y con 8 de longitud de las claves, es correcto