Cálculo de los índices lexicográficos de la partición de enteros

Question

Si ordenamos todas las particiones de un entero en un orden lexicográfico, ¿cómo podemos calcular la posición de cada partición en este orden sin tener que enumerar explícitamente todas las demás particiones que la preceden? ¿Cómo se hace la modificación cuando restringimos la parte máxima y el número de particiones? Me gustaría utilizar estos índices en la búsqueda en bases de datos. Sería útil incluso si obtenemos una fórmula de forma cerrada cuando el número de partes se restringe a un número pequeño, por ejemplo $<15$ y el número entero es $< 100$ con cada parte $<5$ .

Answer 1

El orden lexicográfico parece más complejo que el orden lexicográfico inverso.
En orden lex inverso, resulta sencillo: definir p(n,k) como el número de particiones de n con la mayor parte k (alternativamente con no más de k partes). Tiene la conocida recursión p(n,k)=p(n,k-1)+p(n-k,k). Entonces, para cualquier partición, digamos 5311, aquí con suma n=10, hacer
p(5+3+1+1,5 -1) = 23
p(3+1+1,3 -1) = 3
p(1+1,1 -1) = 0
p(1,1 -1) = 0
súmalos para obtener 26, y réstalo de p(5+3+1+1)= 42 para obtener el rango = 16. Para ver por qué esto funciona, mira las particiones transpuestas contadas por p(10,4), p(5,2) etc que se recortan de.

Answer 2

No estoy seguro de que la respuesta general esté en este documento Algoritmo 515: Generación de un vector a partir del índice lexicográfico (ya que no lo he leído, no está disponible en línea), pero da el algoritmo para las combinaciones, es decir, de combinación a índice y de índice a combinación.

En The Art Of Computer Programming (TAOCP) de Knuth, Semi-numerical Algorithms también tiene ejemplos y referencias de tales algoritmos (como se menciona en el comentario).

En combinatoria general esto se llama clasificación y desclasificación (como se menciona en el comentario).

Dado que los elementos de una secuencia combinatoria están ordenados lexicográficamente y el hecho de que se pueden contar (eficientemente) los elementos combinatorios hasta $N$ .

El algoritmo general para hallar el índice de cualquier objeto combinatorio en orden lexicográfico sería (a grandes rasgos):

1. Para k en 0..n-1
2. Contar cuántos elementos de longitud n-1-k tienen el k-ésimo elemento menor que comb[k]
3. es la suma de los contadores.

En otras palabras, el algoritmo más general para clasificar (ordenar) objetos combinatorios (calcular el índice en el orden dado el objeto combinatorio), aunque no necesariamente eficiente, es:

Índice = Calcula cuántos vienen antes dado el orden y la combinatoria y añadir $1$

A continuación se presenta el algoritmo (general) asociado para desclasificar. En concreto $C(n)$ sea el número de tamaños $n$ objetos combinatorios de cierto tipo que satisfacen una relación de recurrencia de la forma:

$$C(n) = u(n)C(n-1) + v(n)C(n-2) + w(n)C(n-3) + ..$$

donde el coeficiente $u(n)$ , $v(n)$ , $w(n)$ . . . son no negativos. Llamamos a los objetos correspondientes al término $u(n)C(n-1)$ objetos de del primer tipo, los correspondientes a $v(n)C(n-2)$ de los objetos segundo tipo, y así sucesivamente. Un algoritmo para desclasificar puede ser el siguiente siguiente:

Algoritmo Unrank. Generar el $r$ -th ( $0 \ge r \lt C(n)$ ) objeto combinatorio.

1. Establecer $U = u(n)C(n-1)$ , $V = v(n)C(n-2)$ , $W = W(n)C(n-3)$ etc.
2. Si $r<U$ entonces devuelve el $r$ -ésimo objeto del primer tipo de tamaño $n-1$ (recursividad).
3. Si $r<U+V$ entonces devuelve el $(r-U)$ -ésimo objeto del segundo tipo de tamaño $n-2$ (recursividad).
4. Si $r<U+V+W$ entonces devuelve el $(r-U-V)$ -ésimo objeto del tercer tipo de tamaño $n-3$ (recursividad).
5. (Y así sucesivamente).

(referencia: http://maths-people.anu.edu.au/~brent/pd/Arndt-tesis.pdf pp 57)

Por supuesto, el algoritmo anterior se basa en el hecho de que existe un orden lexicográfico y el recuento de elementos combinatorios (por ejemplo, combinaciones, permutaciones, particiones, etc.) es eficiente (lo que no siempre es el caso).

Tenga en cuenta especialmente que las particiones son más fáciles de generar en orden lexicográfico inverso (es decir descendente ). Una tesis doctoral sobre la codificación de particiones como lexicográficamente ascendente (en lugar de descendente ) y la referencia ALGORITMOS RAPIDOS PARA GENERAR PARTICIONES INTEGRAS, ANTOINE ZOGHBIU and IVAN STOJMENOVIC, 1998

Answer 3

Quizá una posibilidad sea multiplicar cada partición en orden lexicográfico por el número que representa su posición en la secuencia. Almacenando las particiones de esta forma recuperas el orden dividiendo el valor almacenado de la partición por el entero original a particionar. Y recuperas los términos de partición correctos dividiéndolos por el orden. No sé cuál es el modelo de datos, pero por supuesto de alguna manera, junto con la serie de cada "nueva partición transformada" también tendrías que almacenar el valor original del entero a particionar, para comparar con él.