Urutkan penyisipan terbalik

19

Objektif

Hasilkan daftar orak asli, dari gerakan yang akan dilakukan Sortasi Sortir untuk mengurutkannya. Daftar asli akan memiliki semua angka dari 0hingga N-1(inklusif) di mana Nukuran input.

Memasukkan

Daftar berisi gerakan yang diperlukan untuk mengurutkan daftar. Setiap nilai mewakili jumlah slot yang dipindahkan oleh nomor asli (diacak) untuk berada di posisi kanannya, perlu diingat bahwa proses ini dari kiri ke kanan.
Nilai pada posisi (0-diindeks)i dalam daftar input akan berada di antara 0dan iinklusif.
Anda tidak perlu menangani input yang tidak valid, perilaku apa pun dapat diterima dalam kasus ini (crash, infinite loop, dll).

Keluaran

Daftar acak

Langkah demi langkah untuk menghasilkan gerakan

Scrambled List | Moves to sort
[4,0,2,1,3,5]  | [0, , , , , ] #4 stay in place
[4,0,2,1,3,5]  | [0,1, , , , ] #0 is moved 1 slot to the left
[0,4,2,1,3,5]  | [0,1,1, , , ] #2 is moved 1 slot
[0,2,4,1,3,5]  | [0,1,1,2, , ] #1 is moved 2 slot
[0,1,2,4,3,5]  | [0,1,1,2,1, ] #3 is moved 1 slot
[0,1,2,3,4,5]  | [0,1,1,2,1,0] #5 is in the right place already
[0,1,2,3,4,5]

Jadi, untuk input, [0,1,1,2,1,0]program Anda perlu meng-output[4,0,2,1,3,5] .
Perlu diingat bahwa pergerakannya tidak ke posisi dalam daftar (akhir) yang diurutkan, tetapi pada segmen yang diurutkan (bagian yang dicetak tebal)

Uji Kasus

[0,0,0] -> [0,1,2]
[0,1,0,1] -> [1,0,3,2]
[0,0,0,0,0,5] -> [1,2,3,4,5,0]
[0,1,2,3] -> [3,2,1,0]
[0,1,1,1] -> [3,0,1,2]
[0,1,1,2,1,0] -> [4,0,2,1,3,5]

Kemenangan

Ini , jadi jawaban terpendek menang.

tongkat
sumber
1
Bisakah program juga mengambil panjang daftar sebagai input?
mbomb007
@ mbomb007 nggak.
Rod
Bisakah kita menggunakan langkah-langkah (n-1) saja? Yang pertama tidak perlu, karena selalu nol.
GB
@ GB yakin, selama outputnya benar, Anda dapat menggunakan algoritma apa pun
Rod

Jawaban:

14

Jelly , 12 byte

L!_UÆ¡$œ?J’U

Cobalah online!

Penjelasan

Kita pada dasarnya dapat melihat dua daftar (input dan output) sebagai pengkodean bilangan bulat; input mengkodekan integer dalam basis faktorial, dan output mengkodekan integer sebagai permutasi. Untungnya, Jelly memiliki builtin yang sudah sangat dekat dengan kedua pengkodean ini, jadi itu hanya masalah menulis potongan kecil kode untuk dikonversi ke integer, lalu kembali ke pengkodean lainnya.

L!_UÆ¡$œ?J’U
   U           Reverse {the input}
    Æ¡         and convert from base factorial to integer;
  _   $        subtract that from
L!             the factorial of the length of {the input};
       œ?      then take the nth permutation of
         J     [1,2,...,l], where l is the length of {the input},
          ’    subtract 1 from every elevent,
           U   and reverse it

Dalam kasus faktorial dasar, kita dapat mengamati bahwa elemen pertama dari daftar harus 0, yang kedua dapat 0 atau 1, yang ketiga harus 0/1/2, dan seterusnya. Jadi, kita harus membalikkan input agar elemen-elemennya menjadi urutan penulisan normal untuk konversi basis.

Selain itu, untuk perintah relatif konversi faktorial dan konversi permutasi agar sesuai dengan operasi yang digunakan penyortiran jenis, kita perlu melakukan dua penyesuaian: membalik urutan permutasi, dan membalik urutan urutan output. Membalikkan daftar output cukup mudah, hanya perlu Udi akhir program. Untuk membalik urutan permutasi, kita kurangi dari faktorial panjang input (ini berfungsi karena faktorial dasar menghasilkan angka dalam kisaran 0 hingga (panjang! -1), sedangkan permutasi diberi nomor oleh Jelly dari 1 hingga panjang! , menghasilkan off-by-one implisit yang membatalkan off-by-one yang biasanya Anda dapatkan ketika mengurangi indeks permutasi dari faktorial).

Jelly , 9 byte, bekerja sama dengan @JonathanAllan

UÆ¡Nœ?J’U

Versi program ini sangat mirip, tetapi menggunakan metode berbeda untuk membalik urutan permutasi; cukup meniadakan input dengan Ncukup untuk membuat œ?memperlakukan pesanan secara terbalik. Selain itu, ia bekerja secara identik dengan program sebelumnya.

Cobalah online!


sumber
4
O_O Apa sihir adalah ini?
DLosc
Oh bagus - Saya tahu atom saya Æ¡dan œ?akan bekerja untuk ini (saya sudah mulai mencoba menggunakannya untuk tantangan ini sebelumnya - saya sangat dekat, hanya perlu L!di sana).
Jonathan Allan
Kode yang sangat baik!
Greg Martin
1
Bahkan, Anda dapat melakukannya dalam 9 byte dengan UÆ¡Nœ?L’Ukarena saya menerapkan œ?(dan serupa) untuk bertindak secara modular (seolah-olah mereka menggunakan daftar Jelly). The Nhanya indeks dengan nilai negatif. Catatan: Saya mengubah Jke L- ini hanya karena diberi nomor itu tetap membuat kisaran di bawah-the-kap).
Jonathan Allan
6

Mathematica, 92 byte

Permute[Range[l=Length@#]-1,(c=Cycles@{#}&)@{}©##&@@c[i-0~Range~#[[i]]]~Table~{i,l,1,-1}]&

Fungsi murni mengambil daftar bilangan bulat negatif sebagai masukan dan mengembalikan daftar bilangan bulat negatif. Kode di atas berisi a ©, yang tidak benar: itu adalah pengganti untuk simbol 3-byte U + F3DE, yang Mathematica wakili oleh lingkaran dengan titik di dalamnya, dan yang mewakili komposisi permutasi.

c=Cycles@{#}&mendefinisikan fungsi yang mengubah daftar bilangan bulat menjadi Cyclesobjek yang mewakili permutasi; misalnya, c[{3,4}]adalah elemen swapping transposisi 3 dan 4 dari daftar. c[i-0~Range~#[[i]]]~Table~{i,l,1,-1}]mengambil daftar input dan menghasilkan permutasi yang diperlukan untuk membatalkan jenis penyisipan. Kemudian c@{}©##&@@menyusun semua permutasi ini bersama-sama, dimulai dengan permutasi identitas c@{}. Akhirnya, Permute[Range[l=Length@#]-1,...]terapkan permutasi ini ke daftar panjang indeks yang diindeks 0.

Greg Martin
sumber
1
Apa yang tidak built-in ?! Tentunya ...
Jonathan Allan
3
@{#}&)@{}©##&@@terlihat menakutkan.
Yytsi
6

Python 2, 79 68 byte

Terima kasih kepada Krazor karena telah menghemat 10 byte

Terima kasih kepada TuukkaX untuk menghemat 1 byte

a=input();b=range(len(a));print[b.pop(j-a[j])for j in b[::-1]][::-1]

Bekerja dengan menghasilkan gerakan secara terbalik

pecandu matematika
sumber
2
Buat itu 66 ! Bagaimana: a=input();b=range(len(a));print[b.pop(j-a[j]) for j in b[::-1]][::-1]. Daftar pemahaman ftw!
FMaz
1
@Krazor Anda memiliki ruang yang bisa dihapus sebelumnya for, jadi buatlah 65 Saya kira: D
Yytsi
@ Krazor Ternyata pemahaman daftar tidak cukup berhasil, tetapi saya menyukai gagasan menggunakan b [:: - 1]!
pecandu matematika
Tidak mungkin? Saya berkomentar dengan ponsel, mungkin saya salah ketik. Bagian mana yang tidak berfungsi? Bagi saya, itu ditafsirkan dengan benar dan memenuhi semua kasus uji.
FMaz
@ Krazor Oh ups, tidak, kau benar. Saya orang yang salah ketik saat pengujian.
pecandu matematika
5

JavaScript (ES6), 69 65 63 byte

a=>a.reverse(b=[...a.keys()]).map(o=>+b.splice(~o,1)).reverse()

Mengganggu input dan output berada dalam urutan yang salah. Sunting: Disimpan 4 byte berkat @Arnauld. Disimpan 2 byte berkat produk @ETH.

Neil
sumber
Saya masih berusaha menemukan cara yang lebih baik tetapi Anda jauh lebih cepat. Yang bagus!
Arnauld
1
Anda tidak perlu i, bukan?
Arnauld
@Arnauld Ternyata tidak. Saya mulai dengan mencoba memahami jawaban Python, dan saya baru saja memperhatikan bahwa itu tidak benar-benar menggunakan i...
Neil
1
Mudah -2:o=>+b.splice(~o,1)
ETHproduksi
3

JavaScript (ES6), 73 71 byte

Disimpan 2 byte berkat produk ETH

m=>(a=m.map((_,i)=>j=i)).map(_=>a.splice(j,0,+a.splice(j-m[j--],1)))&&a

Uji kasus

Arnauld
sumber
Cara yang bagus untuk mendapatkan panjang dan jangkauan pada saat yang sama. Saya akan menyarankan a=m.map(_=>j++,j=0), tapi itu panjang yang sama dan saya yakin Anda sudah mencobanya.
ETHproduksi
@ ETHproductions Anda benar: Saya sudah mencobanya juga. :-) (Mungkin perlu dicatat bahwa ini tidak setara: ini akan jmenjadi a.lengthdaripada a.length-1dan akan membutuhkan a.splice(--j,0,a.splice(j-m[j],1)[0]))
Arnauld
Heh, saya juga memikirkan hal itu, tapi saya pikir itu tidak layak disebut karena panjangnya sama
ETHproduksi
1
Mudah -2:+a.splice(j-m[j--],1)
ETHproduksi
2

Haskell , 85 byte

f x|n<-length x-1=reverse x#[n,n-1..0]
(n:r)#l=r#(take n l++drop(n+1)l)++[l!!n]
x#l=x

Cobalah online! Contoh penggunaan: f [0,1,1,2,1,0]hasil [4,0,2,1,3,5].

f xmemanggil fungsi #dengan daftar xterbalik dan daftar [length x - 1, length x - 2, ... , 0]. (n:r)#lmelakukan penyisipan terbalik dengan mengambil nelemen th secara keluar l, di mana l!!nmenghasilkan nelemen th dan take n l++drop(n+1)lmenghasilkan daftar ldengan nelemen th dihapus.

Laikoni
sumber
Haskell, sangat cantik.
FMaz
1

perl, 61 byte

@o=@p=0..@ARGV-1;splice@o,$_,0,splice@o,$_-pop,1for reverse@p

Output berakhir di array @o. Contoh dengan larik input sebagai argumen baris perintah:

perl -le'@o=@p=0..@ARGV-1;splice@o,$_,0,splice@o,$_-pop,1for reverse@p;print@o' 0 1 1 2 1 0
402135
Kjetil S.
sumber
1

Ruby, 49 byte

->l{(w=l.size).times{l.insert(l.shift+w-=1,w)};l}

Lakukan "penyisipan terbalik" pada tempatnya di dalam daftar, dimulai dengan jumlah terbesar.

GB
sumber