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
Nos vemos... en la sigiente entrega.