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...
Mostrar Mensajes
