Jest to wyzwanie z najmniejszą liczbą operacji, w którym celem jest uporządkowanie wektora w kolejności rosnącej przy użyciu jak najmniejszej liczby zmian. Twój algorytm może sortować wektor tylko za pomocą „odwrócenia sub-wektora” 1 , ale może używać innych operacji do operacji arytmetycznych, pętli, sprawdzania, czy jest posortowany itp . Liczba odwrotności sub-wektorów wykonywanych przez algorytm jest jego wynikiem.
1 „Odwrócenie sub-wektora”:
- Wybierz zakres liczb w wektorze i odwróć elementy w tym zakresie.
Aby dać prosty przykład, jeśli zaczynasz od wektora {4,3,2,1}
, możesz go posortować na wiele różnych sposobów:
- Odwróć cały wektor. Jest to oczywiście najkrótsze podejście, ponieważ wymaga tylko jednego cofnięcia:
{4,3,2,1} -> {1,2,3,4}
- Możesz wykonać wersję sortowania bąbelkowego, która wymaga 6 cofnięć:
{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}
- Możesz zacząć od pierwszych 3 elementów, potem trzech ostatnich, a na końcu dwóch pierwszych i dwóch ostatnich, co wymaga 4 zamian:
{4,3,2,1} -> {2,3,4,1} -> {2,1,4,3} -> {1,2,4,3} -> {1,2,3,4}
- ... i tak dalej. Dostępnych jest nieskończona ilość opcji (możesz powtórzyć dowolną operację, jeśli chcesz).
Zasady i wymagania:
Twój kod musi kończyć się w mniej niż minutę w przypadku listy zawierającej 100 cyfr. Możesz to zrobić samemu, ale zagraj fair 2 .
Musisz przechowywać indeksy początkowe i końcowe wszystkich wykonywanych transakcji zamiany, aby można było zweryfikować rozwiązanie. (Wyjaśnię, co to oznacza poniżej).
Kod musi być deterministyczny.
Możesz wprowadzić dane w dowolnym formacie: wektor numeryczny, lista z linkami, tablica z długością ... cokolwiek zechcesz.
Możesz zrobić, co chcesz na kopii wektora. Obejmuje to próbę różnych cofnięć i sprawdzenie, która jest najbardziej wydajna. Brutalne zmuszanie jest w porządku, ale trzymaj się limitu czasu.
Wynik jest całkowitą liczbą przerzutów dla 5 wektorów testowych. Tie-breaker będzie datownikiem.
Przykład:
4 1 23 21 49 2 7 9 2 | Początkowy wektor / lista 4 1 2 9 7 2 49 21 23 | (2, 8) (przerzucono elementy między indeksami 2 i 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)
Wynik wyniósłby 6, ponieważ wykonałeś 6 zwrotów. Musisz przechowywać (nie drukować) indeksy wymienione po prawej stronie w odpowiednim formacie, który można łatwo wydrukować / wydrukować w celu weryfikacji.
Wektory testowe:
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
Jestem całkiem pewien, że znalezienie optymalnego rozwiązania jest trudne NP (ponieważ regularne sortowanie naleśników jest).
2 Tak, ludzie z bardzo szybkimi komputerami mogą skorzystać, ze względu na limit jednej minuty. Po długiej dyskusji doszedłem do wniosku, że najlepiej, jeśli każdy przeprowadzi własne testy porównawcze, nie jest to najszybsze wyzwanie dla kodu.
źródło
n-1
flipami? Mogę udowodnić jedynie dolną granicę wynoszącą około 50.Odpowiedzi:
Java, algorytm genetyczny, 80 + 81 + 79 + 78 + 80 = 398 (wcześniej
418)Po wypróbowaniu wielu różnych pomysłów i przeważnie zawiodłem, zdecydowałem się na ten algorytm: zacznij od tablicy wejściowej, wypróbuj wszystkie możliwe zmiany i zachowaj pewną liczbę wyników przy najmniejszej liczbie przebiegów, a następnie zrób to samo dla tych wyników, aż otrzymujemy posortowaną tablicę.
Przez „przebiegi” rozumiem maksymalne podpowierzchnie, które pojawiają się dokładnie lub odwrotnie w posortowanej tablicy. Zasadniczo są to maksymalnie posortowane podgrupy, ale w przypadku powtarzających się elementów liczba elementów na środku powinna być taka sama. Np. Jeśli posortowana tablica jest
2, 2, 3, 3, 4, 4
wtedy4, 3, 3, 2
uruchomieniem, ale2, 2, 3, 4
nie jest (i nie ma2, 3, 2
).W tej wersji zoptymalizowałem algorytm do cofania tylko na granicach przebiegu i tylko wtedy, gdy bieg do tyłu może zostać połączony z nowo sąsiadującym przebiegiem. Ponadto przebiegi są dostosowywane i łączone na każdym kroku, aby uniknąć ponownego obliczenia ich ze zmodyfikowanej tablicy. Pozwoliło mi to zwiększyć „wielkość populacji” z 30 do około 3000 i przeprowadzić wiele symulacji w różnych rozmiarach.
Dane wejściowe to lista liczb oddzielonych przecinkiem i / lub spacją (od standardowego wejścia). Jeśli dane wejściowe są puste, program uruchamia 5 testów. Każda z nich zajmuje tutaj około 40 sekund.
źródło
Jeden ruch brutalna siła, a następnie sortowanie selekcji (również naiwne rozwiązanie), 90 + 89 + 88 + 87 + 89 = 443 ruchów
dla każdego możliwego pierwszego ruchu wypróbuj go, a następnie wykonaj sortowanie według wyboru.
Tak, to kolejne naiwne rozwiązanie.
Nie jestem pewien, czy to powinna być edycja, czy inny post, ale wydaje się, że rozwiązanie jest zbyt proste, więc edycja jest wybrana.
Wybór sortowania (rozwiązanie naiwne), 92 + 93 + 95 + 93 + 96 = 469 ruchów
Naiwne rozwiązanie wykorzystuje sortowanie według wyboru.
Tam musi być jakieś lepsze rozwiązania, ale pisać to, ponieważ nie mogę znaleźć lepszego (bez wyszukiwania brute-force).
(Powyższy kod to JavaScript Shell )
źródło