Material registrado:

    Safe Creative #1709190281730

    Cajón de sastre:

    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.

    Código para algoritmo empuja-inserta
     
    Option Explicit
    Sub R_Permutacion()
    'Algoritmo Empuja-Inserta para la creación de permutaciones de elementos en Excel
    'Creado por Eloy Caballero;  https://eloycaballero.com/
    'Limpieza de la zona de escritura
    Worksheets("Hoja1").Range("$A$2:$I$1048576").Clear
    'Control de tiempo
    'Dim tInicio As Double, dUracion As Double
    'tInicio = Timer
    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
    'dUracion = Timer - tInicio
    'Debug.Print dUracion
    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

    Añadido 28-10-2018 Salida a archivo externo

    Dejo primero el código modificado del anterior que permite sacar los resultados a archivo externo, advirtiendo de que solo permitirá un máximo de 10 elementos a permutar. Si intentamos poner 11, nos dará error de asignación de memoria en VBA. Después dejo también el código modificado que permite permutar caracteres individuales de una cadena. Este código es una modificación del que se encuentra en la página: JLD Excel. Ojo con los límites de los que hablo en el video siguiente. Tenedlos en cuenta y no digáis que no os lo he advertido.

    Vamos entonces con la primera macro, que lee los elementos a permutar de la primera fila de la hoja 1 y saca los resultados a un archivo cuya ruta o ubicación en nuestro árbol de directorios se nos pregunta a través de un diálogo de Excel:

    Primera macro
     
    Option Explicit
    Sub R_Permutacion()
    'Algoritmo Empuja-Inserta para la creación de permutaciones de elementos en Excel
    'Creado por Eloy Caballero; https://eloycaballero.com/
    'Modificamos para salida a archivo de texto
    Dim DatString() As Variant 'Aquí se alojará la cadena a permutar
    Dim Filename As String, rutaDir As String
    Dim ene As Long
    ene = Worksheets("Hoja1").Range("a1").CurrentRegion.Count 'Numero de elementos de la permutacion
    'Como mínimo necesitamos dos elementos
    If ene <= 1 Then
    MsgBox "Mínimo dos elementos"
    Exit Sub
    End If
    'No ponemos ningún límite TARDA MUCHO Y GENERA ARCHIVOS MUY GRANDES
    'Funciona para 10 elementos, para 11 da error por falta de memoria en VBA
    If ene > 10 Then
    MsgBox "Llevará mucho tiempo y generará archivo muy grande"
    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 de la primera fila esquina izquierda de la hoja 1
    Next i
    Dim ciclos As Double
    ciclos = Application.WorksheetFunction.Fact(ene) ' esto serviría para Excel, pero no para LOCalc
    '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 String, MPas() As String '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 = Application.WorksheetFunction.Fact(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 fichero externo
    '================Seleccionamos directorio de destino del archivo final=================
    With Application.FileDialog(msoFileDialogFolderPicker)
    .InitialFileName = Application.DefaultFilePath & "\"
    .Title = "Seleccionar carpeta para crear archivo"
    .Show
    If .SelectedItems.Count = 0 Then
    MsgBox "Cancelled"
    Else
    rutaDir = .SelectedItems(1)
    End If
    End With
    '======================================================================================
    Filename = rutaDir & "\txtperm.csv"
    Open Filename For Output As #1
    For m = 1 To ciclos
    For n = 1 To ene
    If n <> ene Then
    Write #1, MPer(m, n);
    Else
    Write #1, MPer(m, n)
    End If
    Next n
    Next m
    Close #1
    MsgBox ciclos & " Permutaciones generadas"
    End Sub

    Y ahora con la segunda macro. Esta solo permuta caracteres individuales de una cadena que se suministra en el InputBox y los saca a un archivo cuya ruta hay que especificar en la línea de código a tal efecto. En caso de duda, ver otra vez el video.

    Segunda macro
     
    Option Explicit
    Dim Filename As String
    Dim CurrentRow
    Sub GetString()
    Dim tInicio As Long
    Dim InString As String
    InString = InputBox("Ingrese el numero o texto")
    tInicio = Timer
    Filename = "C:\....escribir aquí la ruta completa...\txtperm.csv"
    Open Filename For Output As #1
    Call GetPermutation("", InString)
    Close #1
    MsgBox "Tiempo empleado: " & Timer - tInicio
    End Sub
    Sub GetPermutation(x As String, y As String)
    ' Algoritmo de autor desconocido
    Dim i As Integer, j As Integer
    j = Len(y)
    If j < 2 Then
    Write #1, x & y
    Else
    For i = 1 To j
    Call GetPermutation(x + Mid(y, i, 1), Left(y, i - 1) + Right(y, j - i))
    Next
    End If
    End Sub

     

    Comments

    This post currently has 7 responses

    • Estimado Eloy:
      Mi nombre es Jose y te escribo desde Toledo.
      He visto el video tutorial sobre permutaciones y me parece estupendo.
      Mi problema es que necesito visualizar las permutaciones de 12 elementos (479.001.600 perm) y claro el código que me descargé no las admite. Comentas que se pueden visualizar si mandas los datos de salida a un archivo de texto externo mediante una modificación del algoritmo pero estoy un poco «pez» en programación VBA. Serías tan amable de enviarme a mi e-mail la modificación del algoritmo para guardarlo en un txt?. Sin más me despido de ti no sin antes felicitarte por los maravillosos video-tutoriales que realizas.
      Un saludo.

      • ¡Hola, José! Gracias por el interés y por «animarme» a retomar el tema. Te contesto con un video en un par de días, pero ya te adelanto que con ese número de datos generados empezamos a movernos en lo que yo llamo los límites de las hojas de cálculo (por el tiempo que tarda Excel) y también de los PC (por lo grande que se hace el archivo de texto generado). Pero bueno, me explicaré mejor en el video y allí te podrás bajar el archivo con el código. A ver si me da tiempo mañana.

    • Hola Eloy , gracias por compartir tu capacidad de intelecto en el excel. Aprendo cada día más y más. Necesito ayuda con una hoja de excel, para saber si se puede hacer o no. Ya que yo pienso que sí pero no tengo respuesta.
      Tengo una hoja de cálculo de inifitas columnas, y filas has 50.000. Lo bueno es que las primeras columnas son las que nos dan los valores en los que nos tenemos que fijar.
      *Supongamos 4 columnas («A» persona identificador -«B» año -«C» año producto-«D»producto-«E» dosis-«F» paks(está en blanco)- «G»sumapacks)
      *Tengo que rellenar la columna «F» siguiendo estas pautas:
      – Seleccionar las filas que contengan los valores de las columnas «A»,»B»,»C»,»D»,»E» – iguales. Tienen que ser iguales.
      – Sumar el valor de la columna «G» de todos estos iguales, y poner el resultado en la columna «F».
      – Eliminar el resto de filas iguales y solo dejar una fila.

      Esto es todo el procedimiento que hago casi de uno en uno a excepción de los No iguales, porque hay filas o bien alguna columna que no són iguales.

      Se puede hacer??
      Muchas gracias.
      Atentamente,
      SARA

      • Sí. Claro que se puede hacer. Incluso parece que se puede hacer sin macros, salvo la parte de «eliminar» las filas. Tengo varios tutoriales subidos a mi canal que resuelven partes de este problema. Primero: para encontrar que filas son iguales en valores de varias columnas, create una columna auxiliar concatenando los valores. Luego puedes aplicar SUMAR.SI a ese resultado y finalmente consolidar valores y eliminar las filas repetidas o no consolidarlas y simplemente ocultarlas. Si es un trabajo puntual, como parece, yo te lo puedo hacer como servicio de consultoría. Si te vale esto, ponme el archivo en una carpeta de la nube y te doy presupuesto y plazo. Si quieres intentar que alguien te lo solucione gratis, prueba en uno de los foros que te mencioné. Saludos.

    • buenas;
      tengo una pequeña duda, en el macro que tienes al dar los resultados los da sin repeticiones.
      en mi caso necesito con repeticiones y no se donde cambiar para que los de con ellos, ya que se puede presentar casos como el que sea necesario la repetición.
      muchas gracias y espero pronta respuesta

      • Hola. Como ya digo en el artículo, este algoritmo está diseñado para permutaciones, que es como, al menos en el español de la península, llamamos a las combinaciones sin repetición de TODOS los elementos de una lista dada. Lo que tú planteas es lo que aquí llamaríamos variaciones (combinaciones con repetición) y esa sería otra historia en la que había que considerar también otra variable, que es si se combinan siempre todos los elementos, o solo algunos subconjuntos de ellos y de qué dimensión son esos subconjuntos. Este algoritmo solo abarca el caso de las permutaciones. ¿Se podría aprovechar para tu necesidad? Intuyo que sí, siempre que seas capaz de diseñar un primer algoritmo que prepare cada diferente conjunto para permutarlo, pero eso, insisto, es otra historia.

    Deja una respuesta

    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