Permutaciones en hoja de cálculo con algoritmo Empuja-Inserta

Permutaciones en hoja de cálculo y combinatoria

Las hojas de cálculo vienen dotadas de fórmulas que realizan cálculos combinatorios, pero no traen ninguna utilidad para efectuar esas combinaciones a nivel práctico, de modo que se puedan usar como datos de entrada en un problema real. Por ejemplo, si hemos construido un modelo matemático que acepta una secuencia de datos como entrada, y esa secuencia de datos está formada por una combinación ordenada aleatoriamente de los valores:

Lluvia, granizo, nievo, helada

La hoja de cálculo (en este caso las fórmulas en Excel y en LibreOffice Calc son idénticas) nos puede decir que con esos 4 elementos, tomados de 4 en 4, se puede generar un total de:

=PERMUTACIONES(4;4)

Que da como resultado 24

En general, por teoría de recuento o combinatoria, sabemos que para un conjunto de “n” elementos, tomados en grupos de “m”, el número de grupos o combinaciones sin repetición de elementos que se pueden formar son, en notación matemática habitual:

Cn,m=n!/(n-m)!

Cuando hablamos de permutaciones, al menos, hasta donde yo sé, en el español de la península, se suele entender que n=m, es decir, que combinamos todos los elementos del conjunto inicial, y entonces n-m=0, y como 0!=1:

Pn,m=n!/0!=n!

Efectivamente: 4!=24

Infografía sobre el funcionamiento del algoritmo Empuja-Inserta, para permutaciones en hoja de cálculo
Infografía sobre el funcionamiento del algoritmo Empuja-Inserta, para permutaciones en hoja de cálculo

Generación efectiva de permutaciones en hoja de cálculo

Se puede calcular el número, pero no se pueden hacer permutaciones en hoja de cálculo. No hay utilidad nativa que permita tomar esos 4 valores y permutarlos para generar la posible tabla de entrada que comprenda las 24 posibles ordenaciones que se pueden introducir, pongamos por caso, a un cierto modelo matemático que se comporta de una manera o de otra según sea la secuencia de presentación de esos datos. En el ejemplo meteorológico antes mencionado, cabe suponer que un servicio de emergencias de protección civil tendrá un protocolo de actuación distinto según sea el orden de presentación de los meteoros.

Las permutaciones se usan en muchos campos de la vida real que se gestionan informáticamente tales como la criptografía, la biología molecular, la lingüistica, el análisis y la minería de datos y las simulaciones de todo tipo, incluida la propia arquitectura de los ordenadores.

A la hora de diseñar mi algoritmo Empuja-Inserta, me he inspirado en el algoritmo Insertion-Push para la ordenación de listas de datos que aprendí en un curso por video del MIT que se puede ver en YouTube, pero he incorporado todo el asunto de las matrices de paso, sin las cuales no se me ocurre como organizar todos los estadios intermedios que son necesarios. Al plasmar este algoritmo en un módulo de la hoja de cálculo, hay que tener en cuenta que las permutaciones se generaran por filas, y por tanto el máximo número de elementos a permutar solo puede ser 9, lo que arroja un total de 9!=362.880, ya que tanto en Excel, como en LibreOffice, el número de filas de una hoja es 1.048.576, lo que superaría las filas necesarias para permutar 10 elementos, o sea 10!=3.628.800. Siempre queda la posibilidad de mandar los datos de salida a un archivo de texto externo mediante una modificación del algoritmo, pero de momento yo me voy a quedar en el ámbito de las hojas de cálculo.

Algoritmo Empuja-Inserta

He comparado la respuesta de mi algoritmo Empuja-Inserta con el único que he visto que estaba en internet, y que se menciona como extraido de un libro de John Walkenbach, pero sin autor conocido. Los resultados, que doy en segundos, indican que mi algoritmo Empuja-Inserta es mucho más lento, pero a cambio es mucho más versátil, pues el del anónimo solo puede trabajar con dígitos simples en una columna, mientras que el mío permuta elementos hechos y derechos, cada uno en su celda (y dios en la de todos), y genera una tabla de datos completamente funcional.

Elementos (nº)Mi algoritmo (s)El anónimo (s)
50,01560
60,07850
70,68750,125
86,17180,5781
9645,5

En fin, aquí está el algoritmo Empuja-Inserta para generación de permutaciones en hoja de cálculo que he probado satisfactoriamente en Excel 2013 y LibreOffice 5.3.7.2, junto a un video tutorial sobre su uso. En la parte inferior de la hoja os dejo también el enlace al archivo descargable de Excel con la utilidad lista para funcionar.

Option Explicit

Sub R_Permutacion()

‘Algoritmo Empuja-Inserta para la creación de permutaciones de elementos en Excel y LibreOffice Calc

‘Creado por Eloy Caballero;  https://eloycaballero.com/

‘Limpieza de la zona de escritura

Worksheets(“Hoja1”).Range(“$A$2:$I$1048576”).Clear

Dim DatString() As Variant ‘Aquí se alojará la cadena a permutar

Dim ene As Long

  ene = Worksheets(“Hoja1”).Range(“a1”).CurrentRegion.Count ‘Numero de elementos de la permutacion

‘Vamos a tolerar 9 items, porque con 10 nos vamos a 3.680.000 filas

If ene > 9 Then

    MsgBox “Solo hasta 9 elementos”

    Exit Sub

End If

‘Como mínimo necesitamos dos elementos

If ene <= 1 Then

    MsgBox “Mínimo dos elementos”

    Exit Sub

End If

ReDim DatString(1 To ene)

Dim i As Long, j As Long, k As Long, m As Long, n As Long

For i = 1 To ene

    DatString(i) = Worksheets(“Hoja1”).Cells(1, i).Value ‘Carga de los elementos a permutar

Next i

Dim ciclos As Long

ciclos = Fkii(ene)

‘Comenzamos con el algoritmo Empuja-Inserta

Dim FilCiclo, ColCiclo As Long ‘filas y columnas de cada ciclo

Dim NewElment As Variant ‘El nuevo elemento que va a empujar

Dim MPer() As Variant, MPas() As Variant  ‘las matriz de resultados y de paso

ReDim MPer(1 To ciclos, 1 To ene)

ReDim MPas(1 To ciclos, 1 To ene)

Dim SubNiv As Long ‘El subnivel de modulación de la matriz de paso

‘Cargamos los dos primeros niveles de permutación

MPer(1, 1) = DatString(2)

MPer(1, 2) = DatString(1)

MPer(2, 1) = DatString(1)

MPer(2, 2) = DatString(2)

‘Comenzamos el algoritmo Empuja-Inserta

‘Haremos tantos ciclos como elementos a permutar

For i = 3 To ene

    FilCiclo = Fkii(i)

    ColCiclo = i

    NewElment = DatString(i)

    ‘Y a partir del 2 ciclo, creamos la matriz de paso, para cada fila del ciclo

    For j = 1 To FilCiclo

        SubNiv = 1 + ((j 1) \ i)

            For k = 1 To ColCiclo

                MPas(j, k) = MPer(SubNiv,k)

            Next k

    Next j

‘Tenemos que alimentar ahora la matriz de permutaciones con la matriz de paso

For m = 1 To ciclos

  For n = 1 To ene

   MPer(m, n) = MPas(m,n)

  Next n

Next m

‘Ahora, otra vez para cada fila del ciclo, hacemos el empuje e inserción

Dim jmod As Long

    For j = 1 To FilCiclo

    ‘Modulamos el índice j para que haga bien el ciclo de columnas

    jmod = j Mod i

    If jmod = 0 Then

      jmod = i

    End If

        ‘Y vamos desde la última para atrás empujando hasta la jmod

        For k = ColCiclo To jmod + 1 Step 1

            MPer(j, k) = MPer(j,k 1)

        Next k

        ‘Y en la jmod introducimos el Nuevo elemento en el hueco generado al empujar

        MPer(j, jmod) = NewElment

    Next j

Next i

‘Imprimimos resultados a las filas de la hoja

For m = 1 To ciclos

   For n = 1 To ene

        Worksheets(“Hoja1”).Cells(m + 1, n) = MPer(m, n)

    Next n

Next m

MsgBox ciclos & ” Permutaciones generadas”

End Sub

Function Fkii(arg As Long) As Long

‘Diseñamos una función para calcular el factorial aparte

Fkii = Application.WorksheetFunction.Fact(arg), esto serviría para Excel

Dim i As Long

    Fkii = 1

    For i = 1 To arg

        Fkii = Fkii * i

    Next i

End Function

Descarga

Comments

So empty here ... leave a comment!

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Sidebar



Si continuas utilizando este sitio, significa que aceptas el uso de cookies. más información

Los ajustes de cookies de esta web están configurados para "permitir cookies" y así ofrecerte la mejor experiencia de navegación posible. Si sigues utilizando esta web sin cambiar tus ajustes de cookies o haces clic en "Aceptar" estarás dando tu consentimiento a esto.

Cerrar