Definisi

Mari kita sebut deret integer (tak terbatas) universal jika berisi setiap deret integer terbatas sebagai urutan berikutnya.

Dengan kata lain, urutan bilangan bulat (a ₁ , a ₂ , ...) bersifat universal jika dan hanya jika, untuk setiap urutan bilangan bulat terbatas (b ₁ ,…, b _n ) , ada offset k sedemikian rupa sehingga (a _{k + 1} ,…, A _{k + n} ) = (b ₁ ,…, b _n ) .

Urutan bilangan prima positif, misalnya, tidak universal, antara lain karena alasan berikut.

• Itu tidak mengandung bilangan bulat negatif, 1 , atau angka gabungan.

• Meskipun mengandung 3 , itu tidak mengandung urutan yang berdekatan (3, 3, 3) .

• Meskipun mengandung 2 dan 5 , itu tidak mengandung urutan yang berdekatan (2, 5) .

• Meskipun mengandung urutan yang berdekatan (7, 11, 13) , itu tidak mengandung urutan yang berdekatan (13, 11, 7) .

Tugas

Pilih salah satu urutan bilangan bulat yang universal (a ₁ , a ₂ , ...) dan menerapkannya dalam bahasa pemrograman pilihan Anda, taat kepada aturan berikut.

• Anda dapat mengirimkan program atau fungsi lengkap.

• Anda memiliki tiga opsi untuk I / O:

  1. Jangan masukan dan cetak atau kembalikan seluruh urutan.

  2. Ambil indeks n sebagai masukan dan mencetak atau kembali sebuah _n .

  3. Ambil indeks n sebagai input dan cetak atau kembali (a ₁ ,…, a _n ) .

• Untuk opsi I / O 2 dan 3 , Anda dapat menggunakan pengindeksan berbasis 0 jika Anda mau.

• Kiriman Anda harus bersifat deterministik: jika dijalankan beberapa kali dengan input yang sama, ia harus menghasilkan output yang sama.

Selain itu, kecuali jika sudah jelas, harap buktikan bahwa urutan yang Anda pilih bersifat universal. Bukti Anda mungkin tidak bergantung pada dugaan yang tidak terbukti.

Aturan standar kode-golf berlaku. Semoga kode terpendek dalam byte menang!

Sekam , 5 byte

Ini mencetak daftar yang tak terbatas

ΣṖ…ݱ

Cobalah online! atau cari indeks pertama dari urutan Anda . (Membutuhkan banyak memori untuk sebagian besar urutan)

Penjelasan:

   ݱ   Infinite list [1,-1,2,-2,3,-3,4,-4,5,-5...]
  …     Rangify       [1,0,-1,0,1,2,1,0,-1,-2,...]
 Ṗ      Powerset
Σ       Concatenate

Dalam Husk Ṗberperilaku baik untuk daftar yang tak terbatas. Anda dapat melihat perilakunya di sini

Python 2 , 49 46 43 byte

def f(n):d=len(`n`);return n/d**(n%d)%d-d/2

f(n)kembali sebuah _n saja. Ini menggunakan digit terkecil dari nbasis duntuk mengekstraksi salah satu digit yang lebih tinggi.

Cobalah online! Skrip ini (milik Dennis) mengambil urutan berhingga apa pun dan memberi Anda tempat di nmana urutan itu dimulai.

Penjelasan

n/d**(n%d)%d-d/2
     (n%d)         least significant digit of n
n/d**(   )%d       get n%d-th digit of n
            -d/2   offset to get negative values

Misalnya, untuk ndalam rentang 3141592650ke 3141592659, d=10dan digit terakhir nmemilih salah satu dari digit lainnya. Kemudian kita tambahkan -d/2untuk mendapatkan nilai negatif.

n%d:       0  1  2  3  4  5  6  7  8  9
f(n)+d/2:  0  5  6  2  9  5  1  4  1  3
f(n):     -5  0  1 -3  4  0 -4 -1 -4 -2

Alternatif mandiri, juga 43 byte:

n=input();d=len(`n`);print n/d**(n%d)%d-d/2

Brachylog 2, 11 byte

≜~×-₂ᵐ~ȧᵐ≜∋

Cobalah online!

Saya juga mencoba algoritma yang menggunakan partisi aditif pada daftar, tetapi tidak lebih pendek. Ini adalah generator yang menghasilkan aliran bilangan bulat tak terbatas sebagai keluaran; tautan TIO memiliki header untuk mencetak sepuluh ribu pertama darinya.

Penjelasan

Program dimulai dengan mencoba semua kemungkinan integer secara berurutan ( ≜mencoba semua kemungkinan yang tersisa, untuk integer secara default). Itu 0, 1, -1, 2, -2, dll. (Meskipun bilangan bulat negatif tidak mencapai akhir program). Ini adalah satu-satunya langkah "tak terbatas" dari program; semua yang lain terbatas.

~×kemudian menghasilkan semua faktorisasi yang mungkin dari bilangan bulat, memperlakukan pesanan yang berbeda sebagai berbeda, dan hanya menggunakan nilai dari 2 ke atas (sehingga hanya ada banyak yang terbatas); perhatikan bahwa bilangan komposit diizinkan dalam factorisation, bukan hanya bilangan prima. Ini berarti bahwa semua urutan kemungkinan bilangan bulat ≥ 2 akan dihasilkan oleh langkah ini di beberapa titik dalam pelaksanaan fungsi (karena urutan seperti itu pasti memiliki beberapa produk, dan produk tersebut akan dihasilkan di beberapa titik oleh awal ≜).

Kita kemudian perlu memetakan himpunan sekuens tersebut ke himpunan semua sekuens integer, yang dilakukan dalam dua langkah: mengurangkan 2 ( -₂) dari setiap elemen ( ᵐ), memberi kita sekumpulan semua sekuens integer nonnegatif, lalu mengambil plus atau minus ( ~ȧ, yaitu "nilai yang memiliki nilai absolut") setiap elemen (ᵐ). Langkah terakhir jelas-jelas tidak deterministik, sehingga Brachylog memperlakukannya sebagai generator, menghasilkan semua daftar yang mungkin yang elemennya plus atau minus elemen yang sesuai dari daftar input. Ini berarti bahwa kita sekarang memiliki generator untuk semua urutan bilangan bulat yang mungkin, dan itu menghasilkan mereka dalam urutan yang berarti mereka semua dihasilkan (khususnya, urutan yang Anda dapatkan jika Anda mengambil nilai absolut dari setiap elemen, tambahkan 2 untuk setiap elemen, dan kemudian memesan oleh produk dari elemen yang dihasilkan).

Sayangnya, pertanyaannya menginginkan urutan tunggal, bukan urutan urutan, jadi kita perlu dua perintah lagi. Pertama, ≜meminta Brachylog untuk secara eksplisit menghasilkan urutan sekuens secara ketat (sebagai lawan menghasilkan struktur data yang menggambarkan konsep sekuens yang dihasilkan melalui metode ini, dan tidak benar-benar menghasilkan sekuens sampai diperlukan); ini terjadi untuk membuat program lebih cepat dalam hal ini, dan memastikan bahwa output dihasilkan dalam urutan yang diminta. Akhirnya, ∋menyebabkan generator mengeluarkan elemen-elemen dari urutan individu satu per satu (pindah ke urutan berikutnya setelah itu mengeluarkan semua elemen dari urutan sebelumnya).

Hasil akhirnya: setiap urutan bilangan bulat yang mungkin dihasilkan dan dihasilkan, satu elemen pada satu waktu, dan semua disatukan menjadi satu urutan universal tunggal.

Pyth - 11 byte

nproduk daya cartesian [-n, n], untuk semua n.

.V1js^}_bbb

Cobalah online di sini (secara terbatas).

Python 2 , 100 99 byte

• Disimpan satu byte berkat ovs ; iterasi di atas itertoolsbuilt-in ke loop tanpa batas.

from itertools import*
for n in count():
 for P in permutations(range(-n,n)*n):
	for p in P:print p

Cobalah online!

Tanpa batas nwaktu mencetak semua permutasi dari- kali rentang integer berulang [-n; n)untuk semua integer non-negatif n.
Anda dapat mencari offset pertama kuntuk setiap urutan menggunakan versi yang dimodifikasi ini .

Perl 6 , 91 byte

loop (my$i=1;;$i++){my@n=(-$i..$i);my@m=@n;loop (my$k=1;$k <$i;$k++){@m=@m X@n;};print @m;}

Cobalah online!

Ini menggunakan metode yang mirip dengan beberapa jawaban lainnya. Menggunakan produk Cartesian untuk mencetak elemen (-1,0,1), lalu semua pasangan elemen yang (-2,-1,0,1,2)dipesan, kemudian semua kembar tiga elemen yang dipesan (-3,-2,-1,0,1,2,3), dll.

Saya baru mengenal Perl, jadi mungkin ada lebih banyak golf yang bisa dilakukan.

Versi yang lebih mudah dibaca:

loop (my $i = 1; ; $i++) {
  my @n = (-$i..$i);
  my @m = @n;
  loop (my $k=1; $k <$i; $k++) {
    @m = @m X @n;
  }
  print @m;
}