Dengan vektor -dimensi dengan entri asli, cari permutasi terdekat dari sehubungan dengan -Jarak.
Detail
- Jika lebih nyaman, Anda dapat menggunakan permutasi dari sebagai gantinya. Jika ada beberapa permutasi terdekat, Anda dapat menampilkan salah satu atau semuanya.
- Jarak antara dua vektor didefinisikan sebagai
- Jika mau, Anda dapat mengasumsikan bahwa input hanya terdiri dari bilangan bulat.
Contohnya
[0.5 1] -> [1 2], [2 1]
c*[1 1 ... 1] -> any permutation
[1 4 2 6 2] -> [1 4 3 5 2], [1 4 2 5 3]
[1 3 5 4 1] -> [2 3 5 4 1], [1 3 5 4 2]
[7 7 3 2 5 6 4 2] -> [8 7 3 2 5 6 4 1], [8 7 3 1 5 6 4 2], [7 8 3 2 5 6 4 1], [7 8 3 1 5 6 4 2]
[-2 4 5 7 -1 9 3] -> [1 4 5 6 2 7 3], [2 4 5 6 1 7 3], [1 4 5 7 2 6 3], [2 4 5 7 1 6 3]
[0 4 2 10 -1 10 5] -> [1 4 2 6 3 7 5], [1 4 3 6 2 7 5], [2 4 3 6 1 7 5], [3 4 2 6 1 7 5], [1 4 2 7 3 6 5], [1 4 3 7 2 6 5], [2 4 3 7 1 6 5], [3 4 2 7 1 6 5]
Skrip oktaf untuk menghasilkan lebih banyak contoh.
v
, akan lebih besar dari0
? Atau, setidaknya, bukan0
?v
dapat berupa bilangan bulat apa saja. (Menambahkan beberapa contoh lagi.)[1.6 2]
merupakan kasus uji penting (algoritma serakah / jenis leksikografis memberikan jawaban yang salah).Jawaban:
Python 2 , 60 byte
Cobalah online!
Menggunakan pengindeksan nol.
Algoritma cepat dengan ide sederhana. Jika kita malah perlu mengubah urutan daftar masukan untuk membuatnya sebagai dekat dengan(1,2,...,n) mungkin, kita harus hanya semacam itu, sebagaimana dibuktikan di bawah ini. Karena kita bukan permuting (1,2,...,n) , kita memilih permutasi yang memerintahkan cara yang sama seperti daftar input, seperti dalam tantangan sayaMeniru sebuah memesan(kecuali input mungkin memiliki mengulangi). (Sunting: mil menunjukkantantangan yang lebih identik ini, di mana Dennis memilikijawaban yang sama.)
Perhatikan bahwa satu-satunya milik(1,2,...,n) yang kita digunakan adalah bahwa itu diurutkan, sehingga algoritma yang sama akan bekerja untuk mengubah urutan setiap daftar yang diberikan untuk meminimalkan jarak ke setiap daftar tetap.
Dalam kode, satu-satunya tujuan
z=zip(l,range(len(l)))
adalah untuk membuat elemen input berbeda, yaitu untuk menghindari ikatan, sambil menjaga perbandingan yang sama antara elemen yang tidak sama. Jika input yang kami jamin tidak ada pengulangan, kami bisa menghapus ini dan hanya memilikinyalambda l:map(sorted(l).index,l)
.sumber
05AB1E , 7 byte
Cobalah online!
Penjelasan
sumber
Perl 6 , 44 byte
Cobalah online!
Codeblock anonim yang mengembalikan permutasi minimum pertama dengan 0 pengindeksan.
Penjelasan:
Saya pikir saya mungkin juga bisa menyingkirkan
.sum
dan mengurutkan hanya dengan daftar nilai absolut, tapi saya tidak yakin ini sebenarnya corret, meskipun melewati kasus pengujian saya saat ini.sumber
[0.6 1]
(dengan asumsi kita terindeks 0), di mana jika Anda mengoptimalkan untuk nilai pertama Anda mendapatkan[1,0]
skor 1,4, tetapi jika Anda mengoptimalkan untuk seluruh vektor, 1 lebih berharga di posisi kedua untuk skor 0,6.Jelly , 8 byte
Cobalah online!
sumber
Jelly , 5 byte
Tautan monadik yang menerima daftar angka yang menghasilkan daftar bilangan bulat.
Cobalah online! Atau lihat test-suite .
Bagaimana?
NB
L
(panjang) akan bekerjaJ
sejakœ?
diberikan bilangan bulatn
,, di sebelah kanan secara implisit akan membuat rentang[1..n]
untuk bekerja dengannya, tetapiJ
eksplisit.sumber
Ruby ,
6360 byteCobalah online!
Ada trik matematika di sini yang dapat membantu dalam jawaban lain juga - alih-alih meminimalkan jumlah nilai absolut dari perbedaan, kami memaksimalkan jumlah produk. Mengapa itu berhasil?
Meminimalkan jumlah
(x-y) squared
tidak sama dengan meminimalkan jumlah|x-y|
, tetapi akan selalu memberikan jawaban yang valid, itu hanya memprioritaskan pengurangan perbedaan besar daripada yang kecil sedangkan tantangan yang sebenarnya tidak berbeda antara keduanya.Tapi
(x-y)*(x-y)
=x*x+y*y-2*x*y
. Karena istilah kuadrat akan selalu muncul di suatu tempat dalam jumlah untuk permutasi apa pun, mereka tidak mempengaruhi hasilnya, jadi kami dapat menyederhanakannya-2*x*y
.2
Faktor - faktornya keluar, jadi kita bisa menyederhanakannya-x*y
. Kemudian jika kita mengubah meminimalkan menjadi memaksimalkan, kita dapat menyederhanakannyax*y
.Secara intuitif, ini mirip dengan mengamati bahwa jika Anda mencoba untuk memaksimalkan rekaman persegi menggunakan satu set dinding horizontal dan satu set vertikal, Anda sebaiknya memasangkan dinding yang ukurannya berdekatan satu sama lain untuk menciptakan kamar yang sedekat mungkin dengan kotak.
3*3 + 4*4 = 25
, sementara3*4 + 4*3 = 24
.Sunting: Disimpan tiga byte dengan menghasilkan dan mengevaluasi string format daripada menggunakan zip dan jumlah.
sumber
Gaia , 13 byte
Cobalah online!
sumber
JavaScript (ES6), 61 byte
Berdasarkan wawasan xnor .
Cobalah online!
Berkomentar
JavaScript (ES6),
130128 byteAda
haruspasti cara yang lebih langsung ...Diindeks 0.
Cobalah online! (dengan output 1-diindeks)
Bagaimana?
Fungsi pembantug menghitung semua permutasi dari ( 0 , . . . , N - 1 ) dimana n adalah panjang implisit dari array input a [] .
Untuk setiap permutasihal , kami menghitung:
Kami akhirnya mengembalikan permutasi yang mengarah ke yang terkecilk .
sumber
Bahasa Wolfram (Mathematica) , 14 byte
Cobalah online!
Berdasarkan wawasan xnor .
sumber
Python 2 ,
149126112 byte-23 byte terima kasih kepada Tn. Xcoder
-14 byte terima kasih kepada xnor
Cobalah online!
Menggunakan permutasi (0 ... n-1).
sumber
functools
lagi.reduce
biasanya berlebihan, terutama di sini di mana Anda menambahkan barang. Saya pikir Anda bisa melakukannyasum(abs(p-q)for p,q in zip(x,a))
.tanpa paket permutasi
Python 3 , 238 byte
Cobalah online!
sumber
Bahasa Wolfram (Mathematica) , 57 byte
Cobalah online!
sumber
Japt
-g
, 12 byteCobalah
Untuk 0-diindeks, ganti 2 byte pertama dengan
m,
memetakan array ke indeks sebagai gantinya.sumber
J ,
258 byteCobalah online!
Jawaban yang jauh lebih pendek berdasarkan ide cemerlang xnor.
jawaban asli
J , 25 byte
Cobalah online!
sumber