pengantar

Tentu saja, kita punya banyak tantangan urutan , jadi ini satu lagi.

Urutan Kimberling ( A007063 ) berlaku sebagai berikut:

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

Ini diproduksi dengan mengocok iterasi normal:

[1] 2  3  4  5  6  7  8

Istilah pertama dari urutan tersebut adalah 1. Setelah itu, kami merombak urutan sampai semua istilah di sebelah kiri digunakan. Pengocokan memiliki pola right - left - right - left - .... Karena tidak ada istilah di sebelah kiri 1, tidak ada pengocokan. Kami mendapatkan yang berikut ini:

 2 [3] 4  5  6  7  8  9

Pada iterasi ^ke- i , kami membuang item ^ke- i dan meletakkannya di urutan kami. Ini adalah iterasi ke - 2 , jadi kami membuang item ke - 2 . Urutan menjadi: 1, 3. Untuk iterasi kami berikutnya, kami akan mengocok iterasi saat ini dengan pola di atas. Kami mengambil item yang tidak digunakan pertama di sebelah kanan item ^ke- i . Ini terjadi 4. Kami akan menambahkan ini ke iterasi baru kami:

 4

Sekarang kita akan mengambil item yang tidak digunakan pertama di sebelah kiri item ^ke- i . Ini 2. Kami akan menambahkan ini ke iterasi baru kami:

 4  2

Karena tidak ada item yang tersisa di sebelah kiri item ^ke- i , kami hanya akan menambahkan sisa urutan ke iterasi baru:

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

Ini adalah iterasi ke - 3 kami , jadi kami akan membuang item ke - 3 , yaitu 5. Ini adalah item ketiga dalam urutan kami:

 1, 3, 5

Untuk mendapatkan iterasi berikutnya, ulangi saja prosesnya. Saya sudah membuat gif jika tidak jelas:

^{Gif itu membuat saya lebih lama daripada menulis posting sebenarnya}

Tugas

• Dengan bilangan bulat n -negatif , hasilkan n syarat pertama dari urutan
• Anda dapat menyediakan fungsi atau program
• Ini adalah kode-golf , jadi pengiriman dengan jumlah byte paling sedikit menang!

Kasus uji:

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

Catatan: Koma dalam output tidak perlu. Misalnya, Anda dapat menggunakan baris baru, atau menampilkan daftar, dll.

Pyth, 22 byte

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

Cobalah online: Demonstrasi

Cukup lakukan teknik pengocokan yang dijelaskan dalam OP.

Penjelasan:

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 byte

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]

Ini adalah fungsi tanpa nama yang menerima integer dan mengembalikan array integer. Untuk menyebutnya, tetapkan ke variabel.

Pendekatan di sini sama dengan yang dijelaskan pada OEIS.

Tidak Disatukan:

# 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]

Disimpan 7 byte berkat Mauris!

Mathematica 130 byte

(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)&

Kita mulai dengan daftar yang terdiri dari rentang dari 1ke 3x, di mana xjumlah istilah urutan Kimberling yang diinginkan.

Pada setiap langkah, n, TakeDropistirahat daftar saat menjadi daftar depan 2n+1istilah (di mana pekerjaan dilakukan) dan daftar belakang (yang akan kemudian bergabung dengan ulang daftar depan). Daftar depan dicocokkan dengan pola berikut, di {t___,z,r___}mana z adalah istilah Kimberling di tengah daftar depan. radalah Riffledengan kebalikan dari tdan kemudian daftar belakang ditambahkan. zdihapus dan ditambahkan ke ( AppendTo) urutan Kimberling yang tumbuh.

nditambahkan oleh 1dan daftar saat ini diproses oleh fungsi yang sama viaNest.

Contoh

(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, 126, 156, 151, 151, 249, 236, 263, 243, 101, 121, 121, 120, 120, 47, 229 }

Python 2, 76 byte

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

Penjelasan

Ini adalah formula OEIS setelah banyak transformasi golf-y! Itu bekerja dengan indah . Kode aslinya adalah

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

Saya pertama kali menyingkirkan i, menggantinya dengan a+1mana - mana dan memperluas ekspresi:

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

Kemudian, menulis ulang b<2*a-1sebagai -~b<2*auntuk menyimpan byte spasi, dan memindahkan +1ke seleksi, pembagian dengan 2, dan negasi:

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

Lalu, -b-1adil ~b, jadi kita bisa menulis (b,~b)[b%2]. Ini sama dengan b^0 if b%2 else b^-1menggunakan operator XOR, atau sebagai alternatif b^b%-2,.

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

Pyth, 29 25 byte

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

Jakube menyimpan 4 byte, tetapi saya tidak tahu cara membaca kode lagi.

Ini solusi lama:

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

Terjemahan dari jawaban Python saya. Saya tidak pandai Pyth, jadi mungkin masih ada cara untuk mempersingkat ini.

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 byte

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

Ini adalah kereta monadik tanpa nama yang menerima bilangan bulat di sebelah kanan dan mengembalikan array. Ini kira-kira pendekatan yang sama dengan jawaban Julia saya .

Fungsi terdalam adalah fungsi diad rekursif yang mengembalikan istilah ke- n dalam urutan Kimberling, diberikan n sebagai argumen kiri dan kanan yang identik.

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

Dengan itu di tangan, kami bisa mendapatkan ketentuan individual dari urutan. Namun, masalahnya kemudian menjadi bahwa ini adalah fungsi diadik , yang berarti membutuhkan argumen di kedua sisi. Masukkan ⍨operator! Diberi fungsi fdan input x, f⍨xsama dengan x f x. Jadi dalam kasus kami, merujuk pada fungsi yang disebutkan di atas f, kita dapat membangun kereta monadik berikut:

f⍨¨⍳

Kami berlaku funtuk setiap integer dari 1 ke input, menghasilkan array.

Disimpan 12 byte berkat Dennis!