Reducir La Permutación

Question

Necesito un algoritmo que puede asignar las pistas en una permutación a un único número, sino también a reducir los números subsiguientes.

Así que una carrera es un proceso secuencial de un conjunto de números en una permutación que se ordena y en orden.En la lista, 1;2;3;5;6;4 hay dos pistas, 1;2;3 y 5;6.Quiero reemplazar con un solo número, un mínimo, de modo que si, después de la eliminación de carreras, tenemos una permutación de los 4 elementos, la permutación utiliza los números del 1 ...4.En el anterior, tenemos que reducir las dos carreras.la primera carrera será de 1, 4 transforma a 2, y [5;6] se transforma a 3, para celebrar el segundo criterio.Si yo pusiera la reducción de la permutación, a continuación, expanda los elementos dentro de la asignación y ordenación de la original de permutación que voy a obtener el mismo resultado.La resultante de la permutación no debería tener ningún ejecuta en él.

Por ejemplo (he resaltado las carreras):

(1;2;3;4;5;6) => 1 //Mappings: 1->1;2;3;4;5;6
(2;3;4);1;(5;6) => 2 1 3 // Mappings: 2->2;3;4, and 3->5;6
(3;4);(1;2);(5;6) => 2 1 3 // Mappings: 2->3;4, and 1->1;2 and 3->5;6

por ahora, estoy pasando por encima de la lista y hacer una lista de listas, la agrupación de las pistas.En realidad la segunda parte es la parte más difícil para hacer una solución limpia.He pensado en el enfoque ingenuo, por curiosidad, si alguien tiene algún truco que puede hacerlo mejor que la mía, yo estoy en como O( 2n + n log n),

• la sustitución de las pistas con la cabeza del elemento de la ejecución y la inserción de los datos en una tabla hash (por la capacidad de recuperación)
• clasificación para crear un mapa de la falta de dígitos con los que se ordenan índice.[1;6;5;4] sería la salida de [(1,1);(4,2);(5,3);(6,4)]
• la sustitución de la lista en el paso 1 con el mapa creado en el paso 2 y la actualización de la tabla hash para la traducción.

se ejecuta a través de un ejemplo, de nuevo:

step 1: replace runs with the head element of the run and inserting data into a hash table  
    [1;3;4;2;5;6;] -> [1;3;2;5]  
step 2: sort array to create map  
    [1235], so we know that, in the previous array, 1 maps to 1, 2 to 2, 3 to 3, 4 to 5.  
step 3: do above translation on array from step one. 
    [1;3;2;4]

Si yo pusiera esta permutación y reconstruir:[1;2;3;4], 3->3;4 y 4->5;6 puedo conseguir, 1;2;3;4;5;6.También se ordena.

Estoy usando listas, por lo que un enfoque funcional, sería preferible.No hay código necesario.Todas las ideas, por supuesto, bienvenido.

EDITAR:

mweerden:

No es claro para mí lo que las condiciones precisas en la cartografía.¿Por qué no es permitido simplemente para producir la permutación [1,2,...,N] para una permutación con N se ejecuta?Parece que prefieren mapa de una carrera a un número desde el que se ejecutan, pero, como esto no siempre es posible) que parecen permitir una cierta libertad.–

Yo no prefiero a un mapa de ejecutar a un número dentro de los que se ejecutan (mirar arriba!), pero yo necesidad de preservar un el pedido.La permutación [1;2;3...N] es una carrera, y por lo tanto puede ser reducido aún más.Es por eso que no es válido.El orden importa en la continuación de las operaciones en otro algoritmo, pero los elementos individuales pueden ser ampliadas en el fin de rescatar el original de permutación.

Answer 1

Notación:

• el recuento empieza en 1
• l.i es el elemento i de la lista l
• l+m es la concatenación de listas l y m
• una carrera es una máxima de la sublista que es una lista de [n,n+1,n+2,...,m] para algunos n y m con n <= m

Así, se nos da una permutación p de la lista [1,2,...,N].Dividimos p en pistas r_1,r_2,...,r_M tal que p = r_1+r_2+...+r_M.Entonces estamos buscando una permutación q de [1,2,...,M] tal que r_(q.1)+r_(q.2)+...+r_(q.M) = [1,2,...,N].

Por ejemplo, si p = [1,3,4,2,5,6], hemos N=6, M=4, r_1 = [1], r_2 = [3,4], r_3 = [2] y r_4 = [5,6].En este caso necesitamos q para ser [1,3,2,4] como r_1+r_3+r_2+r_4 = [1]+[2]+[3,4]+[5,6] = [1,2,3,4,5,6].

Tenga en cuenta que q no puede contener pistas de longitud mayor que uno por definición;si, entonces no es un i < M con q.i + 1 = q.(i+1) y por lo tanto una sublista r_(q.i)+r_(q.(i+1)) = r_(q.i)+r_(q.i + 1) de [1,2,...,N], pero r_(q.i)+r_(q.i + 1) también es una sublista de p lo que contradice que r_(q.i) y r_(q.i + 1) se ejecuta.

Ahora, para encontrar un q dado un p, asumimos que la disponibilidad de un mapeo de la estructura de datos con O(1) las inserciones y las búsquedas de números y listas con O(1) anexa y adelante recorrido.A continuación, hacemos la siguiente.

• Primero construimos la lista runheads = [r_1.1,r_2.1,...,r_M.1].Esto se puede hacer trivialmente por la que atraviesan p mientras que el mantenimiento de la ejecución actual.Durante este paso, nos recuerda también el número máximo encontrado para obtener N al final y la construcción de una asignación heads con los elementos de runheads como claves.Este paso es claramente O(n).Tenga en cuenta que no es relevante lo que los valores de heads son, por lo que podemos utilizar ejecutar r_i como valor para la clave r_i.1.

• Siguiente repetimos de 1 (e incluyendo) N el mantenimiento de un valor k con valor inicial 1.Para cada valor i verificamos para ver si i es en heads.Si este es el caso que nos agregue i -> k para una asignación de f y aumentar k.Este paso es también claramente O(n).Para ser capaz de volver de q a p también se puede almacenar una asignación adicional rev con k -> i o incluso k -> runheads(i) en ningún extra grande-O costo.

• Finalmente aplicamos la asignación de f a los elementos de runheads para obtener q.De nuevo O(n).

Para ilustrar con un ejemplo nos fijamos en el caso de que p = [1,3,4,2,5,6].

• En el primer paso tenemos runheads = [1,3,2,5], N=6 y heads = { 1 -> [1], 3 -> [3,4], 2 -> [2], 5 -> [5,6] }.

• Para el segundo de los pasos que hemos cuatro casos para los que tenemos que hacer algo: 1, 2, 3 y 5.Para estos casos tenemos los valores para k que son 1, 2, 3 y 4, respectivamente.Esto significa que f será { 1 -> 1, 2 -> 2, 3 -> 3, 5 -> 4 }.(Y rev sería { 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 5 } o { 1 -> [1], 2 -> [2], 3 -> [3,4], 4 -> [5,6] }, dependiendo de lo que se eligió a la tienda.)

• Para obtener q calculamos map(f,runheads) que es [f(1),f(3),f(2),f(5)] o, de manera equivalente, [1,3,2,4].

Así que, si no me equivoco y si las estructuras de datos que satisfacen los requisitos mencionados, esta solución debe ser O(n).Tenga en cuenta que, en la práctica, en realidad, puede ser más útil el uso de sus propios (O(n*log(n))) solución.Si usted tiene un gran p pero con sólo un par de carreras, de ordenación runheads y el uso que para construir las asignaciones podría ser más eficiente.Yo creo que p tendría que ser bastante grande para que este sea el caso.

Answer 2

Editado para clarificación

paso 1: ejecute el algoritmo, pero en lugar de producir solo una tabla hash, produzca una tabla hash (D1) indexada por el jefe del conjunto al que está asignando (por ejemplo, para [3,4] eso será 3) y una Lista (L1) con el conjunto en sí

[3; 4; 6; 8; 1; 2]:

   D1              L1

3 -> [3,4]     1 -> [3,4]

6 -> [6]       2 -> [6]

8 -> [8]       3 -> [8]

1 -> [1,2]     4 -> [1,2]

Paso 2: si miras las colecciones que tenemos ahora, verás que, para un conjunto dado, tenemos el índice en el que lo encontramos (en L1) y el valor de Head. El valor de mapa correcto será el número entero mínimo entre ellos que aún no se ha tomado. Por ejemplo, para [3,4] tendremos que el valor debe estar entre 1 y 3 y, dado que 1 ya está tomado, el valor correspondiente es 2. Tenga en cuenta que, dado que D1 está indexado por el Head valor, siempre se tomarán valores más bajos si existe el conjunto correspondiente. En el ejemplo, [1,2] se asigna a 1, de modo que esta clave ya está & Quot; tomada & Quot ;. Entonces, en pseudocódigo:

for (int Current = 1; Current  < L1.Length; Current++)
{
  GetHead(L1[Current]);
  Index = Current;
  While Head > Index
  {
    if D1.Empty(Index)
    {
      D1.Add(Index,D2[Current])
      D1.DeleteIfNotEmpty(Head);
    }
    else
      Index++;
  }
}

Por ejemplo

• tomamos el primer valor en L1 - > [3,4] ...
• get the Head = 3
• Comenzando en 1, buscamos D1 [1] que ya está en uso, por lo que incrementamos a 2.
• Buscamos D1 [2] que está vacío, por lo que asignamos D1 [2] = [3,4] y eliminamos D [3]

Eso no proporciona O (n) sino algo como O (n + log (n)) (n para el primer paso, log (n) para el segundo)

Para el ejemplo anterior que te lleva:

1 -> [1,2]
2 -> [3,4]
3 -> [6]
4 -> [8]

Ahora, si tiene [3; 4; 8; 6; 1; 2], eso dará como resultado

1 -> [1,2]
2 -> [3,4]
3 -> [8]
4 -> [6]

porque está usando el orden absoluto en la matriz original, no sé si eso está bien o querrás que 6 esté en el índice 3 y 8 en el índice 4, en ese caso probablemente tengas para preordenar L1 en función del encabezado que incrementará su complejidad por Log (n)

Si tiene que preordenar, tendrá 0 (n + log ^ 2 (n)) que no es tan malo (tal vez menos suponiendo que un QuickSort tenga O (Log n) ordenando L1 será O (log (log n))