Este es un desafío de pocas operaciones donde el objetivo es ordenar un vector en orden ascendente usando la menor cantidad de reversiones. Su algoritmo solo puede ordenar el vector usando "reversiones de sub-vectores" 1 , pero puede usar otras operaciones para operaciones aritméticas, bucles, verificar si está ordenado, etc. El número de reversiones de sub-vectores que realiza su algoritmo es su puntaje.
1 A "inversión de sub-vector":
- Seleccione un rango de números en el vector e invierta los elementos en ese rango.
Para dar un ejemplo simple, si comienza con el vector {4,3,2,1}
, puede ordenarlo de muchas maneras diferentes:
- Invierte todo el vector. Obviamente, este es el enfoque más corto, ya que solo requiere una inversión:
{4,3,2,1} -> {1,2,3,4}
- Puede hacer una versión del tipo burbuja, que requiere 6 reversiones:
{4,3,2,1} -> {3,4,2,1} -> {3,2,4,1} -> {2,3,4,1} -> {2,3,1,4} -> {2,1,3,4} -> {1,2,3,4}
- Puede comenzar con los primeros 3 elementos, luego los tres últimos, y finalmente los dos primeros y los dos últimos, lo que requiere 4 intercambios:
{4,3,2,1} -> {2,3,4,1} -> {2,1,4,3} -> {1,2,4,3} -> {1,2,3,4}
- ... y así. Hay una cantidad infinita de opciones disponibles (puede repetir cualquier operación si lo desea).
Reglas y requisitos:
Su código debe finalizar en menos de un minuto para obtener una lista con 100 números. Puedes cronometrar esto tú mismo, pero juega limpio 2 .
Debe almacenar los índices de inicio y finalización de todos los intercambios que realice, para que la solución pueda verificarse. (Explicaré lo que esto significa a continuación).
El código debe ser determinista.
Puede tomar la entrada en cualquier formato que desee: vector numérico, lista enlazada, matriz con longitud ... lo que quiera.
Puedes hacer lo que quieras en una copia del vector. Eso incluye intentar diferentes reversiones y verificar cuál es más eficiente. La fuerza bruta está perfectamente bien, pero cumpla con el límite de tiempo.
La puntuación es el número total de vueltas para los 5 vectores de prueba. El desempate será el sello de fecha.
Ejemplo:
4 1 23 21 49 2 7 9 2 | Vector / lista inicial 4 1 2 9 7 2 49 21 23 | (2, 8) (volteó los elementos entre los índices 2 y 8) 4 1 2 2 7 9 49 21 23 | (3, 5) 4 1 2 2 7 9 23 21 49 | (6, 8) 4 1 2 2 7 9 21 23 49 | (6, 7) 2 2 1 4 7 9 21 23 49 | (0, 3) 1 2 2 4 7 9 21 23 49 | (0, 2)
El puntaje sería 6, ya que realizó 6 reversiones. Debe almacenar (no imprimir) los índices enumerados en el lado derecho en un formato adecuado que pueda imprimirse / imprimirse fácilmente con fines de verificación.
Vectores de prueba:
133, 319, 80, 70, 194, 333, 65, 21, 345, 142, 82, 491, 92, 167, 281, 386, 48, 101, 394, 130, 111, 139, 214, 337, 180, 24, 443, 35, 376, 13, 166, 59, 452, 429, 406, 256, 133, 435, 446, 304, 350, 364, 447, 471, 236, 177, 317, 342, 294, 146, 280, 32, 135, 399, 78, 251, 467, 305, 366, 309, 162, 473, 27, 67, 305, 497, 112, 399, 103, 178, 386, 343, 33, 134, 480, 147, 466, 244, 370, 140, 227, 292, 28, 357, 156, 367, 157, 60, 214, 280, 153, 445, 301, 108, 77, 404, 496, 3, 226, 37
468, 494, 294, 42, 19, 23, 201, 47, 165, 118, 414, 371, 163, 430, 295, 333, 147, 336, 403, 490, 370, 128, 261, 91, 173, 339, 40, 54, 331, 236, 255, 33, 237, 272, 193, 91, 232, 452, 79, 435, 160, 328, 47, 179, 162, 239, 315, 73, 160, 266, 83, 451, 317, 255, 491, 70, 18, 275, 339, 298, 117, 145, 17, 178, 232, 59, 109, 271, 301, 437, 63, 103, 130, 15, 265, 281, 365, 444, 180, 257, 99, 248, 378, 158, 210, 466, 404, 263, 29, 117, 417, 357, 44, 495, 303, 428, 146, 215, 164, 99
132, 167, 361, 145, 36, 56, 343, 330, 14, 412, 345, 263, 306, 462, 101, 453, 364, 389, 432, 32, 200, 76, 268, 291, 35, 13, 448, 188, 11, 235, 184, 439, 175, 159, 360, 46, 193, 440, 334, 128, 346, 192, 263, 466, 175, 407, 340, 393, 231, 472, 122, 254, 451, 485, 257, 67, 200, 135, 132, 421, 205, 398, 251, 286, 292, 488, 480, 56, 284, 484, 157, 264, 459, 6, 289, 311, 116, 138, 92, 21, 307, 172, 352, 199, 55, 38, 427, 214, 233, 404, 330, 105, 223, 495, 334, 169, 168, 444, 268, 248
367, 334, 296, 59, 18, 193, 118, 10, 276, 180, 242, 115, 233, 40, 225, 244, 147, 439, 297, 115, 354, 248, 89, 423, 47, 458, 64, 33, 463, 142, 5, 13, 89, 282, 186, 12, 70, 289, 385, 289, 274, 136, 39, 424, 174, 186, 489, 73, 296, 39, 445, 308, 451, 384, 451, 446, 282, 419, 479, 220, 35, 419, 161, 14, 42, 321, 202, 30, 32, 162, 444, 215, 218, 102, 140, 473, 500, 480, 402, 1, 1, 79, 50, 54, 111, 189, 147, 352, 61, 460, 196, 77, 315, 304, 385, 275, 65, 145, 434, 39
311, 202, 126, 494, 321, 330, 290, 28, 400, 84, 6, 160, 432, 308, 469, 459, 80, 48, 292, 229, 191, 240, 491, 231, 286, 413, 170, 486, 59, 54, 36, 334, 135, 39, 393, 201, 127, 95, 456, 497, 429, 139, 81, 293, 359, 477, 404, 129, 129, 297, 298, 495, 424, 446, 57, 296, 10, 269, 350, 337, 39, 386, 142, 327, 22, 352, 421, 32, 171, 452, 2, 484, 337, 359, 444, 246, 174, 23, 115, 102, 427, 439, 71, 478, 89, 225, 7, 118, 453, 350, 109, 277, 338, 474, 405, 380, 256, 228, 277, 3
Estoy bastante seguro de que encontrar una solución óptima es NP-hard (ya que la clasificación de panqueques es regular).
2 Sí, las personas con computadoras muy rápidas pueden tener un beneficio, debido al límite de tiempo de un minuto. Después de mucha discusión, pensé que es mejor si todos hacen su propio benchmarking, no es un desafío de código más rápido.
fuente
n-1
flips? Solo puedo probar un límite inferior de aproximadamente 50.Respuestas:
Java, algoritmo genético-ish, 80 + 81 + 79 + 78 + 80 = 398 (anteriormente
418)Después de probar un montón de ideas diferentes y fallar en su mayoría, me decidí por este algoritmo: comience con la matriz de entrada, intente todas las reversiones posibles y mantenga un cierto número de resultados con el menor número de ejecuciones, luego haga lo mismo para esos resultados, hasta obtenemos una matriz ordenada.
Por "ejecuciones" me refiero a las submatrices máximas que aparecen exactamente o invertidas en la matriz ordenada. Básicamente son subarreglos ordenados máximos, pero en el caso de elementos repetidos, el número de elementos en el medio debe coincidir. Por ejemplo, si la matriz ordenada es
2, 2, 3, 3, 4, 4
entonces4, 3, 3, 2
una ejecución pero2, 2, 3, 4
no lo es (y tampoco lo es2, 3, 2
).En esta versión, optimicé el algoritmo para invertir solo en los límites de la ejecución y solo si una ejecución inversa se puede unir con una nueva ejecución adyacente. Además, las ejecuciones se ajustan y unen en cada paso, para evitar volver a calcularlas desde la matriz modificada. Esto me permitió aumentar el "tamaño de la población" de 30 a aproximadamente 3000, y ejecutar simulaciones múltiples en varios tamaños.
La entrada es una lista de números separados por comas y / o espacios (desde stdin). Si la entrada está vacía, el programa ejecuta las 5 pruebas. Cada uno lleva unos 40 segundos aquí.
fuente
Un movimiento de fuerza bruta luego selección de selección (también solución ingenua), 90 + 89 + 88 + 87 + 89 = 443 movimientos
para cada primer movimiento posible, pruébalo y luego haz una selección.
Sí, esta es otra solución ingenua.
No estoy seguro de si esto debería ser una edición u otra publicación, pero parece que la solución es demasiado simple, por lo que se elige la edición.
Selección de selección (solución ingenua), 92 + 93 + 95 + 93 + 96 = 469 movimientos
Una solución ingenua utiliza el tipo de selección.
No DEBE ser algunas soluciones mejores, pero este post ya que no he encontrado uno mejor (sin búsqueda de fuerza bruta).
(El código anterior es JavaScript Shell )
fuente