Daj permutację bez dwóch kolejnych liczb całkowitych obok siebie

18

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.

Anush
źródło
Kiedy mówisz „wyprowadzaj permutację”, masz na myśli listę? Czy możemy stworzyć funkcję, która implementuje samo mapowanie permutacji?
xnor
@xnor Powinien być wyprowadzany w postaci czytelnej dla człowieka. Nie obchodzi mnie dokładnie jak.
Anush
Byłby [[1,3],[0,2]]akceptowalny format wyjściowy?
Kudłaty
@Shaggy To nie jest świetne. Czy to oznacza 1,3,0,2?
Anush
Powiązane
Peter Taylor

Odpowiedzi:

31

Galaretka , 3 2 bajty

ḂÞ

Sortuje liczby całkowite w [1, ..., n] według ich LSB.

Wypróbuj online!

Dennis
źródło
Łał! To jest niesamowite.
Anush
2
„Sortuj według LSB” oznacza, że ​​co drugi przesuwa się na początek, ale czy definicja galaretki wymaga, aby liczby w każdej połowie pozostawały w oryginalnej kolejności? Jeśli nie, 100 (4) może znajdować się obok 101 (5) i nadal być „sortowane według LSB”. Nie obwiniasz kodu, ale może komentarz opisujący nie jest kompletny?
WGroleau
1
@WGroleau Tak, Þsortowanie stabilne, ponieważ jest realizowane za pomocą sortedfunkcji Python , która gwarantuje stabilność .
user202729
3
Algorytm jest dla mnie bardziej imponujący niż jego niewielki rozmiar, jeśli chodzi o jego spryt. Przypuszczam, że można także odwrócić kolejność bitów, sortować i odwrócić.
WGroleau,
4
Może istnieć tylko 65536 różnych dwubajtowych programów Jelly. To niesamowite , wiele z nich okazuje się być odpowiedzią na wyzwania ppcg.
Anush
8

Python 3 , 40 , 38 bajtów

lambda n:[*range(1,n,2),*range(0,n,2)]

Wypróbuj online!

To biegnie w O(n)czasie.

Dzięki Dennis za oszczędność 2 bajtów!

DJMcMayhem
źródło
Zwycięzca najszybszej nagrody! :)
Anush
Najszybszy działający lub pierwszy opublikowany?
WGroleau
2
@WGroleau Pierwszy opublikowany.
user202729
6

Haskell, 22 bajty

f jest funkcją n, która zwraca odpowiednio uporządkowaną listę. Korzystam z opcji indeksowania 1.

f n=[2,4..n]++[1,3..n]
Pingwin
źródło
6

Oktawa , 17 bajtów

@(x)[2:2:x,1:2:x]

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.

Stewie Griffin
źródło
1
Nie są 3i 2obok siebie f(4)?
pajonk
Ups ... naprawiono. Ta sama liczba bajtów. :-)
Stewie Griffin
5

JavaScript (ES6), 40 bajtów

f=
n=>[...Array(i=n)].map(_=>(i+--i)%(n|1))
<input type=number min=4 oninput=o.textContent=f(+this.value).join`\n`><pre id=o>

Edycja: Zapisano 1 bajt dzięki @Arnauld.

Neil
źródło
5

Gaia , 2 bajty

r∫

Wypróbuj online!

Jest to prosto (stabilna) orts liczby całkowite w zakresie [1, wejściowych] ich pa r ści.

Pan Xcoder
źródło
Ten sam komentarz co w przypadku Jelly: czy algorytm lub definicja języka gwarantuje, że obie połówki pozostaną w oryginalnej kolejności?
WGroleau
@WGroleau Tak, w Gaia meta-operator sortowania jest stabilny.
Pan Xcoder
5

R , 39 36 35 bajtów

function(x)c(seq(2,x,2),seq(1,x,2))

Wypróbuj online!

ngm
źródło
Końcowa NA dla liczb nieparzystych.
JayCe
Wina żony. Musieliśmy jechać na rowerze, zanim mogłem to naprawić. Ale ogoliłeś też trochę bajtów.
ngm
Tak, czułem się źle, prosząc cię o dodanie bajtów, więc musiałem znaleźć sposób na usunięcie niektórych ... to zadziałało dobrze.
JayCe
4

Japt, 4 bajty

Można również wymienić usię vuzyskać inną kolejność.

õ ñu

Spróbuj

Lub, jeśli możemy wyprowadzić tablicę 2 tablic:

õ ó

Spróbuj

Kudłaty
źródło
Technicznie drugi generuje listę liczb oddzielonych przecinkami ;-) Oba zawodzą 4, niestety; możesz naprawić pierwszy, zmieniając una vlub ona õ.
ETHprodukcje
3

Mathematica, 50 -> 47 -> 42 bajty

p = Join[Range[2, #, 2], Range[1, #, 2]] &

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

a[0] = a[1] = 1; a[2] = a[3] = 0;
a[n_] := a[n] = (n + 1)*a[n - 1] - (n - 2)*a[n - 2] - (n - 5)*a[n - 3] + (n - 3)*a[n - 4]

Wypróbuj online!

Przykład:

a[#] & /@ Range[4, 12]

{2, 14, 90, 646, 5242, 47622, ​​479306, 5296790, 63779034}

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.

Dr Wolfgang Hintze
źródło
@ Stewie Griffin Ponieważ jestem tu nowy, wyjaśnij bardziej szczegółowo, co masz na myśli. W mojej pierwszej uwadze podałem algorytm i kod, który rozwiązuje problem w czasie wielomianowym. Dlatego należy uznać to rozwiązanie za wyzwanie. Druga część stanowi ciekawy problem. Dlatego należy to traktować jako komentarz.
Dr Wolfgang Hintze
Pozwoliłem sobie nieco zmodyfikować twoje zgłoszenie, aby Twój kod Mathematica znalazł się na górze. W przypadku wyzwań związanych z golfem obowiązkowe jest podanie rzeczywistego kodu (możliwie najkrótszego). Sposób, w jaki go sformatowałem, staje się odpowiedzią Mathematica, tak jak zapewne zamierzałeś, i nadal masz pod nim twoje oryginalne wyjaśnienie. Jeśli uważasz, że czegoś brakuje lub nieprawidłowo zredagowałem twoją wstępną odpowiedź, możesz ją edytować samodzielnie. Witamy w PPCG! :)
Kevin Cruijssen
@ Kevin Cruijssen Dziękuję bardzo za ciepłe przyjęcie i edycję mojego naiwnego zgłoszenia. Dodałem teraz program Mathematica do drugiej uwagi. Który najprawdopodobniej nie jest lege artis. Przede wszystkim nie wiem, jak stworzyć fajny link „spróbuj online”.
Dr Wolfgang Hintze
Dowolny link można utworzyć za pomocą [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.
Kevin Cruijssen
Przepraszam za mój nieco tępy komentarz, a później brak odpowiedzi! Odpowiedź pojawiła się w kolejce recenzji i nie zauważyłem kodu z powodu formatowania. Często zdarza się, że nowi użytkownicy podają „interesujące uwagi” do wyzwań, nie podając rzeczywistej odpowiedzi. Chociaż odbywa się to w dobrej wierze, nie o to chodzi w witrynie. Myślałem, że to taka odpowiedź. Powinienem był odpowiedzieć na twój komentarz, ale spieszyłem się i nie mogłem napisać nowego komentarza, więc zamiast tego usunąłem stary. Przeprosiny! Witamy na stronie! Mam nadzieję, że zostaniesz! :)
Stewie Griffin
2

Biała spacja , 161 bajtów

Oto oficjalne, nieskomentowane zgłoszenie: Wypróbuj online!

push_0   
read_n	
		push_0   
retreive_n			push_1  		
subtract	   dup_and_out[ 
 	
 	]label_s'
   
'push_2  		 
subtract	   dup[ 
 ]jump_next_if_neg:
		  
:dup_and_out[ 
 	
 	]else_jump_back:
 
 
:label_ss'
    
'push_0   
retreive_n			push_2  		 
subtract	   dup_and_out[ 
 	
 	]dup[ 
 ]jump_next:
 
    
:label_ssss'
      
'push_2  		 
subtract	   dup[ 
 ]jump_end_if_neg:
		   
:dup_and_out[ 
 	
 	]else_jump_back:
 
    
:label_sss'
     
'end



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:

[Space][Space][Space][N]                   Push a 0 on the stack
[Tab][Tab][N][Tab][Tab][Tab][Tab]          Read input value and store in heap
[Space][Space][Space][N]                   Push a 0 on the stack again
[Tab][Tab][Tab]                            Retrieve the value from the heap
[Space][Space][Tab][Tab][N]                Push a -1 on the stack
[Tab][Space][Space][Space]                 Add -1 to value
[Space][N][Space]                          Duplicate 
[Tab][N][Space][Tab]                       Output
[N][Space][Space][Space][N]                Set First Label
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 Subtract 2 from value
[Space][N][Space]                          Duplicate
[N][Tab][Tab][Space][Space][N]             If negative, jump to second label
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[N][Space][N][Space][N]                    Jump back to first label
[N][Space][Space][Space][Space][N]         Set Second Label
[Space][Space][Space][N]                   Push a 0 on the stack
[Tab][Tab][Tab]                            Retrieve input value from heap again
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 This time, Add a -2 to the value
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[Space][N][Space]                          Duplicate
[N][Space][N][Space][Tab][N]               Jump to third label
[N][Space][Space][Space][Tab][N]           Set third label
[Space][Space][Tab][Tab][Space][N]         Push a -2 on the stack
[Tab][Space][Space][Space]                 Subtract 2 from value
[Space][N][Space]                          Duplicate
[N][Tab][Tab][Space][Space][Space][N]      Jump to end if negative
[Space][N][Space]                          Duplicate
[Tab][N][Space][Tab]                       Output
[N][Space][N][Space][Tab][N]               Jump back to third label
[N][Space][Space][Space][Space][Space][N]  Set fourth label/end
[N][N][N]                                  Terminate
X1M4L
źródło
Niektóre rzeczy do golfa: push_0, read_STDIN_as_int, push_0, retrievemożna push_0, duplicate_0, read_STDIN_as_int, retrieveuratować bajt. I pierwsza etykieta może być pusta z NSSNzamiast NSSSN(a następnie druga etykieta może być NSSSN; trzecia NSSTN; czwarta NSSSSN). Powinno to również zaoszczędzić 8 bajtów. Możesz także usunąć pierwszy, Jump_to_third_labelponieważ masz już Set_third_labelprawo pod nim. Łącznie: 140 bajtów ; (lub z komentarzami: Wypróbuj online .) -3 bajty, jeśli usuniesz NNNwyjście.
Kevin Cruijssen
1

Gol> <> , 14 bajtów

FL:2%Z}:3=?$|B

Wypróbuj online!

Przykład pełnego programu i jak to działa

1AGIE;GDlR~
FL:2%Z}:3=?$|B

1AG          Register row 1 as function G
   IE;       Take number input; halt on EOF
      GD     Call G and print the stack
        lR~  Empty the stack
             Repeat indefinitely

F           |   Repeat n times...
 L              Push loop counter (0..n-1)
  :2%Z}         If even, move to bottom of the stack
       :3=?$    If top == 3, swap top two
                  This is activated only once to make [2 0 3 1]
             B  Return
Bubbler
źródło
1

J , 10 bajtów

i./:2|1+i.

Wypróbuj online!

Wyjaśnienie:

  /:          sort
i.            the numbers in the range 0..n-1 
    2|        according the remainder mod 2 of 
      1+i.    the numbers in the range 1..n   
Galen Iwanow
źródło
1

Java 8, 56 bajtów

n->{for(int i=n;i>0;)System.out.println((i+--i)%(n|1));}

Port odpowiedzi JavaScript (ES6) @Neil .

Wypróbuj online.


Stara 66 bajtów odpowiedź:

n->{String[]r={"",""};for(;n-->0;)r[n%2]+=n+" ";return r[0]+r[1];}

Wypróbuj online.

Wyjaśnienie:

n->{                  // Method with integer parameter and String return-type
  String[]r={"",""};  //  Result-Strings, both starting empty
  for(;n-->0;)        //  Loop in the range (n, 0]
    r[i%2]+=i+" ";    //   Append `i` and a space to one of the two result-Strings,
                      //   depending on if it is even (first) or odd (second)
  return r[0]+r[1];}  //  Return the two result-Strings appended to each other
Kevin Cruijssen
źródło
1

Rubinowy, 27 bajtów

->n{(1..n).sort_by{|i|i&1}}

Jak w tej odpowiedzi , npierwsze liczby całkowite są sortowane według najmniej znaczącego bitu.

Wypróbuj online!

Eric Duminil
źródło