Regresos 16 (2): Particiones condicionadas. Algoritmo básico

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.

Regresos 16 (1): Particiones condicionadas de un número natural

En el año 2017 publiqué en mi blog “Números y hoja de cálculo” (https://hojaynumeros.blogspot.com/) una serie de estudios sobre particiones de un número obtenidas mediante mi herramienta Cartesius.

Quedé bastante satisfecho, pero echaba de menos poder estudiar las particiones de un número (formas de descomponer un número natural en sumandos) para valores mayores que doce, que es el máximo que me permitía Cartesius. He despojado los algoritmos de esta herramienta de muchas opciones, y me he quedado con lo imprescindible para calcular números de particiones condicionadas. Sigue siendo un proceso lento, pero me permite, con paciencia, abordar cálculos para números mayores que doce.

Lo he incorporado a la hoja “Buscador”, que tengo preparada para su descarga gratuita (https://www.hojamat.es/blog/buscador1.xlsm), y con ella, y sin abandonar Cartesius, ampliaré los trabajos del año 2017.

Tres herramientas

Esta va a ser una serie de entradas, por lo que es conveniente realizar una presentación previa de las mismas. En primer lugar, hay que advertir que el espíritu de ellas es el de aprendizaje y ejercitación. En este tema está todo publicado, y desde este blog poco se puede añadir, pero sí resulta atractivo cotejar distintos métodos para llegar a un mismo objetivo.  El mejor y más aconsejable sería el de trabajar con papel y bolígrafo, que es como mejor se aprende, pero al final se terminará recurriendo a herramientas informáticas.

Usaremos, de forma más o menos simultánea, tres herramientas básicas:

Cartesius

Es mi herramienta tradicional para construir productos cartesianos condicionados. En el tema de particiones ya he publicado muchos ejemplos, y resulta bastante sencilla de entender. Sus condiciones resultan claras.

Descargable desde

https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius

Buscador

En el archivo descargable presentado más arriba he situado, en su tercera hoja, una subrutina para realizar el mismo trabajo que el de Cartesius, pero que no sufre la restricción de las doce columnas. Resulta también más rápida, ya que el que no sea tan general le dota de más velocidad, pero nunca suficiente, porque todos los temas de Combinatoria acaban por abordar cálculos que resultan muy lentos.

Dirección de descarga: https://www.hojamat.es/blog/buscador1.xlsm

PARI

Este lenguaje posee herramientas potentes y rápidas, aunque adolece de falta de presentaciones intuitivas. Está dirigido a profesionales, pero en este blog le hemos conseguido mucha utilidad. Su orden FORPART será un pequeño tesoro para comprobar cálculos o ampliarlos.

Página web: https://pari.math.u-bordeaux.fr/gpwasm.html

 Algoritmo básico

Las particiones actúan sobre conjuntos de sumandos. Por ejemplo, si deseo descomponer el número 20 en cuatro sumandos primos, deberé usar el conjunto (2, 3, 5, 7, 11, 13, 17, 19). El resultado final es que existen 6 particiones distintas.

 Particiones condicionadas                         

Número:    20             

Número de particiones: 6

Conjunto de particiones: 5 5 5 5, 7 5 5 3, 7 7 3 3, 11 3 3 3, 11 5 2 2,       13 3 2 2

En algunas ocasiones, el número de particiones condicionadas proviene de operaciones sobre conjuntos de números sometidos a alguna operación (condición previa). Por ejemplo, podemos estar interesados en particiones en las que las partes sean todas libres de cuadrados, o que pertenezcan a la sucesión de Fibonacci. Esta será la condición previa en cada caso.

El manejo de cuatro números que no tienen que guardar relación entre ellos nos lleva, en el nivel elemental de algoritmos en el que se mueve esta serie, a usar bucles anidados: FOR I=12 T0…FOR J=12 TO…FOR K=12 TO… Esto supone una gran ineficiencia y poca versatilidad, porque el número de bucles debería adaptarse a cada ejemplo determinado.

Desde hace muchos años llevo usando punteros sobre una matriz rectangular (es una imagen para entendernos) en el que van avanzando por los distintos elementos llevando algún tipo de recuerdo de los que ya han visitado.

Concretando el ejemplo del primer párrafo, imaginemos que estudiamos el rango de números entre 40 y 50, y buscamos en ellos conjuntos de cuatro números con la propiedad pedida. Llamamos, por ejemplo, INICIO al valor mínimo (40 en este caso) y TOPE o FINAL al último (50). Por otra parte, daremos el nombre de NUME al número de elementos que tendrán nuestros conjuntos. Desde INICIO hasta final llamaremos E(I) a cada valor concreto de un elemento. En la imagen que sigue sería una columna, mientras que horizontalmente se representarían los elementos elegidos de izquierda a derecha, que será el “movimiento” que tendrá el puntero.

 

Al principio cuesta un poco entender la dinámica de este proceso, pero compensa el no tener que anidar bucles. En mis herramientas de ayuda a la enseñanza lo he usado, entre otros, en estas tres:

Combimaq (https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#combimaq)

Cartesius

(https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius)

Partlista (https://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#reprenum)

En la siguiente entrada se desarrollarán estas ideas.

 

Submulticonjuntos (2)

 Representación numérica de un multiconjunto

Con lo visto hasta ahora en la anterior entrada, lo esencial en un multiconjunto lo constituyen las multiplicidades. La naturaleza de los elementos no influye apenas en los conteos. Es un fenómeno similar a la descomposición en factores primos, que muchas funciones dependen tan solo de los exponentes. Esto nos permite representar un multiconjunto como un número, de forma unívoca. De las posibilidades existentes (hay variantes en la tarea de representar un multiconjunto mediante un número, como, por ejemplo, los números de Heinz), elegiremos aquí las siguientes:

·      Ordenamos las multiplicidades de mayor a menor (para que el número resultante sea lo más pequeño posible)

·      A cada multiplicidad correspondiente a un elemento dado le asignamos un número primo repetido, siguiendo el orden natural (algunos autores comienzan con el 1). En caso de empate, no hay problema, porque resulta el mismo número.

·   Si multiplicamos todos esos primos, resultará un número que poseerá una relación biunívoca con el conjunto.

Por ejemplo, en la palabra ZARAGOZA ordenamos las multiplicidades vistas en la entrada anterior: 3 de A, 2 de Z y 1 del resto de caracteres, R, G y O.

Sustituimos cada multiplicidad por números primos repetidos y ordenados:

2*2*2*3*3*5*7*11=27720.

Este número identifica, de forma unívoca, a todos los multiconjuntos con la serie de multiplicidades 3, 2, 1, 1, 1. Cada submulticonjunto de ellos se relacionará con un divisor de 27720, por el criterio general de divisibilidad, en el que los factores primos de los divisores son subconjuntos de los correspondientes en 27720.

Pedimos los divisores de 27720 con bigomega=3 (tres factores primos) en cualquier buscador, o con la función siguiente:

Function dosfact$(n, k)

Dim i

s = ""

For i = 2 To n

If n / i = n \ i Then

If bigomega(i) = k Then

s = s + ajusta(i) + "  "

End If

End If

Next i

dosfact = s

End Function

La aplicamos a 27720 con k=3, por ejemplo, y resultan 19 divisores:

8  12  18  20  28  30  42  44  45  63  66  70  99  105  110  154  165  231  385 

Ahora usamos la técnica de las combinaciones acotadas que vimos en la entrada anterior, con Cartesius:

xtotal=3

xt=2,3,5,7,11

creciente

contar(2)<4

contar(3)<3

contar(5)<2

contar(7)<2

contar(11)<2

Coincide el número de submulticonjuntos de tres elementos:

Son también 19.

Cálculo directo

Usando la técnica combinatoria de eliminar combinaciones prohibidas resultaría:

Combinaciones con repetición:

COMBINAT(5+3-1;3) = COMBINAT(7;3 = 35

Hay que restarle uno por la combinación prohibida (3,3,3) y para el 5, 7 y 11, cinco cada uno para eliminar aquellos en los que están repetidos: (5,5,2), (5,5,3), …

En total: 35-1-5-5-5=19

Para casos más complicados habría que acudir a técnicas parecidas al Principio de Inclusión y exclusión, sumando y restando posibilidades. Para cálculos mediante fórmulas directas, las incluidas en https://arxiv.org/abs/2009.01233, m-submultisets and m-permutations of multisets elements

Para encontrar el número total de submulticonjuntos sustituiríamos XTOTAL=3 en Cartesius por XRANGO=8, que los abarca todos menos el conjunto vacío. Resultan 95.

Si contamos el conjunto vacío, serían 96, representado en los divisores de 27720 por el número 1.

Si ahora calculamos la función TAU (número de divisores) por su fórmula, usando las multiplicidades, resulta:

TAU(27720)=(1+3)(1+2)(1+1)(1+1)(1+1)=4*3*2*2*2=96

El paralelismo entre subconjuntos y divisores queda comprobado. Es interesante.

Submulticonjuntos (1)

Un multiconjunto (multiset en inglés) es un conjunto en el que se permite la repetición de algunos o todos sus elementos un número determinado de veces, llamado multiplicidad del elemento. Al conjunto de elementos tomados sin repetición se le llama conjunto subyacente,

Un ejemplo claro son los conjuntos de tiradas en Combinatoria, las extracciones de bolas con repetición o el conjunto de los factores primos de un número. En todos ellos se permite que algunos elementos estén repetidos, Otro ejemplo típico es el las letras de una palabra. Por ejemplo, las letras de la palabra ZARAGOZA. Aquí se permite que la Z se repita dos veces y la A tres. Su conjunto subyacente es ZARGO.

Formalmente, un multiconjunto es un conjunto de elementos que son pares del tipo (elemento, multiplicidad). Por ejemplo, las letras de ZARAGOZA forman el multiconjunto

{(A,3),(Z,2),(R,1),(G,1),(O,1)}

Un submulticonjunto de un multiconjunto es otro multiconjunto cuyos elementos pertenecen al multiconjunto inicial con multiplicidades no mayores que las del mismo.

Así, GOZAR es submulticonjunto de ZARAGOZA, pero no lo es ARROZ, porque la R tiene una multiplicidad mayor.

Combinaciones con repetición

En todas las cuestiones que siguen, la base son las combinaciones con repetición. Podremos usar la fórmula para m objetos tomados de n en n, fórmula elemental y conocida:

Tomemos como ejemplo el conjunto {2,3,4,5} Si deseamos construir todas las combinaciones con repetición de 3 en 3, según la fórmula, deberemos obtener en total, usando el lenguaje de las hojas de cálculo:

COMBINAT(4+3-1,3) = COMBINAT(6,3)=6*5*4/6=5*4=20

En efecto, con nuestra herramienta Cartesius se puede comprobar.

(https://www.hojamat.es/sindecimales/combinatoria/herramientas/herrcomb.htm#cartesius)

Basta exigir estas tres condiciones:

xtotal=3

xt=2,3,4,5

creciente

Se pide crear tres columnas con contenido 2,3,4,5 y solo se exige que los arreglos sean crecientes, para que resulten combinaciones y no variaciones. El resultado es el esperado, 20 combinaciones con repetición.

 

Combinaciones con repetición acotadas

Si en lugar del conjunto {2,3,4,5} eligiéramos el multiconjunto {2,3,3,4,4,5} deberíamos tener en cuenta que sus subconjuntos no pueden presentar más frecuencias que las determinadas, un 2, dos 3, dos 4 y un 5.

En Cartesius tendríamos que acotar las frecuencias, para que resultaran subconjuntos. Podría ser así:

 

xtotal=3

xt=2,3,4,5

creciente

contar(2)<2

contar(3)<3

contar(4)<3

contar(5)<2

 

Se restringen las frecuencias, con lo que resultan submulticonjuntos:

El resultado sería:

Las combinaciones se han reducido a 10.

¿Cómo llegar a ese número sin usar Cartesius?

En nuestro caso, al número 20 habría que restarle las combinaciones en las que el 3 se repite más de dos veces, y también aquellas en las que ocurre lo mismo con el cuatro. Después eliminaríamos aquellas en las que el 2 o el 5 se repitieran más de una vez

Sería:

Combinaciones totales: CR(4,3)=COMBINAT(6,3)=20

Combinaciones no válidas con el 2: Hay que desechar aquellas combinaciones en las que el 2 se repita dos o tres veces, es decir, fijamos el 2 dos veces, y nos quedan combinaciones de cuatro elementos tomados de uno en, es decir:

CR(4,1)=COMBINAT(4,1)=4. Igual ocurre con el 5

Combinaciones no válidas para el 3: Siguiendo el mismo razonamiento, fijamos el 3 tres veces y queda CR(4,0)=1, e igual para el 4

Nos quedaría prohibir que dos elementos sobrepasaran la multiplicidad, pero eso no ocurre y hemos terminado:

Número de submulticonjuntos: 20-4-4-1-1=10

Así que la idea es, para eliminar combinaciones, fijar cada elemento en su multiplicidad y uno más, y desarrollar lo que queda:

CR(4,3)-CR(4,1)-CR(4,1)-CR(4,0)-CR(4,0)

Se comprende que con más elementos el cálculo se complica, pero este sería el camino correcto.

Números de pastel

Estos números constituyen una extensión natural de los traducidos como “Catering perezoso” (o también como “Cortador perezoso”), que ya se han estudiado en este blog. Si aquellos contaban el máximo de cortes rectilíneos sobre una tarta o pizza, considerados en dos dimensiones (todos frontales a la superficie mayor de la tarta), aquí se trata de cortar un cubo o una tarta mediante cortes planos que actúan sobre tres dimensiones. Buscaremos siempre el número máximo de partes, por lo que no se consideran planos paralelos, ni cortes paralelos, ni varios planos incidentes en el mismo punto.

Siguiendo las ideas de Peter C. Heinig en https://oeis.org/A000125, podemos contemplar tres escalas de complejidad en estos cortes:

Una dimensión, cortes sobre una recta. Es evidente que el número máximo de regiones para n cortes es

C₁(n)=binomial(n,0)+binomial(n,1)=1+n

En el caso de un plano, vimos, en la sucesión de catering perezoso, https://hojaynumeros.blogspot.com/2026/02/el-catering-perezoso.html, que el número era: n(n+1)/2+1, que también se puede escribir como

C₂(n)= binomial(n,0)+binomial(n,1)+binomial(n,2)

En nuestro caso actual, sobre tres dimensiones, es fácil razonar que su expresión es C(n+1,3)+n+1=(n+1)n(n-1)/6+n+1, lo que nos llevaría a

C₃(n) = binomial(n,0) + binomial(n,1) + binomial(n,2) + binomial(n,3)

Lo vemos:

Una tarta, con el corte mediante un solo plano se divide en dos partes, y se cumple C(1)=0+1+1=2

Para dos cortes obtenemos cuatro partes como máximo, y se cumple:

C(2)=3*2*1/6+2+1=4

Aquí podemos seguir por inducción: Supongamos efectuados los n-1 cortes primeros. Al cortarlos con un nuevo plano, si ese número es máximo, se formarán en el nuevo plano el máximo de cortes posible, que sabemos que es C₂(n-1), y serían elementos de la sucesión del catering perezoso, luego C₃(n)= C₃(n-1)+C₂(n-1), y quedaría:

C₃(n)= C₃(n-1)+(n-1)n/2+1=n(n-1)(n-2)/6+n+(n-1)n/2+1

Mediante el programa wxMaxima comprobamos la identidad entre este resultado y el propuesto. En el recorte de pantalla observamos además que las expresiones se pueden simplificar bastante:

Por una parte, hemos obtenido una fórmula manejable:

Por otra, se ha comprobado en el razonamiento que C₃(n)= C₃(n-1)+C₂(n-1) y, por tanto, que es válida la sugerencia de:

C₃(n) = binomial(n,0) + binomial(n,1) + binomial(n,2) + binomial(n,3)

Con esta comprobación se ha descubierto también que estos números son la suma de los cuatro primeros elementos de la fila n del triángulo de Pascal:

Esta propiedad nos permite identificar los números de pastel con el número de subconjuntos de un conjunto de n elementos cuyo cardinal no supere los tres elementos. Expresado de otra forma, la suma del número de combinaciones de n elementos tomados de 0, 1, 2 o 3 elementos.

Al igual que ocurría con la sucesión del catering perezoso, la existencia de una fórmula tan directa hace inútil la búsqueda de otro algoritmo o función. Basta organizar una tabla con esa fórmula:

Coinciden los valores extraídos del triángulo de Pascal y con los publicados en https://oeis.org/A000125,

 Recurrencia

Con la fórmula básica se puede llegar a números de orden grande, pero quizás se prefiera una recurrencia por la rapidez de cálculo. En la página de OEIS citada se propone la siguiente:

a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4).

Bastará, pues, crear una columna con los cuatro primeros en una hoja de cálculo y después aplicar la fórmula a esos cuatro y rellenar hacia abajo hasta el punto que deseemos.

Comienzo:

Escribimos los cuatro primeros, y al quinto le aplicamos la fórmula de recurrencia.

Segundo paso

Rellenamos hacia bajo la fórmula:

De esta forma, en segundos, llegamos al orden que deseemos:

Las recurrencias lineales son muy útiles para construir tablas de forma casi instantánea.