algorithm - probabilidad - permutaciones y combinaciones pdf

Algoritmo para contar el número de bloques válidos en una permutación (7)

Posible duplicado:
Encontrar subsecuencias ordenadas en una permutación

Dada una matriz A que tiene una permutación de 1,2, ..., n. Un subbloque A [i..j]
de una matriz A se llama bloque válido si todos los números que aparecen en A [i..j]
Son números consecutivos (no pueden estar en orden）).

Dada una matriz A = [7 3 4 1 2 6 5 8] los bloques válidos son [3 4], [1,2], [6,5],
[3 4 1 2], [3 4 1 2 6 5], [7 3 4 1 2 6 5], [7 3 4 1 2 6 5 8]

Así que la cuenta para la permutación anterior es 7.

Proporcione un algoritmo O (n log n) para contar el número de bloques válidos.

(Este es un intento de hacer este N.log (N) en el peor de los casos. Desafortunadamente, es incorrecto: a veces se descuentan. Supone incorrectamente que puede encontrar todos los bloques mirando solo pares adyacentes de bloques válidos más pequeños. De hecho, tiene para ver trillizos, cuádruples, etc., para obtener todos los bloques más grandes.)

Lo haces con una estructura que representa un subbloque y una cola para los subbloques.

struct c_subblock { int index ; /* index into original array, head of subblock */ int width ; /* width of subblock > 0 */ int lo_value; c_subblock * p_above ; /* null or subblock above with same index */ };

Asigne una matriz de subbloques del mismo tamaño que la matriz original e inicie cada subbloque para que tenga exactamente un elemento. Añadirlos a la cola a medida que avanza. Si comienzas con la matriz [7 3 4 1 2 6 5 8] terminarás con una cola como esta:

cola: ([7,7] [3,3] [4,4] [1,1] [2,2] [6,6] [5,5] [8,8])

Los valores de {index, width, lo_value, p_above} para el subbloque [7,7] serán {0, 1, 7, null}.

Ahora es facil Perdona el pseudocódigo c-ish.

loop { c_subblock * const p_left = Pop subblock from queue. int const right_index = p_left.index + p_left.width; if ( right_index < length original array ) { // Find adjacent subblock on the right. // To do this you''ll need the original array of length-1 subblocks. c_subblock const * p_right = array_basic_subblocks[ right_index ]; do { Check the left/right subblocks to see if the two merged are also a subblock. If they are add a new merged subblock to the end of the queue. p_right = p_right.p_above; } while ( p_right ); } }

Esto los encontrará a todos, creo. Normalmente es O (N log (N)), pero será O (N ^ 2) para una lista completamente ordenada o no ordenada. Sin embargo, creo que hay una respuesta a esto: cuando creas la matriz original de subbloques, buscas secuencias clasificadas y no ordenadas y las añades como subbloques de nivel base. Si mantiene un recuento, auméntelo en (ancho * (ancho + 1)) / 2 para el nivel base. Eso te dará el recuento INCLUYENDO todos los subbloques de 1 longitud.

Después de eso, simplemente use el bucle de arriba, haciendo estallar y empujando la cola. Si está contando, tendrá que tener un multiplicador en los subbloques izquierdo y derecho y multiplicarlos para calcular el incremento. El multiplicador es el ancho del subbloque de nivel de base más a la izquierda (para p_left) o a la derecha (para p_right).

Espero que esto sea claro y no demasiado buggy. Solo lo estoy golpeando, así que incluso puede estar mal. [Nota posterior. Esto no funciona después de todo. Vea la nota abajo.]

Como todos los demás, simplemente estoy desechando esto ... funciona para el ejemplo que se muestra a continuación, ¡pero YMMV!

La idea es contar el número de subbloques ilegales y restarlos del número total posible. Contamos los ilegales al examinar cada elemento de la matriz y descartar sub-bloques que incluyen el elemento pero no su predecesor o sucesor.

Para cada i en [1, N], calcule B [A [i]] = i.
Let Count = el número total de subbloques con longitud> 1, que es N-Choose-2 (uno para cada combinación posible de índice inicial y final).
Para cada uno, considérese A [i]. Ignorando los casos de borde, sea x = A [i] -1, y sea y = A [i] +1. Un [i] no puede participar en ningún subbloque que no incluya x o y. Sea iX = B [x] e iY = B [y]. Hay varios casos a tratar independientemente aquí. El caso general es que iX<i<iY<i . En este caso, podemos eliminar el subbloque A [iX + 1 .. iY-1] y todos los bloques intermedios que contengan i. Hay (i - iX + 1) * (iY - i + 1) tales subbloques, así que llame a este número Eliminado. (Otros casos quedan como un ejercicio para el lector, como son los casos de borde). Set Count = Count - Eliminated.
Devuelva la cuenta.

El costo total parece ser N * (costo del paso 2) = O (N).

WRINKLE: En el paso 2, debemos tener cuidado de no eliminar cada sub-intervalo más de una vez. Podemos lograr esto eliminando solo los subintervalos que se encuentran total o parcialmente a la derecha de la posición i.

Ejemplo:
A = [1, 3, 2, 4] B = [1, 3, 2, 4]

Recuento inicial = (4 * 3) / 2 = 6

i = 1: A [i] = 1, por lo que necesita sub-bloques con 2 en ellos. Podemos eliminar [1,3] de la consideración. Eliminado = 1, Cuenta -> 5.

i = 2: A [i] = 3, por lo que necesita sub-bloques con 2 o 4 en ellos. Esto descarta [1,3] pero ya lo consideramos cuando miramos a la derecha desde i = 1. Eliminado = 0.

i = 3: A [i] = 2, por lo que necesita sub-bloques con [1] o [3] en ellos. Podemos eliminar [2,4] de la consideración. Eliminado = 1, Cuenta -> 4.

i = 4: A [i] = 4, por lo que necesitamos sub-bloques con [3] en ellos. Esto descarta [2,4], pero ya lo hemos tenido en cuenta cuando miramos a la derecha desde i = 3. Eliminado = 0.

Cuenta final = 4, correspondiente a los sub-bloques [1,3,2,4], [1,3,2], [3,2,4] y [3,2].

Esta pregunta involucra un poco de un "truco matemático" pero es bastante sencillo una vez que lo entiendes. Sin embargo, el resto de mi solución no se ajustará a los criterios O (n log n).

La parte de matemáticas :

Para dos números consecutivos, su suma es 2k+1 donde k es el elemento más pequeño. Para tres es 3k+3 , 4: 4k+6 y para N tales números es Nk + sum(1,N-1) . Por lo tanto, necesita dos pasos que se pueden hacer simultáneamente:

Crea la suma de todos los sub-arrays.
Determine el elemento más pequeño de una sub-matriz.

La parte de programación dinámica

Cree dos tablas utilizando los resultados de las entradas de la fila anterior para construir las entradas de cada fila sucesiva. Desafortunadamente, estoy totalmente equivocado, ya que esto aún requeriría n ^ 2 comprobaciones de sub-array. Ugh!

La matriz original no contiene duplicados, por lo que debe ser un bloque consecutivo. Llamemos a este bloque (1 ~ n). Podemos probar si el bloque (2 ~ n) es consecutivo verificando si el primer elemento es 1 o n, que es O (1). Del mismo modo, podemos probar el bloque (1 ~ n-1) verificando si el último elemento es 1 o n.

No puedo convertir esto en una solución que funcione, pero tal vez ayude a alguien ...

Mi proposición

PASO = 2 // cantidad de número examinado

B [0,0,0,0,0,0,0,0]

B [1,1,0,0,0,0,0,0]

VÁLIDO (A, B) - si no es válido mover uno

B [0,1,1,0,0,0,0,0]

VÁLIDO (A, B) - si es válido, mueve uno y paso

B [0,0,0,1,1,0,0,0]

VÁLIDO (A, B)

B [0,0,0,0,0,1,1,0]

PASO = 3

B [1,1,1,0,0,0,0,0] no está bien

B [0,1,1,1,0,0,0,0] ok

B [0,0,0,0,1,1,1,0] no está bien

PASO = 4

B [1,1,1,1,0,0,0,0] no está bien

B [0,1,1,1,1,0,0,0] ok

.....

CON <- 0 STEP <- 2 i <- 0 j <- 0 WHILE(STEP <= LEN(A)) DO j <- STEP WHILE(STEP <= LEN(A) - j) DO IF(VALID(A,i,j)) DO CON <- CON + 1 i <- j + 1 j <- j + STEP ELSE i <- i + 1 j <- j + 1 END END STEP <- STEP + 1 END

El método válido comprueba que todos los elementos son consecutivos.

Nunca probado pero, podría estar bien

Ok, he bajado a 1 repetición porque puse 200 recompensas en una pregunta relacionada: encontrar subsecuencias ordenadas en una permutación, así que no puedo dejar comentarios por un tiempo.

Tengo una idea: 1) Localizar todos los grupos de permutación. Ellos son: (78), (34), (12), (65). A diferencia de la teoría de grupos, su orden y posición, y si son asuntos adyacentes. Entonces, un grupo (78) puede representarse como una estructura (7, 8, false) , mientras que (34) sería (3,4,true) . Estoy usando la notación de Python para las tuplas, pero en realidad podría ser mejor usar una clase completa para el grupo. Aquí verdadero o falso significa contiguo o no. Dos grupos son "adyacentes" si (max(gp1) == min(gp2) + 1 or max(gp2) == min(gp1) + 1) and contigous(gp1) and contiguos(gp2) . Esta no es la única condición para que la union(gp1, gp2) sea contigua, porque (14) y (23) combinan en (14) muy bien. Esta es una gran pregunta para la tarea de clase, pero una terrible para la entrevista. Sospecho que esto es tarea.

Sólo algunos pensamientos:

A primera vista, esto suena imposible: una matriz completamente ordenada tendría sub-bloques válidos O (n ² ) .

Por lo tanto, necesitaría contar más de un subbloque válido a la vez. La comprobación de la validez de un subbloque es O (n) . Comprobar si un subbloque está completamente ordenado también es O (n) . Un subbloque completamente ordenado contiene n · (n - 1) / 2 subbloques válidos, que puede contar sin romper este subbloque.

Ahora, toda la matriz es obviamente siempre válida. Para un enfoque de dividir y conquistar, necesitarías dividirlo. Hay dos puntos de ruptura concebibles: la ubicación del elemento más alto y la del elemento más bajo. Si divide la matriz en dos en uno de estos puntos, incluido el extremo en la parte que contiene el elemento del segundo al extremo, no puede haber un subbloque válido que cruce este punto de ruptura.

Al elegir siempre el extremo que produce una división más uniforme, esto debería funcionar bastante bien (promedio O (n log n) ) para matrices "aleatorias". Sin embargo, puedo ver problemas cuando su entrada es algo como (1 5 2 6 3 7 4 8) , que parece producir un comportamiento O (n ² ) . (1 4 7 2 5 8 3 6 9) sería similar (espero que vea el patrón). Actualmente no veo ningún truco para detectar este tipo de caso peor, pero parece que requiere otras técnicas de división.