Permutasi dalam Penyamaran

17

Dengan vektor n -dimensi v dengan entri asli, cari permutasi p terdekat dari sehubungan dengan(1,2,...,n)l1 -Jarak.

Detail

  • Jika lebih nyaman, Anda dapat menggunakan permutasi dari (0,1,...,n1) sebagai gantinya. Jika ada beberapa permutasi terdekat, Anda dapat menampilkan salah satu atau semuanya.
  • Jarak l1 antara dua vektor u,v didefinisikan sebagai
    d(u,v)=i|uivi|.
  • 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.

cacat
sumber
Apakah kami dijamin bahwa semua elemen v, akan lebih besar dari 0? Atau, setidaknya, bukan 0?
Shaggy
1
Tidak, entri vdapat berupa bilangan bulat apa saja. (Menambahkan beberapa contoh lagi.)
flawr
Jika mereka dapat berupa bilangan real maka [1.6 2]merupakan kasus uji penting (algoritma serakah / jenis leksikografis memberikan jawaban yang salah).
histokrat
2
Gandakan tersamar? Saya tidak yakin itu harus ditutup seperti itu, karena tidak jelas bahwa itu adalah tugas yang sama (seperti yang sekarang dibuktikan oleh xnor).
Arnauld
1
(Sebenarnya, ini bukan tugas yang sama, tetapi semua solusi dari tantangan terkait adalah solusi untuk yang ini.)
Arnauld

Jawaban:

13

Python 2 , 60 byte

def f(l):z=zip(l,range(len(l)));print map(sorted(z).index,z)

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.)

Klaim: Sebuah permutasi dari daftar l yang meminimalkan jarak ke (1,2,...,n) adalahl diurutkan.

Bukti: Perhatikan beberapa permutasi lain l dari l . Kami akan membuktikan itu tidak bisa lebih baik daripada l diurutkan.

Pilih dua indeks i,j yang l memiliki out-of-order, di situlah i<j tetapi li>lj . Kami menunjukkan bahwa swapping mereka tidak dapat meningkatkan jarak ke (1,2,...,n) . Kami perhatikan bahwa swap mengubah kontribusi kedua elemen ini sebagai berikut:

|lii|+|ljj||lij|+|lji|.

Ini cara yang rapi untuk menunjukkan bahwa ini tidak bisa menjadi peningkatan. Pertimbangkan dua orang berjalan di garis bilangan, satu bergerak dari li ke i dan yang lainnya dari lj ke j . Jarak total yang mereka tempuh adalah ekspresi di sebelah kiri. Karena i<j tetapi li>lj , mereka beralih siapa yang lebih tinggi pada garis bilangan, yang berarti mereka harus menyeberang di beberapa titik selama berjalan mereka, sebut saja p . Tetapi ketika mereka mencapai p, mereka kemudian dapat menukar tujuan mereka dan berjalan dengan jarak total yang sama. Dan kemudian, tidak bisa lebih buruk bagi mereka untuk berjalan ke tujuan yang ditukar sejak awal daripada menggunakan p sebagai titik jalan, yang memberikan jarak total di sisi kanan.

Jadi, memilah dua out-of-order elemen dalam l membuat jarak ke (1,2,...,n) lebih kecil atau sama. Mengulangi proses ini pada akhirnya akan mengurutkan l . Jadi, l diurutkan setidaknya sebaik l untuk setiap pilihan l , yang berarti optimal atau terikat untuk optimal.

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 memilikinya lambda l:map(sorted(l).index,l).

Tidak
sumber
wawasan yang cemerlang
Jonah
Anda telah menyederhanakan ini untuk menemukan pemesanan .
mil
@miles Itu sangat lucu, saya benar-benar lupa tentang tantangan itu meskipun saya menulis jawaban, dan Dennis memiliki jawaban Python yang tepat yang saya bantu golf.
xnor
"Bukti visual" itu rapi. Saya mendapat ide yang sama tetapi harus menjelaskan setiap kasus formula itu untuk membuktikannya. Sebagai komentar sampingan, beberapa alternatif untuk mendapatkan peringkat di Python menggunakan perpustakaan pihak ketiga ditunjukkan di posting ini .
Joel
5

05AB1E , 7 byte

āœΣαO}н

Cobalah online!


Penjelasan

ā              # get the numbers 1 to len(input) + 1
 œ             # Permutations of this
  Σ  }         # Sort by ...
   α           # Absolute difference
    O          # Sum these
      н        # And get the first one 
               # implicitly print
Data Kedaluwarsa
sumber
1
Setiap kali saya kagum dengan ini, apa yang tidak bisa dilakukan oleh 05AB1E ?
Pria acak
5
@Therandomguy Tidak ada banyak hal yang tidak dapat dilakukan di 05AB1E, tapi cukup buruk di: tantangan berbasis regex; tantangan berbasis matriks (meskipun ini telah diperbaiki setelah beberapa builtin baru); kurangnya angka imajiner; tantangan terkait tanggal / waktu; dll. Meski keras, itu tetap bisa dilakukan biasanya. Untuk memberikan dua contoh: Hitungan Hari Kerja (pergi ke hari berikutnya, dan hari kerja dilakukan secara manual); Quine mengeluarkan sendiri dalam biner (konversi UTF-8 dilakukan secara manual).
Kevin Cruijssen
@ Grimy harus diperbaiki sekarang :)
Data Kadaluarsa
3

Perl 6 , 44 byte

{permutations(+$_).min((*[]Z-$_)>>.abs.sum)}

Cobalah online!

Codeblock anonim yang mengembalikan permutasi minimum pertama dengan 0 pengindeksan.

Penjelasan:

{                                          }   # Anonymous code block
 permutations(+$_)                             # From the permutations with the same length
                  .min(                   )    # Find the minimum by
                                      .sum       # The sum of
                                >>.abs           # The absolute values of
                       (*[]Z-$_)                 # The zip subtraction with the input

Saya pikir saya mungkin juga bisa menyingkirkan .sumdan mengurutkan hanya dengan daftar nilai absolut, tapi saya tidak yakin ini sebenarnya corret, meskipun melewati kasus pengujian saya saat ini.

Jo King
sumber
1
Itu juga menghancurkan otak saya (atau pertanyaan yang sebagian besar setara dengan "apakah algoritma serakah bekerja untuk ini?"). Contoh tandingan paling sederhana adalah [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.
histokrat
2

Jelly , 5 byte

Œ¿œ?J

Tautan monadik yang menerima daftar angka yang menghasilkan daftar bilangan bulat.

Cobalah online! Atau lihat test-suite .

Bagaimana?

Œ¿œ?J - Link: list of numbers, X
Œ¿    - Index of X in a lexicographically sorted list of
         all permutations of X's items
    J - range of length of X
  œ?  - Permutation at the index given on the left of the
         items given on the right

NB L(panjang) akan bekerja Jsejak œ?diberikan bilangan bulat n,, di sebelah kanan secara implisit akan membuat rentang [1..n]untuk bekerja dengannya, tetapi Jeksplisit.

Jonathan Allan
sumber
2

Ruby , 63 60 byte

->v{[*1..v.size].permutation.max_by{|p|eval [p,0]*'*%p+'%v}}

Cobalah 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) squaredtidak 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. 2Faktor - faktornya keluar, jadi kita bisa menyederhanakannya -x*y. Kemudian jika kita mengubah meminimalkan menjadi memaksimalkan, kita dapat menyederhanakannya x*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.

histokrat
sumber
2
Meminimalkan jumlah (xy) kuadrat tidak sama dengan meminimalkan jumlah | xy |, tetapi itu akan selalu memberikan jawaban yang valid. Mengapa demikian? Apakah tidak aday yang meminimalkan |x-y| tapi tidak (x-y)2?
Joel
1

Gaia , 13 byte

e:l┅f⟪D†Σ⟫∫ₔ(

Cobalah online!

e:		| eval and dup input
l┅f		| push permutations of [1..length(input)]
⟪   ⟫∫ₔ		| iterate over the permutations, sorting with minimum first
 D†Σ		| the sum of the absolute difference of the paired elements
       (	| and select the first (minimum)
Giuseppe
sumber
1

JavaScript (ES6), 61 byte

Berdasarkan wawasan xnor .

a=>[...a].map(g=n=>g[n]=a.sort((a,b)=>a-b).indexOf(n,g[n])+1)

Cobalah online!

Berkomentar

a =>                    // a[] = input array
  [...a]                // create a copy of a[] (unsorted)
  .map(g = n =>         // let g be in a object; for each value n in the copy of a[]:
    g[n] =              //   update g[n]:
      a.sort(           //     sort a[] ...
        (a, b) => a - b //       ... in ascending order
      ).indexOf(        //     and find the position
        n,              //       of n in this sorted array,
        g[n]            //       starting at g[n] (interpreted as 0 if undefined)
      ) + 1             //     add 1
  )                     // end of map()

JavaScript (ES6),  130  128 byte

Ada  harus  pasti cara yang lebih langsung ...

Diindeks 0.

a=>(m=g=(k,p=[])=>1/a[k]?(h=i=>i>k||g(k+1,b=[...p],b.splice(i,0,k),h(-~i)))``:p.map((v,i)=>k+=(v-=a[i])*v)|k>m||(R=p,m=k))(0)&&R

Cobalah online! (dengan output 1-diindeks)

Bagaimana?

Fungsi pembantu g menghitung semua permutasi dari (0,...,n-1)dimana n adalah panjang implisit dari array input Sebuah[].

Untuk setiap permutasi hal, kami menghitung:

k=n-1+saya=0n-1(halsaya-Sebuahsaya)2
Satu-satunya alasan untuk memimpin n-1 adalah bahwa kami menggunakan kembali penghitung internal g untuk menyimpan beberapa byte, tetapi tidak berdampak pada hasil akhir.

Kami akhirnya mengembalikan permutasi yang mengarah ke yang terkecil k.

Arnauld
sumber
1

Python 2 , 149 126 112 byte

-23 byte terima kasih kepada Tn. Xcoder

-14 byte terima kasih kepada xnor

from itertools import*
f=lambda a:min(permutations(range(len(a))),key=lambda x:sum(abs(a-b)for a,b in zip(x,a)))

Cobalah online!

Menggunakan permutasi (0 ... n-1).

Hiatsu
sumber
Anda dapat beralih ke Python 2, sehingga Anda tidak perlu functoolslagi.
Tn. Xcoder
reducebiasanya berlebihan, terutama di sini di mana Anda menambahkan barang. Saya pikir Anda bisa melakukannya sum(abs(p-q)for p,q in zip(x,a)).
xnor
0

tanpa paket permutasi

Python 3 , 238 byte

def p(a,r,l):
 if r==[]:l+=[a];return
 for i in range(len(r)):
  p(a+[r[i]],r[:i]+r[i+1:],l)
def m(l):
 s=(float("inf"),0);q=[];p([],list(range(len(l))),q)
 for t in q:D=sum(abs(e-f)for e,f in zip(l,t));s=(D,t)if D<s[0]else s
 return s[1]

Cobalah online!

David
sumber
0

Japt -g , 12 byte

Êõ á ñÈíaU x

Cobalah

Untuk 0-diindeks, ganti 2 byte pertama dengan m,memetakan array ke indeks sebagai gantinya.

Êõ á ñÈíaU x     :Implicit input of array U
Ê                :Length
 õ               :Range [0,Ê]
   á             :Permutations
     ñÈ          :Sort by
       í U       :  Interleave with U
        a        :  Reduce each pair by absolute difference
           x     :  Reduce resulting array by addition
                 :Implicit output of first sub-array
Shaggy
sumber
0

J , 25 8 byte

#\/:@/:]

Cobalah online!

Jawaban yang jauh lebih pendek berdasarkan ide cemerlang xnor.

jawaban asli

J , 25 byte

(0{]/:1#.|@-"1)i.@!@#A.#\

Cobalah online!

Jonah
sumber