Permutaciones en matrices (Visual Basic y C++)

Un ejercicio clásico de programación consiste en generar todas las permutaciones de una matriz o cadena de caracteres. Para este último caso en Visual Basic hay una solución que consta de dos procedimientos (uno de ellos recursivo), mientras que para las matrices, echando mano de la Wikipedia buena (en inglés), así como de sitios como rosettacode.org (una Wikipedia de la programación), la mejor solución para generar pemutaciones es el algoritmo de Heap, que puede ser recursivo o no recursivo (como el indicado más adelante, más práctico para permutar matrices):


procedure generate(n : integer, A : array of any):
c : array of int
for i := 0; i < n; i += 1 do
c[i] := 0
end for
output(A)
i := 0;
while i < n do
if c[i] < i then
if i is even then
swap(A[0], A[i])
else
swap(A[c[i]], A[i])
end if
output(A)
c[i] += 1
i := 0
else
c[i] := 0
i += 1
end if
end while

Resolviendo la Estrella Mágica

Estrella mágica de grado 6: la suma de los lados de cada triángulo mayor, y de los números del hexágono interno, debe ser siempre 26. Abajo se muestra una de las 72 soluciones posibles.

Como parte de mi afición por los cubos de Rubik había encontrado hace un tiempo el canal de Cuby, un youtuber aficionado a estos cubos y a los puzzles en general. En uno de sus videos presenta una Estrella Mágica, un acertijo con forma de estrella de seis puntas en el cual hay que colocar los números del 1 al 12, de modo tal que los lados de cada triángulo mayor de la estrella, así como los seis números del hexágono central, sumen 26:

Y aquí entra nuevamente el tema de las permutaciones. Aunque existen soluciones matemáticas para este problema, la primera intención siempre suele ser resolverlo por fuerza bruta, es decir, con un programa que genere todas las permutaciones posibles y muestre las soluciones.

En el minuto 6:58 del video está el código usado por él (C# sobre Visual Studio), y como a mí me colapsó el Visual Basic al querer resolverlo en Excel, me pareció mejor volver al C++ (sobre Dev-C++), y crear un programa que además cuente el número de soluciones. Resulta que aunque hay 479.001.600 permutaciones posibles, sólo 72 solucionan el problema. Adjunto aquí el código fuente y la aplicación generada, con el valor de cada letra del tablero según el esquema de la imagen anterior.

Resolver por fuerza bruta un problema como éste es muy sencillo, comparado con otros como el problema de las n damas, que consiste en colocar n damas en un tablero de ajedrez de n por n casillas, de manera que no haya más de una dama por cada fila, columna y diagonal del tablero, que se complica al resolverlo por fuerza bruta cuando n pasa de 50, y para el cual hay una recompensa de un millón de dólares para una solución polinomial (no algorítmica) con n igual a 1000. Lo que en el fondo no es otra cosa que una solución del problema P=NP:

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.