En esta entrada se desarrollan las ideas sobre punteros móviles para evitar el uso de múltiples bucles en Combinatoria. Seguiremos actuando sobre particiones de un número.
Un ejemplo previo
Supongamos que deseo descomponer el número 50 en sumandos cuadrados, sin importarme el número de ellos que usemos, pero que sea a lo más tres.
Con Cartesius
Esta herramienta no es
excesivamente amigable, pero la suelo incluir por sus prestaciones. En ella
podríamos plantear lo siguiente:
xrango=3
xt=1..50
xt=filtro(cuadrado)
creciente
suma=50
Estas condiciones, por orden, exigen que los sumandos sean
uno, dos o tres. Después se fijan los datos en el conjunto 1…50. Se les aplica
un filtro para quedarnos tan solo con los cuadrados, y, finalmente, se fija la
suma en 50 con sumandos crecientes.
El resultado es
Cartesius solo llega a conjuntos de 12, luego necesitaremos, si deseamos trabajar con Excel, otra herramienta distinta. Es lo que voy a presentar ahora, para destacar la conveniencia del uso de punteros. En negrita y cursiva figura el código, y en tipo normal los comentarios.
Con el Buscador
Este código de algoritmo puede
resultar pesado o difícil, por lo que quienes sólo deseen estudiar los ejemplos
lo pueden ignorar. Es interesante porque permite, con ligeros retoques, su
adaptación a muchas situaciones.
Sub particion()
'Devuelve el número total de particiones condicionadas y su
desarrollo
Dim pp, i, j, contador, tope, fila, n, final, suma
Dim e(1000), su(1000)
Dim seguir As Boolean
Dim s$ ‘Contenedor de particiones
‘Lee el número y el tope de las particiones
n =
ActiveWorkbook.Sheets(3).Cells(4, 7).Value
tope
= ActiveWorkbook.Sheets(3).Cells(5, 7).Value
Call borrarango("e6:i2000")
fila = 8
final
= n
For
i = 1 To n 'Inicios
e(i) = 0
su(i) = 0
su(i) = i
Next
i
fila = 8 ‘Inicio de la presentación de
resultados
For i = 1 To n 'Inicios
e(i) = 0 ‘Este
vector sigue a los sumandos en la tabla
su(i) = 0, Contenido de la celda que señala
el puntero
Next i
'Restricciones o filtros En el ejemplo, que sean cuadrados
i =
1
While
i <= final
If
Not escuad(su(i)) Then
For
j = i To n - 1: su(j) = su(j + 1): Next j
final = final – 1 ‘Elimina los que no valen
Else
i =
i + 1
End
If
Wend
If
Not escuad(su(final)) Then final = final – 1
‘Final es el máximo número de sumandos
contador = 0
pp = 1 'inicio
de puntero
'Aquí inicios varios según el problema a tratar
suma = 0
While pp > 0 'puntero activo((va marcha
atrás en ese paso)
‘El puntero va y viene mientras sea positivo y no sobrepase
los topes
e(pp) = e(pp) + 1 ' avanza en columna dentro
del puntero
suma = suma + su(e(pp))
seguir = False 'determina si se sigue o no en
la misma columna de datos
If e(pp) > final Or suma > n Or (pp > 1 And
e(pp) > e(pp - 1)) Then seguir = True 'Se ha llegado al tope del
rango de datos, y hay que seguir con otra columna
If seguir Then 'Seguir significa retroceder
el puntero e iniciar su contenido
e(pp) = 0: pp
= pp - 1: suma = 0
Else
'Hay algo que comunicar sobre el conjunto, quizás una
solución, un mensaje o un añadido
suma = 0
For j = 1 To pp: suma = suma + su(e(j)): Next j
If
suma = n And pp <= tope Then
contador = contador + 1’Una solución
fila = fila + 1
s =
""
For
j = 1 To pp: s = s + Str$(su(e(j))): Next j
ActiveWorkbook.Sheets(3).Cells(fila,
6).Value = s
End
If
If
pp < n Then pp = pp + 1
End
If 'Nivel 1
If
pp < n Then pp = pp + 1
End
If
Wend
'Operaciones finales
ActiveWorkbook.Sheets(3).Cells(5,
5).Value = contador
End
Sub
El ejemplo actual se resuelve cambiando las restricciones (en este caso escuad()), porque deseamos que los sumandos sean cuadrados. El resto, valor de n y del tope, se leen en el Buscador.
Al pulsar en el botón de búsqueda obtenemos la solución deseada:
Abajo aparecerán las soluciones
y, a la izquierda del tope, el número de ellas, que aquí son 3.
La ventaja de este algoritmo es
que puede devolver particiones superiores a 12, que es la limitación de
Cartesius. También es más rápido.
En la imagen podemos observar las
particiones de 100 en trece elementos que son cuadrados pares:
Han resultado trece particiones.
En la siguiente entrada acudiremos mayoritariamente a la
instrucción de PARI forpart.
No hay comentarios:
Publicar un comentario