Esse é um desafio para poucas operações , onde o objetivo é classificar um vetor em ordem crescente, usando o menor número de reversões. Seu algoritmo pode classificar o vetor apenas usando "reversões de subvectores" 1 , mas pode usar outras operações para operações aritméticas, loops, verificar se estão classificadas etc. O número de inversões de subvectores que seu algoritmo realiza é sua pontuação.
1 "Reversão de subvetor":
- Selecione um intervalo de números no vetor e inverta os elementos nesse intervalo.
Para dar um exemplo simples, se você começar com o vetor {4,3,2,1}
, poderá classificá-lo de várias maneiras diferentes:
- Inverta o vetor inteiro. Essa é obviamente a abordagem mais curta, pois requer apenas uma reversão:
{4,3,2,1} -> {1,2,3,4}
- Você pode fazer uma versão da classificação de bolhas, que requer 6 reversões:
{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}
- Você pode começar com os três primeiros elementos, depois os três últimos e, finalmente, os dois primeiros e os dois últimos, o que exige quatro trocas:
{4,3,2,1} -> {2,3,4,1} -> {2,1,4,3} -> {1,2,4,3} -> {1,2,3,4}
- ... e assim por diante. Há uma quantidade infinita de opções disponíveis (você pode repetir qualquer operação, se quiser).
Regras e requisitos:
Seu código deve terminar em menos de um minuto para uma lista com 100 números. Você pode cronometrar isso sozinho, mas jogue limpo 2 .
Você deve armazenar os índices inicial e final de todos os swaps executados, para que a solução possa ser verificada. (Vou explicar o que isso significa abaixo).
O código deve ser determinístico.
Você pode inserir a entrada em qualquer formato que desejar: vetor numérico, lista vinculada, matriz com comprimento ... o que quiser.
Você pode fazer o que quiser em uma cópia do vetor. Isso inclui tentar diferentes reversões e verificar qual é a mais eficiente. A força bruta é perfeitamente adequada, mas atenha-se ao limite de tempo.
A pontuação é o número total de inversões para os 5 vetores de teste. O desempate será o carimbo de data.
Exemplo:
4 1 23 21 49 2 7 9 2 | Vetor / lista inicial 4 1 2 9 7 2 49 21 23 | (2, 8) (virou os elementos entre os índices 2 e 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)
A pontuação seria 6, pois você realizou 6 reversões. Você deve armazenar (não imprimir) os índices listados no lado direito em um formato adequado que possa ser facilmente impresso / impresso para fins de verificação.
Vetores de teste:
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
Estou bastante certo de que encontrar uma solução ideal é difícil para NP (já que é uma classificação regular de panquecas).
2 Sim, pessoas com computadores muito rápidos podem se beneficiar, devido ao prazo de um minuto. Depois de muita discussão, achei que seria melhor se todos fizessem seus próprios testes comparativos, não é um desafio de código mais rápido.
fonte
n-1
flips? Eu só posso provar um limite inferior de cerca de 50.Respostas:
Java, algoritmo genético-ish, 80 + 81 + 79 + 78 + 80 = 398 (anteriormente
418)Depois de tentar várias idéias diferentes e, principalmente, falhar, decidi pelo algoritmo: comece com a matriz de entrada, tente todas as reversões possíveis e mantenha um certo número de resultados com o menor número de execuções, e faça o mesmo com esses resultados, até temos uma matriz classificada.
Por "execuções", quero dizer subarrays máximos que aparecem exatamente ou invertidos na matriz classificada. Basicamente, são subarrays ordenados máximos, mas no caso de elementos repetidos, o número de elementos no meio deve corresponder. Por exemplo, se a matriz classificada for,
2, 2, 3, 3, 4, 4
então,4, 3, 3, 2
é uma execução, mas2, 2, 3, 4
não é (e nem é2, 3, 2
).Nesta versão, otimizei o algoritmo para reverter apenas nos limites da execução e somente se uma execução reversa puder ser associada a uma execução recém-adjacente. Além disso, as execuções são ajustadas e unidas a cada etapa, para evitar recalculá-las da matriz modificada. Isso me permitiu aumentar o "tamanho da população" de 30 para cerca de 3000 e executar várias simulações em vários tamanhos.
Entrada é uma lista de números separados por vírgula e / ou espaço (de stdin). Se a entrada estiver vazia, o programa executa os 5 testes. Cada um leva cerca de 40 segundos aqui.
fonte
Um movimento de força bruta e depois o tipo de seleção (também solução ingênua), 90 + 89 + 88 + 87 + 89 = 443 movimentos
para cada primeira jogada possível, tente e faça uma classificação.
Sim, essa é outra solução ingênua.
Não sei se deve ser uma edição ou outra postagem, mas parece que a solução é muito simples, portanto, a edição é escolhida.
Classificação da Seleção (Solução Ingênua), 92 + 93 + 95 + 93 + 96 = 469 movimentos
Uma solução ingênua usa classificação de seleção.
Não deve haver algumas soluções melhores, mas este post desde que eu não encontrar um melhor (sem pesquisa de força bruta).
(O código acima é JavaScript Shell )
fonte