Wyzwanie
Biorąc pod uwagę liczbę całkowitą n ≥ 4 , wyprowadzaj permutację liczb całkowitych [0, n-1] z tą właściwością, że nie ma dwóch kolejnych liczb całkowitych (liczb całkowitych z różnicą bezwzględną 1) obok siebie.
Przykłady
- 4 → [1, 3, 0, 2]
- 5 → [0, 2, 4, 1, 3]
- 6 → [0, 2, 4, 1, 3, 5]
- 7 → [0, 2, 4, 1, 5, 3, 6]
Zamiast tego możesz użyć indeksowania 1 (używając liczb całkowitych [1, n] zamiast [0, n-1] ).
Twój kod musi działać w czasie wielomianowym w n , więc nie możesz wypróbować wszystkich permutacji i przetestować każdego z nich.
[[1,3],[0,2]]
akceptowalny format wyjściowy?Odpowiedzi:
Galaretka ,
32 bajtySortuje liczby całkowite w [1, ..., n] według ich LSB.
Wypróbuj online!
źródło
Þ
sortowanie stabilne, ponieważ jest realizowane za pomocąsorted
funkcji Python , która gwarantuje stabilność .Python 2 , 32 bajty
Wypróbuj online!
źródło
Python 3 ,
40, 38 bajtówWypróbuj online!
To biegnie w
O(n)
czasie.Dzięki Dennis za oszczędność 2 bajtów!
źródło
Python 2 , 34 bajty
Wypróbuj online!
Python 2 , 40 bajtów
Wypróbuj online!
źródło
Haskell, 22 bajty
f jest funkcją n, która zwraca odpowiednio uporządkowaną listę. Korzystam z opcji indeksowania 1.
źródło
Oktawa , 17 bajtów
Wypróbuj online!
Wykorzystuje to to samo podejście, co wiele innych. Połącz dwa wektory, jeden ze wszystkimi liczbami parzystymi w zakresie obejmującym 2 ... x i wszystkimi liczbami nieparzystymi w zakresie obejmującym 1 ... x . Składnia powinna być dość oczywista, więc nie wyjaśnię tego.
źródło
3
i2
obok siebief(4)
?JavaScript (ES6), 40 bajtów
Edycja: Zapisano 1 bajt dzięki @Arnauld.
źródło
Gaia , 2 bajty
Wypróbuj online!
Jest to prosto (stabilna) ∫ orts liczby całkowite w zakresie [1, wejściowych] ich pa r ści.
źródło
R ,
393635 bajtówWypróbuj online!
źródło
05AB1E , 3 bajty
Port odpowiedzi Python dla DJMcMayhem i galaretki Dennisa
Wypróbuj online!
W jaki sposób?
źródło
Japt, 4 bajty
Można również wymienić
u
sięv
uzyskać inną kolejność.Spróbuj
Lub, jeśli możemy wyprowadzić tablicę 2 tablic:
Spróbuj
źródło
4
, niestety; możesz naprawić pierwszy, zmieniającu
nav
lubo
naõ
.Mathematica, 50 -> 47 -> 42 bajty
Wypróbuj online!
Podziękowania dla user202729 za zwrócenie uwagi na podwójny potencjał optymalizacji Dołącz [] do Flatten [] i używania czystych funkcji.
Chciałbym dodać dwie uwagi.
1) Zbudowanie konkretnej permutacji bez spadającej lub rosnącej sukcesji jest dość proste dla n> = 4, zgodnie z żądaniem n PO.
Składa się z dwóch kolejnych list.
Dla parzystych n są to:
lista1 = (2,4, ..., n / 2)
lista2 = (1,3, ..., n / 2-1)
Dla nieparzystych n mamy:
list1 = (2,4, ..., Floor [n / 2])
list2 = (1,3, ..., Floor [n / 2])
Dla tego „algorytmu” musi zostać podjęta tylko jedna decyzja (n parzysta lub nieparzysta), reszta to po prostu zapisanie n liczb.
Możliwe rozwiązanie Mathematica znajduje się u góry.
2) Powiązanym pytaniem jest, ile takich permuacji istnieje w funkcji n.
Mathematica, 124 bajty
Wypróbuj online!
Przykład:
Liczenie liczby takich permutacji jest standardowym problemem.
Dla n = 4 są 2: {{2,4,1,3}, {3,1,4,2}}
Dla n = 5 jest 14: {{1,3,5,2,4}, {1,4,2,5,3}, {2,4,1,3,5}, {2,4, 1,5,3}, {2,5,3,1,4}, {3,1,4,2,5}, {3,1,5,2,4}, {3,5,1, 4,2}, {3,5,2,4,1}, {4,1,3,5,2}, {4,2,5,1,3}, {4,2,5,3, 1}, {5,2,4,1,3}, {5,3,1,4,2}}
Liczba a (n) tych permutacji szybko rośnie: 2, 14, 90, 646, 5242, 47622, 479306, 5296790, 63779034, ...
Dla dużego n stosunek a (n) / n! wydaje się zbliżać do granicy 1 / e ^ 2 = 0,135335 ... Nie mam ścisłego dowodu, ale jest to tylko przypuszczenie z dowodów numerycznych. Możesz to przetestować, próbując uruchomić program online.
Powyższy program (na podstawie podanego poniżej odniesienia) oblicza te liczby.
Więcej informacji można znaleźć w odpowiedniej sekwencji na OEIS: A002464 . Problem Hertzsprunga: sposoby ułożenia n nieatakujących królów na planszy n X n, z 1 w każdym rzędzie i kolumnie. Również liczba permutacji o długości n bez rosnących lub malejących sukcesji.
źródło
[some text](the_link)
. Jeśli chodzi w szczególności o link „Wypróbuj online”, witryna https://tio.run/, która jest hostowana przez nasz własny @Dennis, zawiera łącza do wszelkiego rodzaju języków programowania. Wolfram Language (Mathematica) jest jednym z nich. U góry możesz kliknąć przycisk odtwarzania, aby uruchomić kod, lub przycisk hiperłącza, aby skopiować „Wypróbuj online”. (znaczniki). I możesz podzielić swój kod na rzeczywisty „Kod” (twoje zgłoszenie), z opcjonalnym nagłówkiem / stopką do (ładnego) drukowania jednej lub wielu przypadków testowych.JavaScript (Node.js) , 42 bajty
Wypróbuj online!
JavaScript (Node.js) , 47 bajtów
Wypróbuj online!
źródło
Rubinowy , 27 bajtów
Wypróbuj online!
Korzystanie z indeksowania 1
źródło
Biała spacja , 161 bajtów
Oto oficjalne, nieskomentowane zgłoszenie: Wypróbuj online!
Wypróbuj online!
Poświęciłem kilka bajtów, aby program działał bezbłędnie. Wierzę, że mógłbym stracić około 7-8 bajtów i nadal by wyświetlał się poprawnie, ale wyświetlałby również komunikaty o błędach i nikt tego nie chce.
Pełne bajty Objaśnienie:
źródło
push_0, read_STDIN_as_int, push_0, retrieve
możnapush_0, duplicate_0, read_STDIN_as_int, retrieve
uratować bajt. I pierwsza etykieta może być pusta zNSSN
zamiastNSSSN
(a następnie druga etykieta może byćNSSSN
; trzeciaNSSTN
; czwartaNSSSSN
). Powinno to również zaoszczędzić 8 bajtów. Możesz także usunąć pierwszy,Jump_to_third_label
ponieważ masz jużSet_third_label
prawo pod nim. Łącznie: 140 bajtów ; (lub z komentarzami: Wypróbuj online .) -3 bajty, jeśli usunieszNNN
wyjście.F # (mono) , 27 bajtów
Wypróbuj online!
źródło
Gol> <> , 14 bajtów
Wypróbuj online!
Przykład pełnego programu i jak to działa
źródło
J , 10 bajtów
Wypróbuj online!
Wyjaśnienie:
źródło
Java 8, 56 bajtów
Port odpowiedzi JavaScript (ES6) @Neil .
Wypróbuj online.
Stara 66 bajtów odpowiedź:
Wypróbuj online.
Wyjaśnienie:
źródło
Rubinowy, 27 bajtów
Jak w tej odpowiedzi ,
n
pierwsze liczby całkowite są sortowane według najmniej znaczącego bitu.Wypróbuj online!
źródło