Considere una lista aleatoria de los enteros 1 a N. Desea ordenarla usando solo las siguientes acciones:
- Intercambie el primer y el último elemento de la lista. (S)
- Destaque el primer elemento y añádalo al final de la lista. (PAGS)
Esto siempre es posible porque cualquier lista se puede ordenar con suficientes intercambios de elementos adyacentes. Usando S y P puede intercambiar cualquier elemento adyacente llamando a P hasta que los dos elementos en cuestión sean el primero y el último elemento de la lista, luego llamando a S para intercambiarlos, luego llamando a P nuevamente hasta que estén en los índices originales (ahora intercambiados )
Sin embargo, en términos del número de operaciones S y P, es poco probable que este método sea óptimo para la mayoría de las listas.
Reto
Escriba un programa o función que tome una permutación de los números del 1 al N (N> 1). Se puede dar como una lista o cadena o lo que sea conveniente. Debería generar una secuencia de S y P que ordenaría la permutación cuando se aplica de izquierda a derecha. Esta secuencia no tiene que ser óptimamente corta, pero más corta es la mejor (ver Puntuación).
Ejemplo
Si la entrada fue [2, 1, 3]
la salida podría ser SP
porque
- S aplicado a lo
[2, 1, 3]
hace[3, 1, 2]
, - y P aplicado a lo
[3, 1, 2]
hace[1, 2, 3]
, que se ordena.
Verificador
Este fragmento de pila se puede usar para verificar que una secuencia realmente ordena la lista. La lista debe tener corchetes y estar separada por comas. La secuencia SP es solo una cadena de S
'sy P
' s.
<style>*{font-family:monospace}</style><script>function swap(list) {var tmp = list[0];list[0] = list[list.length - 1];list[list.length - 1] = tmp;}function pop(list) {list.push(list.shift())}function check() {var result = 'Sorted sucessfully.';var details = '';try {var list = eval(document.getElementById('list').value);var seq = document.getElementById('seq').value;details += 'Sequence: ' + seq + '<br>Steps:<br>' + list + ' <-- original';for(var i = 0; i < seq.length; i++) {if (seq.charAt(i) == 'S')swap(list);else if (seq.charAt(i) == 'P')pop(list);details += ' (' + i + ')<br>' + list;}details += ' <-- final (' + i + ')';for(var i = 1; i < list.length; i++) {if (list[i-1] > list[i]) {result = 'Sorting failed!';break;}}} catch(e) {result = 'Error: ' + e;}document.getElementById('result').innerHTML = result;document.getElementById('details').innerHTML = details;}</script><p>List<br><input id='list'type='text'size='60'value='[2, 1, 3]'></p><p>SP Sequence<br><textarea id='seq'rows='1'cols='60'>SP</textarea><br></p><button type='button'onclick='check()'>Check</button><p id='result'></p><p id='details'></p>
Tanteo
Su algoritmo debe producir secuencias SP correctas, pero posiblemente subóptimas, para N = 2 a 256. Para cualquier permutación en este rango, debe ejecutarse en menos de 5 minutos en una computadora moderna decente .
Su puntaje es el número total de operaciones S y P que su algoritmo necesita para ordenar las 30 listas proporcionadas a continuación. El puntaje más bajo gana.
No puede codificar su programa para que se ajuste a estos datos. Si parece necesario, puedo agregar más datos de prueba para determinar el ganador.
1. Length 3
[2, 1, 3]
2. Length 7
[2, 7, 5, 3, 4, 6, 1]
3. Length 41
[7, 12, 17, 2, 14, 15, 33, 20, 37, 18, 9, 25, 41, 26, 39, 29, 16, 5, 23, 24, 35, 38, 32, 6, 11, 21, 27, 8, 40, 3, 10, 36, 13, 30, 31, 28, 1, 4, 19, 22, 34]
4. Length 52
[19, 49, 34, 26, 38, 3, 14, 37, 21, 39, 46, 29, 18, 6, 15, 25, 28, 47, 22, 41, 32, 51, 50, 5, 45, 4, 30, 44, 10, 43, 20, 17, 13, 36, 48, 27, 35, 24, 8, 12, 40, 2, 1, 16, 7, 31, 23, 33, 42, 52, 9, 11]
5. Length 65
[12, 53, 4, 5, 17, 32, 58, 54, 18, 43, 21, 26, 51, 45, 9, 2, 35, 28, 40, 61, 57, 27, 62, 39, 24, 59, 36, 25, 20, 33, 63, 56, 64, 47, 38, 7, 13, 34, 16, 30, 49, 22, 37, 3, 48, 11, 52, 1, 29, 42, 50, 23, 6, 8, 60, 65, 46, 10, 41, 31, 44, 15, 14, 19, 55]
6. Length 69
[58, 15, 63, 18, 24, 59, 26, 37, 44, 67, 14, 52, 2, 31, 68, 54, 32, 17, 55, 50, 42, 56, 65, 29, 13, 41, 7, 45, 53, 35, 21, 39, 61, 23, 49, 12, 60, 46, 27, 57, 28, 40, 10, 69, 1, 6, 19, 62, 8, 30, 64, 34, 3, 43, 38, 20, 25, 33, 66, 47, 4, 36, 16, 11, 5, 22, 51, 48, 9]
7. Length 75
[14, 69, 1, 43, 32, 42, 59, 37, 70, 63, 57, 60, 56, 73, 67, 6, 11, 36, 31, 22, 40, 7, 21, 35, 50, 64, 28, 41, 18, 17, 75, 54, 51, 19, 68, 33, 45, 61, 66, 52, 49, 65, 4, 72, 23, 34, 9, 15, 38, 16, 3, 71, 29, 30, 48, 53, 10, 8, 13, 47, 20, 55, 74, 27, 25, 62, 46, 24, 44, 39, 2, 26, 58, 12, 5]
8. Length 80
[3, 65, 44, 14, 19, 6, 11, 29, 79, 35, 42, 16, 68, 7, 62, 30, 38, 46, 15, 9, 75, 5, 52, 32, 22, 70, 64, 13, 21, 47, 10, 4, 55, 40, 45, 56, 77, 27, 23, 72, 17, 71, 53, 20, 18, 25, 73, 59, 36, 34, 37, 57, 1, 69, 24, 58, 33, 76, 2, 12, 49, 61, 78, 67, 66, 63, 50, 80, 28, 48, 26, 51, 41, 60, 31, 54, 39, 8, 74, 43]
9. Length 103
[40, 62, 53, 6, 32, 85, 8, 83, 33, 29, 87, 93, 22, 37, 80, 12, 74, 69, 64, 9, 18, 98, 17, 45, 60, 38, 10, 103, 19, 5, 54, 15, 90, 100, 79, 91, 46, 82, 43, 31, 51, 96, 30, 70, 76, 16, 55, 77, 11, 65, 58, 75, 61, 3, 28, 24, 101, 20, 41, 72, 86, 56, 35, 50, 78, 27, 67, 95, 44, 68, 48, 26, 39, 97, 21, 49, 102, 73, 63, 7, 71, 52, 1, 88, 34, 42, 14, 47, 36, 99, 4, 13, 94, 89, 59, 92, 57, 25, 23, 66, 81, 2, 84]
10. Length 108
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108]
11. Length 109
[48, 89, 25, 64, 8, 69, 81, 98, 107, 61, 106, 63, 59, 50, 83, 24, 86, 68, 100, 104, 56, 88, 46, 62, 94, 4, 47, 33, 19, 1, 77, 102, 9, 30, 44, 26, 16, 80, 67, 75, 70, 96, 108, 45, 79, 51, 12, 38, 73, 37, 65, 31, 60, 22, 28, 3, 43, 71, 105, 91, 93, 101, 13, 97, 29, 72, 82, 87, 27, 5, 17, 10, 34, 84, 53, 15, 78, 41, 85, 6, 14, 57, 76, 7, 23, 99, 32, 95, 49, 2, 21, 109, 74, 39, 11, 103, 18, 90, 35, 40, 58, 20, 55, 52, 36, 54, 42, 92, 66]
12. Length 151
[61, 7, 8, 79, 78, 4, 48, 13, 14, 117, 12, 96, 130, 118, 63, 110, 72, 57, 86, 126, 62, 10, 29, 102, 99, 28, 56, 135, 11, 151, 141, 97, 45, 109, 38, 150, 40, 149, 52, 140, 106, 80, 66, 134, 125, 137, 31, 85, 68, 94, 36, 26, 95, 92, 49, 25, 120, 148, 33, 73, 41, 100, 58, 127, 60, 122, 133, 9, 19, 81, 59, 55, 103, 146, 42, 21, 128, 75, 101, 82, 50, 142, 131, 76, 20, 69, 139, 83, 16, 64, 17, 124, 90, 138, 37, 1, 34, 43, 129, 77, 23, 35, 144, 121, 113, 115, 114, 67, 98, 70, 145, 104, 71, 5, 119, 6, 18, 88, 116, 111, 132, 39, 89, 24, 15, 107, 27, 65, 30, 47, 143, 93, 53, 108, 2, 74, 123, 44, 51, 54, 87, 147, 84, 3, 112, 46, 32, 91, 136, 22, 105]
13. Length 173
[93, 14, 141, 125, 64, 30, 24, 85, 44, 68, 91, 22, 103, 155, 117, 114, 123, 51, 131, 72, 67, 61, 5, 41, 10, 20, 129, 86, 154, 108, 161, 2, 82, 153, 96, 50, 136, 121, 128, 126, 120, 111, 89, 113, 104, 84, 18, 109, 42, 83, 162, 124, 173, 116, 12, 54, 52, 39, 122, 49, 46, 1, 130, 71, 152, 73, 56, 34, 149, 75, 133, 8, 74, 45, 88, 23, 7, 60, 115, 134, 53, 119, 106, 81, 112, 31, 35, 172, 159, 38, 59, 69, 142, 146, 110, 170, 160, 166, 43, 58, 4, 107, 78, 156, 47, 33, 145, 63, 163, 27, 70, 77, 36, 16, 100, 26, 19, 151, 57, 32, 15, 13, 40, 169, 98, 132, 135, 62, 66, 90, 102, 171, 99, 148, 80, 144, 147, 168, 94, 143, 17, 3, 140, 97, 11, 65, 55, 92, 95, 127, 167, 150, 87, 118, 28, 137, 9, 29, 105, 157, 25, 165, 158, 21, 164, 101, 79, 76, 6, 138, 48, 37, 139]
14. Length 177
[68, 117, 61, 159, 110, 148, 3, 20, 169, 145, 136, 1, 120, 109, 21, 58, 52, 97, 65, 168, 34, 134, 111, 176, 13, 156, 172, 53, 55, 124, 177, 88, 92, 23, 72, 26, 104, 121, 133, 73, 39, 140, 25, 71, 119, 158, 146, 128, 18, 94, 113, 45, 60, 96, 30, 5, 116, 153, 90, 115, 67, 80, 112, 154, 9, 17, 10, 33, 81, 38, 95, 118, 35, 160, 151, 150, 76, 77, 14, 147, 173, 135, 162, 114, 27, 100, 167, 74, 69, 165, 108, 79, 91, 48, 105, 125, 129, 75, 93, 11, 12, 64, 24, 170, 142, 98, 44, 37, 43, 78, 16, 28, 166, 155, 138, 164, 122, 163, 107, 130, 86, 56, 2, 161, 63, 126, 131, 144, 82, 106, 103, 32, 132, 54, 41, 171, 70, 85, 19, 143, 137, 87, 84, 66, 99, 102, 15, 49, 123, 175, 89, 51, 141, 62, 50, 36, 152, 47, 42, 8, 7, 46, 29, 22, 149, 139, 4, 40, 83, 6, 59, 57, 174, 31, 127, 101, 157]
15. Length 192
[82, 130, 189, 21, 169, 147, 160, 66, 133, 153, 143, 116, 49, 13, 63, 61, 94, 164, 35, 112, 141, 62, 87, 171, 19, 3, 93, 83, 149, 64, 34, 170, 129, 182, 101, 77, 14, 91, 145, 23, 32, 92, 187, 54, 184, 120, 109, 159, 27, 44, 60, 103, 134, 52, 122, 33, 78, 88, 108, 45, 15, 79, 137, 80, 161, 69, 6, 139, 110, 67, 43, 190, 152, 59, 173, 125, 168, 37, 151, 132, 1, 178, 20, 114, 119, 144, 25, 146, 42, 136, 162, 123, 31, 107, 131, 127, 51, 105, 2, 65, 28, 102, 76, 24, 135, 174, 9, 111, 98, 39, 74, 142, 70, 121, 154, 38, 113, 75, 40, 86, 100, 106, 181, 117, 95, 85, 138, 41, 167, 172, 4, 186, 17, 16, 104, 71, 81, 73, 57, 8, 140, 118, 158, 12, 148, 53, 29, 185, 18, 150, 22, 188, 72, 128, 84, 96, 47, 192, 126, 56, 163, 50, 157, 165, 97, 166, 180, 7, 46, 30, 191, 124, 5, 48, 175, 68, 36, 89, 177, 11, 176, 183, 99, 90, 55, 26, 10, 58, 115, 155, 179, 156]
16. Length 201
[23, 8, 58, 24, 19, 87, 98, 187, 17, 130, 116, 141, 129, 166, 29, 191, 81, 105, 137, 171, 39, 67, 46, 150, 102, 26, 163, 183, 170, 72, 160, 43, 9, 197, 189, 173, 196, 68, 100, 16, 93, 175, 74, 28, 133, 122, 27, 79, 107, 162, 62, 192, 108, 104, 97, 12, 60, 155, 161, 82, 167, 158, 149, 30, 124, 22, 168, 115, 134, 94, 34, 184, 127, 121, 177, 112, 142, 95, 164, 41, 59, 55, 143, 85, 176, 3, 156, 148, 153, 42, 180, 145, 78, 147, 119, 109, 139, 178, 61, 181, 136, 157, 91, 84, 47, 71, 70, 118, 18, 63, 80, 56, 123, 194, 117, 195, 152, 66, 48, 11, 99, 201, 128, 151, 138, 64, 21, 131, 159, 103, 75, 49, 169, 113, 53, 114, 69, 54, 165, 38, 101, 76, 200, 199, 140, 125, 193, 88, 32, 51, 126, 14, 13, 77, 52, 50, 198, 172, 5, 92, 96, 15, 106, 182, 31, 83, 120, 57, 135, 65, 7, 154, 20, 25, 45, 1, 6, 73, 40, 174, 132, 10, 111, 186, 190, 4, 36, 188, 185, 146, 44, 110, 179, 2, 90, 86, 35, 37, 33, 89, 144]
17. Length 201
[97, 146, 168, 5, 56, 147, 189, 92, 154, 13, 185, 109, 45, 126, 17, 10, 53, 98, 88, 41, 163, 99, 157, 35, 125, 34, 173, 171, 138, 104, 149, 172, 60, 183, 36, 65, 32, 180, 87, 167, 59, 84, 188, 11, 69, 57, 174, 61, 66, 7, 8, 111, 91, 58, 128, 94, 141, 139, 31, 78, 156, 70, 16, 162, 26, 33, 106, 175, 103, 21, 164, 110, 159, 80, 200, 82, 123, 144, 44, 148, 4, 55, 179, 184, 186, 124, 63, 107, 54, 112, 137, 165, 121, 25, 132, 196, 90, 89, 71, 160, 95, 117, 197, 37, 108, 39, 115, 12, 52, 119, 120, 79, 29, 49, 93, 22, 122, 161, 76, 38, 72, 169, 85, 178, 77, 105, 190, 100, 9, 86, 177, 194, 2, 136, 114, 51, 68, 19, 47, 195, 113, 193, 67, 96, 182, 170, 50, 83, 143, 166, 3, 192, 24, 127, 140, 176, 134, 158, 116, 199, 1, 135, 118, 145, 14, 15, 155, 48, 42, 73, 46, 102, 191, 28, 201, 181, 75, 133, 153, 6, 131, 130, 81, 20, 198, 64, 142, 150, 27, 101, 18, 30, 40, 23, 129, 43, 62, 187, 152, 151, 74]
18. Length 205
[161, 197, 177, 118, 94, 112, 13, 190, 200, 166, 127, 80, 115, 204, 186, 60, 50, 97, 175, 32, 26, 65, 16, 4, 55, 120, 143, 187, 121, 29, 18, 82, 17, 21, 144, 20, 88, 195, 99, 67, 203, 23, 176, 126, 137, 77, 70, 30, 103, 182, 113, 119, 36, 47, 90, 98, 54, 3, 49, 105, 57, 135, 153, 142, 174, 155, 158, 11, 157, 22, 171, 110, 28, 196, 129, 163, 79, 63, 38, 145, 140, 2, 128, 180, 106, 59, 25, 184, 81, 164, 95, 39, 68, 78, 178, 156, 72, 51, 202, 66, 48, 101, 71, 108, 130, 5, 107, 147, 199, 12, 27, 150, 167, 91, 64, 170, 191, 151, 149, 168, 34, 125, 188, 181, 139, 58, 75, 189, 124, 152, 183, 7, 111, 89, 84, 52, 141, 83, 69, 62, 73, 43, 123, 14, 179, 162, 114, 138, 117, 159, 74, 85, 10, 96, 86, 31, 132, 1, 104, 109, 45, 165, 148, 172, 154, 92, 173, 40, 19, 56, 37, 205, 44, 193, 122, 185, 93, 133, 53, 9, 169, 6, 61, 136, 46, 76, 33, 15, 116, 198, 160, 194, 131, 41, 42, 35, 146, 134, 192, 8, 87, 201, 100, 24, 102]
19. Length 211
[200, 36, 204, 198, 190, 161, 57, 108, 180, 203, 135, 48, 134, 47, 158, 10, 41, 11, 23, 127, 167, 121, 109, 211, 201, 1, 42, 40, 86, 104, 147, 139, 145, 101, 144, 166, 176, 92, 118, 54, 182, 30, 58, 123, 124, 67, 125, 154, 187, 168, 103, 17, 72, 98, 12, 184, 59, 87, 174, 93, 45, 116, 73, 69, 74, 80, 56, 14, 34, 85, 38, 185, 165, 110, 164, 151, 43, 192, 62, 4, 140, 170, 197, 111, 173, 141, 65, 77, 70, 136, 206, 83, 100, 148, 25, 183, 209, 189, 150, 33, 46, 16, 64, 114, 71, 102, 91, 39, 177, 196, 169, 128, 129, 44, 75, 188, 146, 26, 84, 138, 162, 194, 105, 37, 35, 88, 156, 130, 193, 19, 179, 82, 106, 181, 153, 28, 53, 21, 195, 66, 159, 115, 113, 112, 191, 172, 63, 143, 178, 94, 160, 186, 31, 29, 90, 68, 205, 155, 119, 117, 157, 107, 60, 79, 171, 149, 6, 24, 27, 50, 51, 126, 15, 133, 2, 131, 7, 49, 207, 163, 18, 120, 199, 61, 52, 32, 208, 20, 210, 13, 78, 55, 137, 202, 152, 8, 81, 76, 9, 97, 22, 99, 132, 95, 122, 89, 175, 5, 3, 96, 142]
20. Length 226
[204, 79, 88, 98, 197, 32, 40, 117, 153, 167, 29, 74, 170, 115, 127, 210, 22, 109, 65, 47, 41, 132, 110, 158, 192, 99, 96, 224, 190, 143, 33, 225, 195, 19, 70, 73, 54, 161, 75, 179, 181, 207, 26, 221, 66, 130, 152, 131, 30, 35, 155, 69, 68, 38, 129, 95, 116, 214, 7, 186, 62, 27, 212, 125, 216, 86, 148, 164, 141, 4, 140, 222, 16, 46, 12, 215, 78, 219, 211, 134, 118, 171, 121, 52, 123, 56, 220, 15, 25, 100, 137, 163, 51, 91, 10, 83, 55, 187, 182, 201, 149, 160, 8, 14, 218, 77, 3, 184, 114, 43, 122, 135, 142, 104, 120, 198, 45, 108, 85, 189, 151, 175, 136, 165, 226, 97, 124, 200, 60, 172, 20, 67, 1, 174, 87, 102, 119, 188, 223, 199, 103, 89, 49, 213, 57, 9, 101, 112, 36, 176, 194, 92, 145, 180, 168, 111, 94, 178, 39, 166, 193, 17, 2, 154, 58, 156, 217, 13, 80, 202, 206, 169, 107, 177, 144, 205, 139, 93, 34, 64, 106, 150, 146, 126, 185, 208, 63, 203, 105, 18, 191, 53, 183, 209, 6, 23, 84, 5, 61, 59, 162, 128, 37, 50, 28, 159, 173, 196, 24, 31, 72, 138, 82, 48, 133, 147, 42, 113, 81, 90, 71, 21, 11, 157, 76, 44]
21. Length 227
[197, 52, 91, 42, 29, 113, 82, 68, 147, 225, 80, 167, 117, 142, 140, 216, 65, 195, 97, 61, 133, 209, 214, 58, 152, 71, 56, 182, 201, 163, 227, 186, 63, 171, 207, 102, 161, 136, 224, 146, 92, 175, 45, 217, 6, 99, 20, 119, 210, 93, 77, 211, 21, 70, 90, 96, 115, 100, 183, 173, 69, 98, 172, 75, 111, 203, 19, 129, 35, 155, 74, 37, 23, 51, 192, 212, 33, 64, 59, 194, 112, 135, 1, 184, 5, 166, 185, 84, 199, 138, 144, 86, 128, 26, 190, 73, 179, 27, 118, 223, 46, 95, 159, 153, 226, 25, 180, 132, 189, 60, 32, 208, 123, 89, 87, 22, 181, 143, 47, 18, 198, 219, 156, 148, 193, 122, 110, 28, 106, 39, 30, 103, 4, 176, 114, 3, 131, 107, 204, 218, 141, 169, 16, 206, 36, 188, 174, 54, 94, 50, 205, 104, 170, 160, 72, 165, 78, 24, 222, 8, 108, 81, 76, 15, 13, 126, 79, 7, 105, 125, 162, 83, 41, 145, 139, 66, 127, 38, 12, 187, 130, 221, 48, 164, 191, 157, 88, 168, 196, 10, 9, 53, 124, 150, 31, 116, 49, 34, 200, 134, 220, 121, 2, 62, 149, 158, 101, 17, 202, 11, 109, 85, 55, 67, 120, 43, 154, 44, 215, 177, 178, 40, 57, 14, 213, 151, 137]
22. Length 230
[69, 204, 215, 61, 97, 149, 9, 11, 137, 71, 37, 219, 92, 115, 156, 159, 200, 222, 3, 89, 172, 177, 203, 45, 54, 82, 147, 176, 168, 6, 26, 81, 25, 132, 212, 70, 228, 122, 225, 141, 100, 12, 124, 30, 146, 73, 19, 49, 52, 62, 217, 166, 191, 102, 163, 50, 181, 7, 134, 58, 76, 199, 179, 169, 197, 108, 174, 22, 186, 171, 114, 103, 173, 68, 65, 4, 13, 117, 64, 10, 126, 77, 206, 133, 121, 60, 40, 38, 59, 178, 224, 211, 187, 80, 220, 140, 8, 34, 130, 41, 95, 105, 227, 66, 210, 180, 192, 106, 209, 107, 157, 188, 170, 101, 131, 87, 14, 165, 78, 182, 136, 193, 190, 20, 67, 125, 36, 5, 145, 218, 99, 138, 154, 16, 29, 152, 194, 53, 148, 93, 202, 229, 198, 109, 43, 214, 150, 51, 128, 216, 1, 83, 196, 135, 74, 119, 75, 42, 142, 72, 226, 185, 116, 162, 63, 2, 112, 33, 184, 158, 15, 213, 144, 223, 98, 57, 160, 143, 90, 44, 205, 35, 21, 48, 151, 85, 123, 32, 47, 39, 189, 161, 56, 207, 84, 94, 230, 46, 164, 113, 175, 18, 195, 110, 127, 96, 129, 88, 17, 153, 104, 91, 86, 31, 118, 111, 120, 201, 28, 221, 23, 139, 24, 27, 167, 208, 183, 155, 79, 55]
23. Length 238
[202, 18, 122, 135, 11, 57, 103, 35, 86, 2, 84, 232, 208, 186, 54, 77, 145, 101, 105, 137, 210, 234, 207, 93, 55, 63, 230, 66, 160, 10, 223, 36, 34, 216, 104, 174, 121, 25, 166, 75, 167, 176, 61, 32, 118, 89, 68, 5, 14, 27, 204, 99, 149, 88, 91, 222, 37, 144, 108, 78, 128, 131, 190, 17, 65, 168, 225, 165, 41, 49, 38, 72, 43, 147, 158, 74, 130, 7, 82, 64, 97, 69, 100, 22, 152, 85, 48, 33, 218, 47, 228, 113, 40, 185, 219, 112, 180, 120, 4, 213, 179, 194, 51, 96, 221, 44, 238, 31, 117, 114, 229, 81, 164, 193, 236, 26, 59, 30, 151, 12, 115, 170, 24, 70, 227, 159, 133, 52, 134, 203, 15, 197, 155, 83, 50, 111, 195, 139, 109, 127, 188, 87, 62, 157, 226, 142, 98, 76, 211, 138, 58, 140, 198, 220, 16, 46, 183, 107, 106, 29, 163, 173, 209, 217, 215, 1, 177, 233, 199, 110, 172, 23, 212, 79, 94, 102, 39, 20, 178, 150, 175, 119, 8, 13, 42, 156, 201, 73, 200, 124, 53, 161, 92, 123, 224, 143, 196, 28, 9, 6, 80, 56, 148, 125, 214, 60, 171, 153, 231, 181, 205, 19, 95, 206, 154, 132, 169, 116, 3, 126, 187, 162, 191, 67, 136, 45, 192, 189, 235, 129, 21, 141, 237, 184, 90, 146, 182, 71]
24. Length 241
[2, 33, 49, 83, 207, 204, 13, 57, 115, 86, 102, 219, 232, 44, 177, 197, 171, 227, 191, 10, 25, 162, 62, 11, 76, 214, 163, 201, 130, 91, 233, 194, 112, 179, 66, 139, 183, 116, 196, 193, 150, 211, 30, 144, 209, 97, 174, 3, 68, 38, 120, 165, 56, 64, 87, 15, 79, 131, 206, 96, 188, 7, 99, 195, 129, 8, 186, 78, 212, 125, 161, 230, 225, 239, 47, 107, 53, 218, 164, 106, 198, 215, 181, 226, 6, 175, 167, 236, 67, 80, 210, 128, 155, 40, 63, 74, 113, 89, 18, 190, 124, 221, 59, 149, 103, 42, 156, 157, 200, 168, 34, 77, 65, 146, 5, 187, 222, 231, 140, 141, 172, 234, 100, 94, 132, 237, 24, 216, 152, 22, 51, 69, 35, 43, 105, 23, 61, 1, 72, 135, 104, 9, 12, 21, 46, 192, 159, 205, 158, 109, 28, 98, 50, 122, 111, 71, 166, 229, 37, 114, 173, 134, 136, 81, 121, 185, 118, 223, 20, 14, 108, 82, 178, 54, 26, 153, 36, 39, 117, 147, 95, 90, 16, 17, 170, 119, 199, 19, 84, 213, 88, 93, 151, 4, 101, 142, 110, 184, 55, 138, 75, 133, 148, 145, 45, 70, 217, 143, 224, 241, 31, 240, 182, 52, 238, 126, 85, 154, 137, 160, 27, 180, 60, 29, 32, 169, 235, 123, 176, 48, 220, 203, 228, 127, 41, 58, 73, 92, 189, 202, 208]
25. Length 241
[105, 160, 132, 32, 10, 117, 76, 2, 190, 108, 178, 51, 71, 237, 232, 47, 14, 124, 100, 31, 169, 196, 8, 184, 21, 151, 223, 86, 42, 127, 55, 58, 229, 4, 219, 46, 238, 179, 24, 194, 203, 122, 66, 15, 81, 146, 172, 106, 129, 135, 216, 120, 92, 231, 144, 195, 181, 162, 69, 45, 137, 136, 9, 30, 5, 188, 91, 49, 147, 233, 198, 17, 241, 163, 36, 18, 183, 59, 16, 29, 116, 182, 41, 48, 23, 39, 154, 210, 68, 167, 95, 213, 79, 225, 37, 157, 109, 143, 78, 142, 173, 155, 200, 110, 20, 73, 141, 168, 156, 126, 150, 201, 114, 1, 230, 211, 217, 131, 140, 204, 209, 149, 103, 199, 165, 175, 35, 107, 74, 63, 193, 239, 218, 234, 197, 224, 174, 121, 60, 88, 22, 171, 133, 207, 152, 34, 43, 228, 125, 115, 101, 7, 12, 220, 82, 153, 134, 52, 130, 70, 72, 44, 177, 89, 65, 98, 94, 53, 208, 227, 161, 3, 123, 236, 221, 87, 102, 50, 90, 180, 185, 186, 67, 77, 26, 212, 27, 222, 6, 145, 11, 13, 84, 25, 164, 64, 85, 139, 214, 189, 61, 96, 191, 128, 93, 138, 148, 19, 119, 202, 75, 176, 159, 56, 104, 206, 40, 187, 215, 62, 166, 240, 112, 226, 170, 83, 97, 57, 99, 38, 28, 113, 205, 158, 235, 111, 54, 192, 118, 80, 33]
26. Length 244
[89, 13, 154, 161, 235, 225, 92, 188, 215, 194, 54, 58, 128, 21, 165, 85, 144, 205, 142, 77, 109, 24, 83, 69, 72, 7, 224, 240, 191, 204, 183, 203, 68, 70, 63, 95, 206, 170, 153, 180, 45, 178, 35, 27, 190, 132, 222, 41, 40, 156, 97, 20, 217, 177, 167, 65, 23, 136, 216, 234, 38, 201, 236, 164, 82, 241, 10, 141, 148, 229, 5, 125, 113, 159, 193, 187, 130, 179, 52, 108, 86, 196, 174, 123, 56, 116, 227, 30, 239, 98, 186, 67, 135, 118, 163, 43, 32, 50, 231, 226, 232, 172, 200, 99, 6, 143, 39, 93, 107, 34, 129, 157, 100, 127, 15, 84, 81, 73, 121, 220, 44, 8, 57, 105, 91, 171, 162, 211, 244, 104, 112, 238, 212, 133, 71, 192, 145, 160, 87, 181, 60, 184, 119, 4, 55, 96, 53, 12, 213, 124, 94, 22, 42, 3, 48, 131, 117, 140, 138, 228, 219, 155, 59, 29, 202, 169, 114, 101, 47, 233, 176, 139, 207, 33, 79, 16, 51, 66, 75, 90, 198, 168, 166, 31, 151, 49, 208, 150, 111, 14, 25, 197, 17, 76, 80, 78, 9, 173, 26, 137, 19, 120, 199, 106, 152, 88, 147, 36, 158, 28, 243, 221, 110, 74, 175, 237, 61, 2, 62, 214, 189, 134, 195, 218, 18, 102, 46, 103, 11, 122, 146, 185, 182, 209, 1, 149, 115, 64, 37, 126, 230, 223, 242, 210]
27. Length 246
[28, 186, 214, 18, 220, 73, 20, 88, 234, 187, 27, 102, 22, 129, 10, 228, 196, 56, 47, 2, 16, 67, 124, 137, 177, 179, 223, 147, 188, 23, 103, 109, 149, 60, 229, 99, 222, 90, 49, 80, 158, 93, 171, 71, 175, 143, 19, 212, 40, 226, 219, 120, 146, 66, 167, 232, 94, 174, 237, 9, 173, 70, 122, 241, 58, 82, 191, 211, 180, 104, 53, 36, 83, 37, 131, 25, 162, 32, 210, 144, 145, 69, 135, 63, 154, 165, 46, 57, 50, 74, 128, 140, 112, 118, 125, 231, 221, 233, 95, 200, 153, 6, 166, 98, 208, 91, 89, 141, 4, 26, 134, 86, 8, 30, 157, 156, 224, 201, 243, 7, 161, 1, 84, 115, 44, 230, 78, 79, 5, 17, 194, 148, 152, 121, 193, 107, 240, 181, 29, 43, 65, 164, 45, 110, 64, 195, 216, 127, 59, 197, 178, 151, 139, 85, 75, 11, 204, 184, 77, 54, 51, 205, 108, 142, 130, 138, 238, 87, 38, 101, 96, 31, 215, 244, 242, 172, 213, 136, 97, 35, 39, 76, 42, 245, 123, 227, 24, 168, 33, 159, 217, 239, 55, 176, 68, 207, 106, 132, 15, 116, 61, 198, 62, 182, 225, 202, 105, 150, 183, 81, 170, 13, 41, 199, 3, 185, 235, 14, 155, 21, 126, 119, 169, 72, 12, 236, 48, 209, 190, 113, 218, 100, 52, 111, 189, 92, 192, 114, 117, 160, 133, 203, 163, 34, 206, 246]
28. Length 250
[119, 57, 59, 181, 212, 120, 236, 121, 99, 247, 138, 187, 175, 108, 107, 197, 123, 101, 141, 77, 201, 3, 52, 60, 56, 240, 157, 39, 42, 199, 23, 18, 136, 74, 137, 143, 229, 170, 20, 160, 206, 219, 191, 185, 46, 223, 150, 190, 116, 96, 198, 221, 220, 159, 238, 48, 176, 113, 168, 33, 44, 142, 67, 244, 13, 218, 122, 246, 214, 234, 237, 27, 165, 24, 153, 90, 84, 154, 235, 196, 80, 111, 102, 231, 228, 135, 16, 148, 26, 45, 10, 71, 156, 224, 183, 232, 72, 94, 132, 54, 58, 248, 144, 213, 139, 129, 245, 115, 25, 164, 87, 19, 193, 81, 32, 78, 91, 167, 171, 40, 92, 226, 109, 69, 86, 38, 61, 5, 14, 118, 145, 103, 53, 93, 172, 178, 225, 68, 163, 210, 179, 192, 208, 169, 17, 12, 50, 233, 6, 55, 243, 158, 88, 188, 242, 36, 173, 126, 155, 184, 216, 149, 47, 76, 200, 1, 112, 28, 161, 174, 41, 73, 222, 66, 37, 63, 64, 124, 89, 205, 9, 186, 202, 70, 203, 127, 105, 250, 182, 79, 43, 133, 8, 241, 114, 128, 51, 83, 98, 49, 209, 7, 95, 151, 162, 189, 180, 75, 195, 62, 207, 21, 104, 30, 117, 110, 140, 29, 227, 249, 82, 152, 11, 34, 85, 106, 217, 211, 2, 35, 215, 4, 230, 134, 31, 194, 97, 22, 125, 130, 100, 239, 131, 166, 65, 15, 146, 177, 204, 147]
29. Length 253
[46, 245, 174, 180, 85, 29, 141, 70, 252, 119, 214, 225, 86, 91, 41, 67, 219, 118, 127, 243, 2, 71, 157, 114, 55, 92, 5, 200, 199, 139, 191, 235, 153, 102, 206, 171, 117, 58, 223, 249, 11, 211, 202, 175, 156, 133, 57, 163, 47, 65, 213, 247, 189, 111, 177, 49, 124, 154, 164, 145, 80, 15, 232, 142, 39, 69, 201, 185, 229, 215, 170, 42, 3, 248, 169, 136, 149, 218, 237, 90, 135, 7, 242, 246, 23, 186, 31, 4, 167, 207, 173, 132, 195, 196, 78, 212, 22, 35, 194, 54, 184, 183, 222, 230, 88, 43, 144, 151, 34, 97, 6, 109, 37, 147, 72, 158, 134, 33, 51, 238, 165, 162, 9, 63, 166, 113, 137, 198, 50, 121, 106, 224, 19, 104, 95, 129, 193, 79, 192, 122, 30, 12, 234, 168, 76, 103, 73, 66, 188, 178, 172, 176, 250, 182, 110, 231, 155, 26, 197, 10, 152, 98, 131, 25, 36, 81, 138, 150, 227, 24, 112, 120, 204, 75, 8, 179, 94, 17, 140, 32, 77, 61, 233, 38, 205, 93, 99, 27, 208, 56, 216, 48, 241, 20, 130, 240, 115, 83, 60, 108, 28, 13, 89, 128, 160, 82, 40, 126, 16, 253, 21, 251, 228, 59, 159, 64, 203, 236, 52, 18, 181, 105, 107, 239, 220, 44, 74, 125, 209, 84, 226, 217, 210, 190, 101, 100, 68, 116, 161, 148, 244, 221, 96, 45, 123, 187, 62, 87, 53, 1, 146, 143, 14]
30. Length 256
[159, 248, 75, 43, 111, 38, 4, 17, 155, 87, 81, 208, 53, 230, 65, 11, 108, 228, 146, 212, 137, 225, 144, 189, 86, 105, 84, 128, 97, 50, 223, 15, 83, 169, 217, 47, 88, 236, 114, 181, 115, 177, 102, 250, 246, 104, 80, 45, 240, 14, 196, 52, 247, 41, 198, 32, 182, 206, 226, 101, 70, 94, 113, 49, 254, 59, 42, 154, 77, 253, 112, 215, 99, 25, 134, 92, 95, 150, 64, 178, 118, 79, 130, 63, 129, 131, 57, 218, 85, 204, 3, 163, 158, 186, 10, 199, 24, 125, 251, 51, 74, 160, 207, 120, 233, 30, 19, 9, 56, 167, 58, 117, 164, 54, 220, 229, 234, 203, 211, 103, 205, 69, 39, 5, 31, 191, 106, 180, 116, 245, 21, 222, 91, 235, 8, 2, 214, 29, 238, 176, 135, 61, 227, 202, 122, 252, 231, 89, 187, 37, 149, 96, 190, 172, 73, 18, 71, 1, 179, 46, 156, 201, 165, 256, 151, 27, 242, 188, 126, 124, 244, 100, 107, 143, 170, 72, 255, 40, 67, 192, 185, 219, 20, 157, 98, 237, 136, 168, 141, 224, 232, 44, 139, 132, 22, 60, 109, 90, 175, 171, 62, 23, 161, 12, 76, 210, 68, 184, 93, 243, 48, 209, 174, 200, 121, 123, 36, 173, 140, 133, 145, 6, 110, 152, 142, 241, 55, 138, 147, 193, 213, 127, 7, 34, 66, 153, 26, 13, 162, 183, 239, 78, 249, 221, 28, 194, 16, 35, 33, 82, 195, 148, 216, 119, 166, 197]
fuente
[2,1]
,[2,1,4,3]
,[1,2,6,4,5,3]
. Por si las personas intentan cosas más complicadas :)Respuestas:
Python 3 (con PyPy) - puntuación: 607771
Editar: creo que el error está solucionado, pero todavía no estoy convencido de que esto funcione hasta que demuestre que funciona
Uso
Explicación
Tanteo
Salida en Pastebin.
Anterior ingenua burbuja ordenar ver. (puntuación: 1126232)
Este definitivamente funciona.
fuente
Javascript ES6 - 607,771
Implementa un tipo de burbuja del "extremo más cercano" que burbujea elementos hacia arriba o hacia abajo según la ruta más corta (burbuja hacia arriba o hacia abajo) a una posición de referencia.
No creo que la rutina sea óptima, pero debería estar razonablemente cerca de ella. Como beneficio adicional, ejecuta el conjunto completo de vectores de prueba en milisegundos.Actualizado para iterar sobre el punto de pivote para mejorar la competitividad. También introduje la heurística para compensar el hecho de que los elementos tienen una movilidad más baja moviéndose "hacia arriba" en la lista que moviéndose "hacia abajo" (un fenómeno análogo a la diferencia en la movilidad de electrones y huecos en un semiconductor). Existen grandes diferencias entre esta implementación y las de Sp3000, de ahí que el hecho de que ambas obtengan exactamente 607,771 es espeluznante. Halloween espeluznante
La rutina ahora tarda unos 20 segundos en ejecutarse.
Salida de muestra
rendimientos
fuente
OCaml, puntuación:
11367071136599Editar:
me equivoqué! Había leídoEditar²: Lo arreglé utilizando la observación de que puedes escribir lo que pensé que era SP como P S. También cambié a la versión con mejor puntuación con algunas optimizaciones para hacerlo menos lento.S
que intercambiaría elementos adyacentes y me perdí que el primer y el último elemento se intercambian. Esta implementación se basa en esto como es obvio de laeval
implementación.El tiempo de ejecución es
1.33181.01 segundos en mi sistema usando el binario compilado por elintérprete.fuente
C, puntuación: 607771
Resulta que mi solución es muy similar a la solución Python de Sp3000 (que explica el puntaje idéntico). Nunca he usado Python, así que no puedo decirlo con certeza, pero creo que el concepto es exactamente el mismo:
Código
Uso
Tanteo
Guión:
Resultados:
fuente
C ++ 11, puntaje: 1122052
Implementación muy ingenua que no tiene en cuenta los agujeros en la secuencia de entrada pero tiene en cuenta el valor mínimo en la secuencia.
La lista de argumentos es solo la secuencia de números, sin comas ni corchetes (por ejemplo: "./a.out 2 7 5")
Tanteo
fuente