Wprowadzenie

Oczywiście mamy wiele wyzwań sekwencyjnych , więc oto kolejne.

Sekwencja Kimberling ( A007063 ) wygląda następująco:

1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, 22, ...

Powstaje to przez tasowanie normalnej iteracji:

[1] 2  3  4  5  6  7  8

Pierwszy termin sekwencji to 1. Następnie przetasujemy sekwencję, aż zostaną użyte wszystkie terminy po lewej stronie. Tasowanie ma wzór right - left - right - left - .... Ponieważ po lewej stronie nie ma żadnych terminów 1, nie ma tasowania. Otrzymujemy następujące:

 2 [3] 4  5  6  7  8  9

Na í ^th iteracji możemy odrzucić í ^th element i umieścić, że w naszym sekwencji. Jest to druga iteracja, więc odrzucamy drugi element. Sekwencja postać: 1, 3. W naszej następnej iteracji pomieszamy bieżącą iterację z powyższym wzorem. Bierzemy pierwszy nieużywany przedmiot po prawej stronie i- ^tego przedmiotu. Tak się dzieje 4. Dołączymy to do naszej nowej iteracji:

 4

Teraz weźmiemy pierwszy nieużywany przedmiot po lewej stronie i- ^tego przedmiotu. Jest 2. Dołączymy to do naszej nowej iteracji:

 4  2

Ponieważ po lewej stronie i- ^tego elementu nie pozostały żadne elementy , dodamy resztę sekwencji do nowej iteracji:

 4  2 [5] 6  7  8  9  10  11  ...

To jest nasza trzecia iteracja, więc odrzucimy trzeci przedmiot, którym jest 5. To jest trzeci element w naszej sekwencji:

 1, 3, 5

Aby uzyskać następną iterację, po prostu powtórz proces. Zrobiłem gif, jeśli nie jest jasne:

^{Gif zajął mi więcej czasu niż napisanie prawdziwego posta}

Zadanie

• Biorąc pod uwagę nieujemną liczbę całkowitą n , wypisz pierwsze n składników sekwencji
• Możesz podać funkcję lub program
• To jest golf golfowy , więc wygrywanie z najmniejszą ilością bajtów wygrywa!

Przypadki testowe:

Input: 4
Output: 1, 3, 5, 4

Input: 8
Output: 1, 3, 5, 4, 10, 7, 15, 8

Input: 15
Output: 1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28

Uwaga: Przecinki na wyjściu nie są konieczne. Możesz na przykład użyć znaku nowej linii lub wydrukować listę itp.

Pyth, 22 bajty

JS*3QVQ@JN=J.i>JhN_<JN

Wypróbuj online: Demonstracja

Po prostu wykonuje technikę tasowania opisaną w OP.

Wyjaśnienie:

JS*3QVQ@JN=J.i>JhN_<JN
JS*3Q                    assign the list [1, 2, ..., 3*input-1] to J
     VQ                  for N in range(Q):
       @JN                  print J[N]
            .i              interleave 
              >JhN             J[N+1:] with
                  _<JN         reverse J[:N]
          =J                assign the resulting list to J

Julia, 78 71 bajtów

n->[(i=j=x;while j<2i-3 j=i-(j%2>0?1-j:j+2)÷2;i-=1end;i+j-1)for x=1:n]

Jest to funkcja bez nazwy, która akceptuje liczbę całkowitą i zwraca tablicę liczb całkowitych. Aby go wywołać, przypisz go do zmiennej.

Podejście tutaj jest takie samo, jak opisane w OEIS.

Nie golfowany:

# This computes the element of the sequence
function K(x)
    i = j = x
    while j < 2i - 3
        j = i - (j % 2 > 0 ? 1 - j : j + 2)÷2
        i -= 1
    end
    return i + j - 1
end

# This gives the first n terms of the sequence
n -> [K(i) for i = 1:n]

Zaoszczędź 7 bajtów dzięki Maurisowi!

Matematyka 130 bajtów

(n=0;s={};Nest[(n++;AppendTo[s,z=#[[n]]];Flatten[TakeDrop[#,1+2(n-1)]/.{t___,z,r___}:> 
Riffle[{r},Reverse@{t}]])&,Range[3*#],#];s)&

Zaczynamy od listy składającej się z zakresu od 1do 3x, gdziex jest pożądana liczba terminów sekwencji Kimberling.

Na każdym kroku n, TakeDropprzerywa bieżącą listę do przodu listy 2n+1terminów (gdzie praca jest wykonywana) i tylnej (listy, które zostaną później połączone z przerobione listy przodu). Pierwsza lista jest dopasowana do następującego wzoru, {t___,z,r___}gdzie z to termin Kimberling na środku pierwszej listy. rjest Riffleoznaczony na odwrocie, ta następnie dołączana jest tylna lista. zjest usuwany i dołączany do ( AppendTo) rosnącej sekwencji Kimberling.

njest zwiększany o, 1a bieżąca lista jest przetwarzana przez tę samą funkcję przezNest.

Przykład

(n=0;s={};Nest[(n++;AppendTo[s,z=#[[n]]];Flatten[TakeDrop[#,1+2(n-1)]/.{t___,z,r___}:> 
Riffle[{r},Reverse@{t}]])&,Range[3*#],#];s)&[100]

{1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, 22, 42, 35, 33, 46, 53, 6, 36, 23, 2 , 55, 62, 59, 76, 65, 54, 11, 34, 48, 70, 79, 99, 95, 44, 97, 58, 84, 25, 13, 122, 83, 26, 115, 82, 91 , 52, 138, 67, 90, 71, 119, 64, 37, 81, 39, 169, 88, 108, 141, 38, 16, 146, 41, 21, 175, 158, 165, 86, 191, 45 , 198, 216, 166, 124, 128, 204, 160, 12, 232, 126, 208, 114, 161, 156, 151, 249, 236, 263, 243, 101, 121, 72, 120, 47, 229 }

Python 2, 76 bajtów

for a in range(input()):
 b=a+1
 while-~b<2*a:b=a-(b^b%-2)/2;a-=1
 print a+b

Wyjaśnienie

To jest wzór OEIS po wielu transformacjach golf-y! Udało się pięknie . Oryginalny kod był

i=b=a+1
while b<2*i-3:b=i-(b+2,1-b)[b%2]/2;i-=1
print i+b-1

Najpierw się go pozbyłem i, zastępując go a+1wszędzie i rozszerzając wyrażenia:

b=a+1
while b<2*a-1:b=a+1-(b+2,1-b)[b%2]/2;a-=1
print a+b

Następnie przepisano b<2*a-1jako, -~b<2*aaby zapisać bajt białych znaków i przeniesiono +1do zaznaczenia, podziału przez 2 i negacji:

while-~b<2*a:b=a-(b,-b-1)[b%2]/2;a-=1

Więc -b-1jest po prostu ~b, żebyśmy mogli pisać (b,~b)[b%2]. Jest to równoważne z b^0 if b%2 else b^-1użyciem operatora XOR lub alternatywnie b^b%-2.

while-~b<2*a:b=a-(b^b%-2)/2;a-=1

Pyth, 29 25 bajtów

VQ+.W<hHyN-~tN/x%Z_2Z2hNN

Jakube zapisał 4 bajty, ale nie mam już pojęcia, jak odczytać kod.

Oto stare rozwiązanie:

VQKhNW<hKyN=K-~tN/x%K_2K2)+KN

Tłumaczenie mojej odpowiedzi w języku Python. Nie jestem zbyt dobry w Pyth, więc może nadal istnieją sposoby na skrócenie tego.

VQ                              for N in range(input()):
  KhN                             K = N+1
     W<hKyN                       while 1+K < 2*N:
           =K-~tN/x%K_2K2)         K = (N--) - (K%-2 xor K) / 2
                          +KN     print K + N

APL, 56 44 bajtów

{⍵<⍺+⍺-3:(⍺-1)∇⍺-4÷⍨3+(1+2×⍵)ׯ1*⍵⋄⍺+⍵-1}⍨¨⍳

Jest to nienazwany pociąg monadyczny, który przyjmuje liczbę całkowitą po prawej i zwraca tablicę. To w przybliżeniu to samo podejście, co moja odpowiedź Julii .

Najbardziej wewnętrzna funkcja to rekurencyjna funkcja dyadyczna, która zwraca n- ty termin w sekwencji Kimberlinga, podając n jako identyczne argumenty lewy i prawy.

{⍵<⍺+⍺-3:                                    ⍝ If ⍵ < 2⍺ - 3
         (⍺-1)∇⍺-4÷⍨3+(1+2×⍵)ׯ1*⍵           ⍝ Recurse, incrementing a and setting
                                             ⍝ ⍵ = ⍺ - (3 + (-1)^⍵ * (1 + 2⍵))/4
                                   ⋄⍺+⍵-1}   ⍝ Otherwise return ⍺ + ⍵ - 1

Dzięki temu jesteśmy w stanie uzyskać indywidualne warunki sekwencji. Problemem jest jednak to, że jest to funkcja dyadyczna , co oznacza, że ​​wymaga argumentów po obu stronach. Wpisz ⍨operatora! Biorąc pod uwagę funkcję foraz wejście x, f⍨xjest taki sam jak x f x. Tak więc w naszym przypadku, odnosząc się do wyżej wspomnianej funkcji jako f, możemy zbudować następujący ciąg monadyczny:

f⍨¨⍳

Aplikujemy f do każdej liczby całkowitej od 1 do wejścia, uzyskując tablicę.

Zaoszczędź 12 bajtów dzięki Dennis!