Pertimbangkan permutasi nilai integer dari 1
hingga N
. Misalnya contoh ini untuk N = 4
:
[1, 3, 4, 2]
Kami akan mempertimbangkan daftar ini menjadi siklik, sehingga 1
dan 2
diperlakukan sebagai yang berdekatan. Satu kuantitas yang dapat kita hitung untuk daftar tersebut adalah total selisih kuadrat dari nilai yang berdekatan:
(1-3)² + (3-4)² + (4-2)² + (2-1)² = 10
Tugas Anda adalah menemukan permutasi yang memaksimalkan kuantitas ini, diberi bilangan bulat positif N
. Dalam kasus N = 4
contoh di atas tidak optimal (pada kenyataannya, itu minimal). Kami dapat mencapai perbedaan kuadrat total 18
dengan permutasi berikut (serta beberapa yang lain):
[1, 4, 2, 3]
Algoritme Anda harus berjalan dalam waktu polinomial N
. Secara khusus, Anda tidak bisa hanya menghitung perbedaan kuadrat total dari semua permutasi.
Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter function (out).
Output dapat dalam format string atau string yang nyaman, tidak ambigu, datar. Anda dapat memilih untuk mengembalikan daftar dengan nilai dari 0
ke N-1
alih-alih 1
ke N
.
Aturan standar kode-golf berlaku.
Data Uji
Ada solusi analitik yang bagus untuk masalah ini. Misalnya, semua solusi yang valid untuk N = 10
setara dengan daftar berikut (hingga perubahan dan pembalikan siklus):
[7, 5, 6, 4, 8, 2, 10, 1, 9, 3]
Saya tidak ingin mengungkapkan terlalu banyak di luar itu (walaupun mungkin cukup untuk mengetahui polanya), jadi alih-alih memberikan contoh lagi, Anda dapat memeriksa bahwa hasil Anda memiliki perbedaan kuadrat total berikut untuk diberikan N
:
N Total squared difference
1 0
2 2
3 6
4 18
5 36
6 66
7 106
8 162
9 232
10 322
33 11936
100 333202
333 12308236
1000 333332002
Ini adalah entri OEIS A064842 (yang juga berisi referensi ke kertas dengan solusi untuk tantangan ini jika Anda macet).
sumber
(i<n/2||n%2)^i%2?i+1:n-i
.Python2,
10598 byte7 byte disimpan berkat komentar oleh @ Dennis
Versi yang diedit 58 byte
Saya sudah percaya itu harus dilakukan sebagai satu-liner, tetapi logikanya terlalu kompleks bagi saya. Melihat JavaScript-answer oleh @ user81655 dan notasi lambda di @Dennis Python-answer, saya mencobanya baru.
Kondisinya sama dengan
Sayangnya semua upaya transformasi hanya menghemat
satuno byte dibandingkan dengan terjemahan langsung(i<n/2or n%2)!=i%2
dari logika-JavaScript.sumber
int()
sekitar input. Juga, Anda dapat meletakkan tubuh for loop pada baris yang sama denganfor...
.Python,
5149 byteTerima kasih kepada @xnor karena bermain golf 2 byte!
Cobalah di Ideone .
Bagaimana itu bekerja
Jika saya adalah angka dalam [0, ..., n - 1] , maka ~ i% n = - (i + 1)% n = - (i + 1) + n = (n - 1) - i , artinya peta 0 untuk n - 1 , 1 ke n - 2 dan, secara umum, j th item dari kiri ke j th dari kanan.
Seperti yang dijelaskan dalam jawaban Jelly saya , kita dapat membuat output dengan mengintip nilai yang lebih rendah di antara i dan ~ i% n , dan memilih i jika itu genap dan ~ i% n jika itu ganjil. Kami mencapai ini sebagai berikut.
Jika minimum bahkan,
min(i,~i%n)%-2
akan menghasilkan 0 , sehingga XORing hasilnya dengan i akan menghasilkan i , dan komputasi modulo residunya n akan kembali i .Jika minimumnya ganjil,
min(i,~i%n)%-2
akan menghasilkan -1 , jadi XORkan hasilnya dengan i akan menghasilkan ~ i , sehingga seluruh ekspresi dievaluasi menjadi ~ i% n seperti yang diinginkan.sumber
(i^min(i,n+~i)%-2)%n
.PHP,
7776515049 byteMenggunakan penyandian ISO 8859-1.
Merakit paruh pertama array seperti ini:
N+1-index
(9, 7, 5)1, 9, 3, 7, 5
Sedangkan untuk paruh kedua array, nilai terluar dijumlahkan
N+1
, yang berarti Anda bisa mendapatkan nilai yang tepat dariN-[left value]
mana nilai kiri sudah diketahui.Jalankan seperti ini (ini juga menunjukkan perbedaan kuadrat total) (
-d
ditambahkan hanya untuk estetika):echo
~ß
untuk menghasilkan spasi.sumber
Python 2, 100
Saya tahu sudah ada jawaban python, tapi saya pikir saya mungkin telah melakukan ini secara berbeda.
Dan sebagai tambahan untuk menguji skor total:
sumber
def t(x,n):return sum((x[i]-x[i-1])**2for i in range(n))
menggunakan wrap-around implisit dari indeks negatif dan menyimpan 4 byte. Saya tahu, bukan bagian dari kompetisi. ;)CJam,
171514 byteIni adalah fungsi yang memunculkan integer n dari stack dan mendorong permutasi [0… n-1] sebagai imbalannya. Kode ini menggunakan pendekatan yang sama dengan jawaban Jelly saya .
Cobalah online!
Bagaimana itu bekerja
sumber
LISP, 86 byte
Input dari fungsi memungkinkan untuk memilih nilai awal (m) dan akhir (n) dari urutan.
Untuk menguji fungsi sesuai dengan sampel yang disediakan, n ditetapkan ke N dan m ke 1.
Di sini kode untuk menguji fungsinya:
Cobalah di Ideone !
sumber
Julia, 39 byte
Ini mencetak permutasi 1: n . Permutasi 0: n-1 tidak memerlukan biaya atau menghemat byte:
Versi terakhir ini adalah port langsung dari jawaban Python saya .
sumber
ES6, 77 byte
The
i&1
sampel angka dari ekstrem ke tengah. Thei&2
menambahkan mereka ke awal atau akhir hasil berpasangan.sumber
R,
11786 bytesunting versi lama buggy yang diganti dengan penerapan algoritme @Dennis 'Jelly
sumber