algorithm - repeticion - Número de permutaciones de elementos n con exactamente k inversiones

permutaciones sin repeticion

Question

Estoy tratando de resolver eficientemente SPOJ Problema 64: Permutaciones .

Sea A = [a1, a2, ..., an] una permutación de números enteros 1,2, ..., n. Un par de índices (i, j), 1 <= i <= j <= n, es una inversión de la permutación A si ai> aj. Nos dan números enteros n> 0 y k> = 0. ¿Cuál es el número de permutaciones de n elementos que contienen exactamente k inversiones?

Por ejemplo, el número de permutaciones de 4 elementos con exactamente 1 inversión es igual a 3.

Para hacer que el ejemplo dado sea más fácil de ver, aquí están las tres permutaciones de 4 elementos con exactamente 1 inversión:

(1, 2, 4, 3)
(1, 3, 2, 4)
(2, 1, 3, 4)

En la primera permutación, 4> 3 y el índice de 4 es menor que el índice de 3. Esta es una inversión única. Como la permutación tiene exactamente una inversión, es una de las permutaciones que estamos tratando de contar.

Para cualquier secuencia dada de n elementos, el número de permutaciones es factorial (n). Por lo tanto, si utilizo la forma de fuerza bruta n ² para contar el número de inversiones para cada permutación y luego verificar si son iguales a k, la solución a este problema tendría la complejidad de tiempo O (n! * N ² ).

Investigación previa

Un problema secundario de este problema se solicitó anteriormente here en StackOverflow. Se proporcionó una solución O (n log n) que utiliza ordenamiento de fusión que cuenta el número de inversiones en una sola permutación. Sin embargo, si utilizo esa solución para contar el número de inversiones para cada permutación, todavía obtendría una complejidad de tiempo de O (n! * N log n) que todavía es muy alta en mi opinión.

Esta pregunta exacta también se hizo anteriormente en Stack Overflow pero no recibió respuestas.

Mi objetivo es evitar la complejidad factorial que proviene de la iteración a través de todas las permutaciones. Idealmente, me gustaría una fórmula matemática que ofrezca la respuesta a esto para cualquier n y k, pero no estoy seguro de si existe una.

Si no hay una fórmula matemática para resolver esto (lo cual dudo) también he visto personas que dan pistas de que es posible una solución de programación dinámica eficiente. Usando DP u otro enfoque, realmente me gustaría formular una solución que sea más eficiente que O (n! * N log n), pero no estoy seguro de por dónde empezar.

Cualquier sugerencia, comentario o sugerencia son bienvenidos.

EDITAR: He respondido el problema a continuación con un enfoque de DP para calcular los números de Mahonian .

Answer 1

Es un día después y he logrado resolver el problema utilizando la programación dinámica. La envié y mi código fue aceptado por SPOJ, así que creo que compartiré mis conocimientos aquí para cualquier persona que esté interesada en el futuro.

Después de buscar en la página de Wikipedia que analiza la inversión en matemáticas discretas , encontré una recomendación interesante al final de la página.

Números de permutaciones de n elementos con k inversiones; Números de Mahonia : A008302

Hice clic en el enlace a OEIS y me mostró una secuencia infinita de enteros llamados los números del Triángulo de Mahonian.

1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 6, 5, 3, 1, 1, 4, 9, 15, 20, 22, 20, 15, 9, 4, 1, 1, 5, 14, 29, 49, 71, 90, 101, 101, 90, 71, 49, 29, 14, 5, 1, 1, 6, 20, 49, 98, 169, 259, 359, 455, 531, 573, 573, 531, 455, 359, 259, 169, 98, 49, 20, 6, 1. . .

Tenía curiosidad acerca de cuáles eran estos números ya que me parecían familiares. Entonces me di cuenta de que había visto la subsecuencia 1, 3, 5, 6, 5, 3, 1 antes. De hecho, esta fue la respuesta al problema para varios pares de (n, k), a saber (4, 0), (4, 1), (4, 2), (4, 3), (4, 4) , (4, 5), (4, 6). Miré lo que había en ambos lados de esta subsecuencia y me sorprendió ver que todas las respuestas eran válidas (es decir, mayores de 0 permutaciones) para n <4 y n> 4.

La fórmula para la secuencia fue dada como:

coeficientes en la expansión del Producto_ {i = 0..n-1} (1 + x + ... + x ^ i)

Esto fue lo suficientemente fácil para que lo entendiera y verificara. Básicamente podría tomar cualquier n y conectar en la fórmula. Entonces, el coeficiente para el término x ^k sería la respuesta para (n, k).

Voy a mostrar un ejemplo para n = 3.

(x 0 )(x 0 + 1 )(x 0 + x 1 + x 2 ) = (1)(1 + x)(1 + x + x 2 ) = (1 + x)(1 + x + x 2 ) = 1 + x + x + x 2 + x 2 + x 3 = 1 + 2x + 2x 2 + x 3

La expansión final fue 1 + 2x + 2x 2 + x 3 y los coeficientes de los términos x ^k fueron 1, 2, 2 y 1 para k = 0, 1, 2, 3, respectivamente. Esto simplemente pasa a ser todos los números válidos de inversiones para permutaciones de 3 elementos.

1, 2, 2, 1 es la tercera fila de los números de Mahonian cuando se presentan en una tabla de la siguiente manera:

1
1 1
1 2 2 1
1 3 5 6 5 3 1
etc.

Así que, básicamente, calcular mi respuesta se redujo simplemente a calcular la fila n Mahonian y tomar el elemento kth con k comenzando en 0 e imprimiendo 0 si el índice estaba fuera de rango. Este fue un caso simple de programación dinámica de abajo hacia arriba, ya que cada fila podría usarse para calcular fácilmente la primera fila de i +.

A continuación se muestra la solución de Python que utilicé, que se ejecutó en solo 0.02 segundos. El límite de tiempo máximo para este problema fue de 3 segundos para sus casos de prueba dados y recibí un error de tiempo de espera antes, así que creo que esta optimización es bastante buena.

def mahonian_row(n):
''''''Generates coefficients in expansion of
Product_{i=0..n-1} (1+x+...+x^i)
**Requires that n is a positive integer''''''
# Allocate space for resulting list of coefficients?
# Initialize them all to zero?
#max_zero_holder = [0] * int(1 + (n * 0.5) * (n - 1))
# Current max power of x i.e. x^0, x^0 + x^1, x^0 + x^1 + x^2, etc.
# i + 1 is current row number we are computing
i = 1
# Preallocate result
# Initialize to answer for n = 1
result = [1]
while i < n:
# Copy previous row of n into prev
prev = result[:]
# Get space to hold (i+1)st row
result = [0] * int(1 + ((i + 1) * 0.5) * (i))
# Initialize multiplier for this row
m = [1] * (i + 1)
# Multiply
for j in range(len(m)):
for k in range(len(prev)):
result[k+j] += m[j] * prev[k]
# Result now equals mahonian_row(i+1)
# Possibly should be memoized?
i = i + 1
return result
def main():
t = int(raw_input())
for _ in xrange(t):
n, k = (int(s) for s in raw_input().split())
row = mahonian_row(n)
if k < 0 or k > len(row) - 1:
print 0
else:
print row[k]
if __name__ == ''__main__'':
main()

No tengo idea de la complejidad del tiempo, pero estoy absolutamente seguro de que este código puede mejorarse a través de la memoization ya que hay 10 casos de prueba dados y los cálculos de casos de prueba anteriores se pueden utilizar para "hacer trampa" en casos de prueba futuros. Haré esa optimización en el futuro, pero espero que esta respuesta en su estado actual ayude a cualquiera que intente este problema en el futuro, ya que evita el enfoque ingenuo de complejidad factorial de generar e iterar a través de todas las permutaciones.

Answer 2

La solución necesita algunas explicaciones. Denotemos el número de permutaciones con n elementos que tienen exactamente k inversiones por I (n, k)

Ahora I (n, 0) siempre es 1. Para cualquier n existe una y solo una permutación que tiene 0 inversiones, es decir, cuando la secuencia está cada vez más ordenada

Ahora I (0, k) siempre es 0 ya que no tenemos la secuencia en sí

Ahora para encontrar el I (n, k), tomemos un ejemplo de secuencia que contiene 4 elementos {1,2,3,4}

para n = 4 a continuación se enumeran las permutaciones y se agrupan por número de inversiones

|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
| 1234 | 1243 | 1342 | 1432 | 2431 | 3421 | 4321 |
| | 1324 | 1423 | 2341 | 3241 | 4231 | |
| | 2134 | 2143 | 2413 | 3412 | 4312 | |
| | | 2314 | 3142 | 4132 | | |
| | | 3124 | 3214 | 4213 | | |
| | | | 4123 | | | |
| | | | | | | |
|I(4,0)=1 |I(4,1)=3 |I(4,2)=5 |I(4,3)=6 |I(4,4)=5 |I(4,5)=3 |I(4,6)=1 |
| | | | | | | |

Ahora para encontrar el número de permutaciones con n = 5 y para cada k posible podemos derivar la recurrencia I (5, k) de I (4, k) insertando el elemento nth (más grande) (5) en algún lugar de cada permutación en el Permutaciones previas, de modo que el número resultante de inversiones es k

por ejemplo, I (5,4) no es más que el número de permutaciones de la secuencia {1,2,3,4,5} que tiene exactamente 4 inversiones cada una. Observemos I (4, k) ahora arriba hasta que la columna k = 4 el número de inversiones sea <= 4 Ahora coloquemos el elemento 5 como se muestra a continuación

|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
| |5|1234 | 1|5|243 | 13|5|42 | 143|5|2 | 2431|5| | 3421 | 4321 |
| | 1|5|324 | 14|5|23 | 234|5|1 | 3241|5| | 4231 | |
| | 2|5|134 | 21|5|43 | 241|5|3 | 3412|5| | 4312 | |
| | | 23|5|14 | 314|5|4 | 4132|5| | | |
| | | 31|5|24 | 321|5|4 | 4213|5| | | |
| | | | 412|5|3 | | | |
| | | | | | | |
| 1 | 3 | 5 | 6 | 5 | | |
| | | | | | | |

Cada una de las permutaciones anteriores que contiene 5 tiene exactamente 4 inversiones. Entonces, la permutación total con 4 inversiones I (5,4) = I (4,4) + I (4,3) + I (4,2) + I (4,1) + I (4,0) = 1 + 3 + 5 + 6 + 5 = 20

Similarmente para I (5,5) de I (4, k)

|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
| 1234 | |5|1243 | 1|5|342 | 14|5|32 | 243|5|1 | 3421|5| | 4321 |
| | |5|1324 | 1|5|423 | 23|5|41 | 324|5|1 | 4231|5| | |
| | |5|2134 | 2|5|143 | 24|5|13 | 341|5|2 | 4312|5| | |
| | | 2|5|314 | 31|5|44 | 413|5|2 | | |
| | | 3|5|124 | 32|5|14 | 421|5|3 | | |
| | | | 41|5|23 | | | |
| | | | | | | |
| | 3 | 5 | 6 | 5 | 3 | |
| | | | | | | |

Entonces, la permutación total con 5 inversiones I (5,5) = I (4,5) + I (4,4) + I (4,3) + I (4,2) + I (4,1) = 3 + 5 + 6 + 5 + 3 = 22

Entonces I(n, k) = sum of I(n-1, ki) such that i < n && ki >= 0

Además, k puede subir hasta n * (n-1) / 2 esto ocurre cuando la secuencia está ordenada en orden decreciente https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/insertion/pages/ar01s04s01.html http://www.algorithmist.com/index.php/SPOJ_PERMUT1

#include <stdio.h>
int dp[100][100];
int inversions(int n, int k)
{
if (dp[n][k] != -1) return dp[n][k];
if (k == 0) return dp[n][k] = 1;
if (n == 0) return dp[n][k] = 0;
int j = 0, val = 0;
for (j = 0; j < n && k-j >= 0; j++)
val += inversions(n-1, k-j);
return dp[n][k] = val;
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
int n, k, i, j;
scanf("%d%d", &n, &k);
for (i = 1; i <= n; i++)
for (j = 0; j <= k; j++)
dp[i][j] = -1;
printf("%d/n", inversions(n, k));
}
return 0;
}

Answer 3

Podemos hacer uso de la programación dinámica para resolver este problema. tenemos n lugares para llenar con números de 1 a n, _ _ _ _ _ _ _ _ _ n toma 7 =, en primer lugar podemos alcanzar la inversión n-1 y al menos 0, de manera similar para el segundo lugar podemos lograr la inversión n-2 máxima y, al menos, 0, en general, podemos alcanzar las inversiones más altas con un índice i, independientemente de la elección del número que hayamos colocado antes. Nuestra fórmula recursiva se verá así:

f (n, k) = f (n-1, k) + f (n-1, k-1) + f (n-1, k-2) ............. f (n-1, max (0, k- (n-1)) sin inversión una inversión dos inversiones n-1 podemos lograr 0 inversiones colocando el más pequeño del número restante de la inversión establecida (1, n) 1 colocando el segundo más pequeño y así sucesivamente,

La condición base para nuestra fórmula recursiva será.

if (i == 0 && k == 0) devuelve 1 (permutación válida)

if (i == 0 && k! = 0) devuelve 0 (permutación no válida).

si dibujamos el árbol de recursión veremos los subproblemas repetidos varias veces, por lo tanto, usaremos la memoria para reducir la complejidad a O (n * k).

Answer 4

Si existe una solución de programación dinámica, es probable que haya una forma de hacerlo paso a paso, utilizando los resultados para permutaciones de longitud n para ayudar con los resultados para permutaciones de longitud n + 1.

Dada una permutación de longitud n - valores 1-n, puede obtener una permutación de longitud n + 1 agregando valor (n + 1) en n + 1 posiciones posibles. (n + 1) es más grande que cualquiera de 1-n, por lo que el número de inversiones que creas cuando haces esto depende de dónde lo agregues: agrégalo en la última posición y no creas inversiones, agrégalo en la última posición posicione y cree una inversión, y así sucesivamente - mire hacia atrás a los n = 4 casos con una inversión para verificar esto.

Entonces, si considera uno de los n + 1 lugares donde puede agregar (n + 1) si lo agrega en el lugar j contando desde la derecha, la última posición como posición 0 el número de permutaciones con K inversiones que esto crea es el número de Permutaciones con inversiones Kj en n lugares.

Entonces, si en cada paso cuenta el número de permutaciones con inversiones K para todas las K posibles, puede actualizar el número de permutaciones con inversiones K para longitud n + 1 utilizando el número de permutaciones con inversiones K para longitud n.

Answer 5

Un problema importante en el cálculo de estos coeficientes es el tamaño del orden del producto resultante. El producto polinomial i = 1,2, .., n {(1 + x). (1 + x + x ^ 2) .... (1 + x + x ^ 2 + .. + x ^ i) + ... (1 + x + x ^ 2 + ... + x ^ n) tendrá un orden equivalente a n * (n + 1). En consecuencia, esto pone un límite computacional restrictivo en el proceso. Si usamos un proceso en el que los resultados anteriores para el Producto para n-1 se usan en el proceso para el cálculo del Producto para n, estamos considerando el almacenamiento de (n-1) * n enteros. Es posible usar un proceso recursivo, que será mucho más lento, y nuevamente se limita a números enteros menores que la raíz cuadrada del tamaño común del número entero. El siguiente es un código recursivo aproximado y listo para este problema. La función mahonian (r, c) devuelve el coeficiente c th para el r r Producto. Pero, de nuevo, es extremadamente lento para productos grandes mayores de 100 o menos. Ejecutando esto se puede ver que la recursión claramente no es la respuesta.

unsigned int numbertheory::mahonian(unsigned int r, unsigned int c)
{
unsigned int result=0;
unsigned int k;
if(r==0 && c==0)
return 1;
if( r==0 && c!=0)
return 0;
for(k=0; k <= r; k++)
if(r > 0 && c >=k)
result = result + mahonian(r-1,c-k);
return result;
}

Como cuestión de interés, he incluido lo siguiente, que es una versión c ++ de Sashank, que es mucho más rápida que mi ejemplo de recursión. Tenga en cuenta que uso la biblioteca de armadillo.

uvec numbertheory::mahonian_row(uword n){
uword i = 2;
uvec current;
current.ones(i);
uword current_size;
uvec prev;
uword prev_size;
if(n==0){
current.ones(1);
return current;
}
while (i <= n){ // increment through the rows
prev_size=current.size(); // reset prev size to current size
prev.set_size(prev_size); // set size of prev vector
prev= current; //copy contents of current to prev vector
current_size =1+ (i*(i+1)/2); // reset current_size
current.zeros(current_size); // reset current vector with zeros
for(uword j=0;j<i+1; j++) //increment through current vector
for(uword k=0; k < prev_size;k++)
current(k+j) += prev(k);
i++; //increment to next row
}
return current; //return current vector
}
uword numbertheory::mahonian_fast(uword n, uword c) {
**This function returns the coefficient of c order of row n of
**the Mahonian numbers
// check for input errors
if(c >= 1+ (n*(n+1)/2)) {
cout << "Error. Invalid input parameters" << endl;
}
uvec mahonian;
mahonian.zeros(1+ (n*(n+1)/2));
mahonian = mahonian_row(n);
return mahonian(c);
}