Sementara mencoret-coret angka, saya menemukan permutasi menarik yang dapat Anda hasilkan dari daftar angka. Jika Anda mengulangi permutasi yang sama ini cukup sering, Anda akan selalu berakhir kembali di array asli. Mari kita gunakan daftar berikut ini:
[1, 2, 3, 4, 5]
sebagai contoh
Membalikkan array. Sekarang array kita adalah
[5, 4, 3, 2, 1]
Susun ulang (swap) setiap pasangan. Daftar kami memiliki 2 pasang:,
[5, 4]
dan[3, 2]
. Sayangnya, kami tidak dapat mengelompokkannya1
menjadi pasangan, jadi kami akan membiarkannya sendiri. Setelah bertukar setiap pasangan, array baru adalah:[4, 5, 2, 3, 1]
Ulangi langkah 1 dan 2 sampai kita kembali ke array asli. Berikut adalah 4 langkah selanjutnya:
Step 2: Start: [4, 5, 2, 3, 1] Reversed: [1, 3, 2, 5, 4] Pairs Swapped: [3, 1, 5, 2, 4] Step 3: Start: [3, 1, 5, 2, 4] Reversed: [4, 2, 5, 1, 3] Pairs Swapped: [2, 4, 1, 5, 3] Step 4: Start: [2, 4, 1, 5, 3] Reversed: [3, 5, 1, 4, 2] Pairs Swapped: [5, 3, 4, 1, 2] Step 5: Start: [5, 3, 4, 1, 2] Reversed: [2, 1, 4, 3, 5] Pairs Swapped: [1, 2, 3, 4, 5] # No more steps needed because we are back to the original array
Jika panjang daftar, n ganjil, ia akan selalu mengambil langkah n persis untuk kembali ke array asli. Jika n adalah genap, ia akan selalu mengambil 2 langkah untuk kembali ke array asli, kecuali n adalah 2, dalam hal ini akan mengambil 1 langkah (karena membalik dan bertukar adalah hal yang sama).
Tugas Anda untuk hari ini (jika Anda memilih untuk menerimanya) adalah memvisualisasikan serangkaian langkah ini untuk daftar panjang yang sewenang-wenang. Anda harus menulis sebuah program atau fungsi yang menggunakan satu bilangan bulat positif n sebagai input, dan melakukan serangkaian langkah untuk daftar ini [1, n]
. Anda harus menampilkan setiap langkah perantara di sepanjang jalan, apakah itu berarti mencetak setiap langkah, atau mengembalikan semuanya sebagai daftar langkah. Saya tidak terlalu pilih-pilih tentang format output, asalkan jelas bahwa Anda menghasilkan setiap langkah. Ini berarti (misalnya) salah satu dari ini:
Mengeluarkan setiap langkah sebagai daftar ke STDOUT
Mengembalikan daftar daftar
Mengembalikan daftar representasi string dari setiap langkah
Mengembalikan / mengeluarkan matriks
akan diterima.
Anda juga harus menampilkan array asli, apakah yang datang di akhir atau di awal terserah Anda. (secara teknis, keduanya benar)
Anda harus menangani kasing tepi 2 mengambil 1 langkah bukan 2 , jadi pastikan solusi Anda bekerja dengan input 2 (dan 1 adalah kasing tepi potensial lainnya).
Seperti biasa, ini adalah kode-golf , sehingga celah standar berlaku, dan mencoba membuat solusi Anda lebih pendek daripada yang lain dalam bahasa pilihan Anda (atau bahkan mencoba untuk mengalahkan bahasa lain yang biasanya lebih pendek dari bahasa Anda jika Anda merasa kesal untuk tantangan).
Tes IO
1:
[1]
2:
[1, 2]
3:
[2, 3, 1]
[3, 1, 2]
[1, 2, 3]
4:
[3, 4, 1, 2]
[1, 2, 3, 4]
5:
[4, 5, 2, 3, 1]
[3, 1, 5, 2, 4]
[2, 4, 1, 5, 3]
[5, 3, 4, 1, 2]
[1, 2, 3, 4, 5]
7:
[6, 7, 4, 5, 2, 3, 1]
[3, 1, 5, 2, 7, 4, 6]
[4, 6, 2, 7, 1, 5, 3]
[5, 3, 7, 1, 6, 2, 4]
[2, 4, 1, 6, 3, 7, 5]
[7, 5, 6, 3, 4, 1, 2]
[1, 2, 3, 4, 5, 6, 7]
9:
[8, 9, 6, 7, 4, 5, 2, 3, 1]
[3, 1, 5, 2, 7, 4, 9, 6, 8]
[6, 8, 4, 9, 2, 7, 1, 5, 3]
[5, 3, 7, 1, 9, 2, 8, 4, 6]
[4, 6, 2, 8, 1, 9, 3, 7, 5]
[7, 5, 9, 3, 8, 1, 6, 2, 4]
[2, 4, 1, 6, 3, 8, 5, 9, 7]
[9, 7, 8, 5, 6, 3, 4, 1, 2]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Dan untuk ukuran yang baik, inilah satu test case raksasa:
27:
[26, 27, 24, 25, 22, 23, 20, 21, 18, 19, 16, 17, 14, 15, 12, 13, 10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 1]
[3, 1, 5, 2, 7, 4, 9, 6, 11, 8, 13, 10, 15, 12, 17, 14, 19, 16, 21, 18, 23, 20, 25, 22, 27, 24, 26]
[24, 26, 22, 27, 20, 25, 18, 23, 16, 21, 14, 19, 12, 17, 10, 15, 8, 13, 6, 11, 4, 9, 2, 7, 1, 5, 3]
[5, 3, 7, 1, 9, 2, 11, 4, 13, 6, 15, 8, 17, 10, 19, 12, 21, 14, 23, 16, 25, 18, 27, 20, 26, 22, 24]
[22, 24, 20, 26, 18, 27, 16, 25, 14, 23, 12, 21, 10, 19, 8, 17, 6, 15, 4, 13, 2, 11, 1, 9, 3, 7, 5]
[7, 5, 9, 3, 11, 1, 13, 2, 15, 4, 17, 6, 19, 8, 21, 10, 23, 12, 25, 14, 27, 16, 26, 18, 24, 20, 22]
[20, 22, 18, 24, 16, 26, 14, 27, 12, 25, 10, 23, 8, 21, 6, 19, 4, 17, 2, 15, 1, 13, 3, 11, 5, 9, 7]
[9, 7, 11, 5, 13, 3, 15, 1, 17, 2, 19, 4, 21, 6, 23, 8, 25, 10, 27, 12, 26, 14, 24, 16, 22, 18, 20]
[18, 20, 16, 22, 14, 24, 12, 26, 10, 27, 8, 25, 6, 23, 4, 21, 2, 19, 1, 17, 3, 15, 5, 13, 7, 11, 9]
[11, 9, 13, 7, 15, 5, 17, 3, 19, 1, 21, 2, 23, 4, 25, 6, 27, 8, 26, 10, 24, 12, 22, 14, 20, 16, 18]
[16, 18, 14, 20, 12, 22, 10, 24, 8, 26, 6, 27, 4, 25, 2, 23, 1, 21, 3, 19, 5, 17, 7, 15, 9, 13, 11]
[13, 11, 15, 9, 17, 7, 19, 5, 21, 3, 23, 1, 25, 2, 27, 4, 26, 6, 24, 8, 22, 10, 20, 12, 18, 14, 16]
[14, 16, 12, 18, 10, 20, 8, 22, 6, 24, 4, 26, 2, 27, 1, 25, 3, 23, 5, 21, 7, 19, 9, 17, 11, 15, 13]
[15, 13, 17, 11, 19, 9, 21, 7, 23, 5, 25, 3, 27, 1, 26, 2, 24, 4, 22, 6, 20, 8, 18, 10, 16, 12, 14]
[12, 14, 10, 16, 8, 18, 6, 20, 4, 22, 2, 24, 1, 26, 3, 27, 5, 25, 7, 23, 9, 21, 11, 19, 13, 17, 15]
[17, 15, 19, 13, 21, 11, 23, 9, 25, 7, 27, 5, 26, 3, 24, 1, 22, 2, 20, 4, 18, 6, 16, 8, 14, 10, 12]
[10, 12, 8, 14, 6, 16, 4, 18, 2, 20, 1, 22, 3, 24, 5, 26, 7, 27, 9, 25, 11, 23, 13, 21, 15, 19, 17]
[19, 17, 21, 15, 23, 13, 25, 11, 27, 9, 26, 7, 24, 5, 22, 3, 20, 1, 18, 2, 16, 4, 14, 6, 12, 8, 10]
[8, 10, 6, 12, 4, 14, 2, 16, 1, 18, 3, 20, 5, 22, 7, 24, 9, 26, 11, 27, 13, 25, 15, 23, 17, 21, 19]
[21, 19, 23, 17, 25, 15, 27, 13, 26, 11, 24, 9, 22, 7, 20, 5, 18, 3, 16, 1, 14, 2, 12, 4, 10, 6, 8]
[6, 8, 4, 10, 2, 12, 1, 14, 3, 16, 5, 18, 7, 20, 9, 22, 11, 24, 13, 26, 15, 27, 17, 25, 19, 23, 21]
[23, 21, 25, 19, 27, 17, 26, 15, 24, 13, 22, 11, 20, 9, 18, 7, 16, 5, 14, 3, 12, 1, 10, 2, 8, 4, 6]
[4, 6, 2, 8, 1, 10, 3, 12, 5, 14, 7, 16, 9, 18, 11, 20, 13, 22, 15, 24, 17, 26, 19, 27, 21, 25, 23]
[25, 23, 27, 21, 26, 19, 24, 17, 22, 15, 20, 13, 18, 11, 16, 9, 14, 7, 12, 5, 10, 3, 8, 1, 6, 2, 4]
[2, 4, 1, 6, 3, 8, 5, 10, 7, 12, 9, 14, 11, 16, 13, 18, 15, 20, 17, 22, 19, 24, 21, 26, 23, 27, 25]
[27, 25, 26, 23, 24, 21, 22, 19, 20, 17, 18, 15, 16, 13, 14, 11, 12, 9, 10, 7, 8, 5, 6, 3, 4, 1, 2]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27]
Bersenang-senang bermain golf!
sumber
1 2 3 4 5
tidak1 2 4 3 5
.array[0]
hanya akan ada 1 pada awal dan akhir proses hinggan = 999
. Dari melihat polanya, sepertinya untuk setiap n aneh , elemen pertama1, n-1, 3, n - 3, 5, n - 5, 7...
naik hinggan - 2, 3, n, 1
, yang akan selalu mengambil n langkah. Saya tidak melihat alasan bahwa pola ini akan berubah dengan n yang lebih besar .1, n, 2, n-2, 4, n-4, 6, n-6, 8, n-8, ...
dan mudah untuk menunjukkan dengan induksi bahwa suatu elemen pada posisi genap x bergerak ke nx setelah satu langkah , dan elemen pada posisi ganjil x pindah ke n-x + 2 . Jadi jika n = 2k + 1 , maka setelah langkah 2k -th 1 akan berada pada 2k , dan pada langkah berikutnya di n-2k = 1 .Jawaban:
TI-Basic (83 series),
585754 bytes (104 karakter)Penjelasan
Mengambil input
Ans
(mis., Menulis5:prgmNAME
untuk menggunakan daftar ukuran lima).Membuat tiga daftar tambahan dari ukuran yang diberikan (yang dibuat ulang dari
ᶫB
pada setiap langkah):ᶫB = ᶫC = {1,2,3,4,5,...}
danᶫD = {-1,-1,-2,-2,-3,...}
. Pada setiap langkah, mengurutkanᶫC
danᶫD
dalam urutan menurun, menerapkan permutasi yang samaᶫA
. Dalam kasusᶫC
, membalikkan iniᶫA
, dan dalam kasusᶫD
, swap ini pasangan yang berdekatan karena TI-Basic menggunakan implementasi seleksi semacam benar-benar bodoh untukSortD(
yang menata ulang sebagai banyak unsur yang identik seperti itu mungkin bisa. KetikaᶫA
sama denganᶫB
lagi, kita berhenti.Tidak, serius, algoritma penyortiran bawaan mereka adalah keluhan terbesar kedua saya dengan penerjemah TI-Basic. (Keluhan terbesar saya adalah seberapa banyak loop bersarang memperlambat penerjemah, karena data loop disimpan dalam tumpukan, tetapi tumpukan tumbuh dari ujung yang salah, sehingga kalkulator harus memindahkan seluruh tumpukan setiap kali elemen didorong) atau muncul.) Tapi kali ini, lebih mudah.
-1 byte:
Pause
menyimpan nilai pencetakannyaAns
, yang lebih pendek daripada referensiᶫA
.-3 byte: ambil input
Ans
sumber
Jelly , 10 byte
Cobalah online!
Penjelasan
Catatan
Jika rentang asli perlu di akhir, tambahkan
ṙ1
kode untuk 12 byte.sumber
05AB1E ,
1311 byteCobalah online!
Penjelasan
sumber
JavaScript (ES6),
8985Edit 4 byte disimpan thx @JustinMariner
Menggunakan fakta bahwa ketika ada elemen di tempat yang tepat, semua elemen berada.
Kurang golf
Uji
sumber
for(l=[];n;l[n-1]=n--);
, Coba secara online! .Mathematica, 142 byte
sumber
JavaScript (ES6), 79 byte
Keluarkan daftar untuk setiap langkah.
Perhatikan bahwa kita tidak perlu menginisialisasi array untuk mendapatkan bola bergulir. Jika tidak diinisialisasi (
x
tidak ditentukan), kita dapat menggunakan indeks array (parameteri
) untuk melakukan langkah pertama:Kasus uji:
Tampilkan cuplikan kode
sumber
R,
1099594797462 byteJika fakta bahwa kode melempar peringatan di atas solusi aktual (tidak ada peringatan jika
n
adalah 1, 3 peringatan jikan
genap dann
peringatan jikan
ganjil) bukan merupakan masalah, maka berikut ini berfungsi sama dengan solusi sebelumnya, berkat vektor mendaur ulang:Cobalah online!
Sekali lagi terima kasih kepada @Giuseppe untuk tambahan 12 byte!
Sebelumnya, solusi peringatan-kurang pada 94 byte:
Cobalah online!
Solusi asli pada 109 byte :
Cobalah online!
sumber
print
mengembalikan argumennya sehingga kita dapat memanfaatkannya di sini. Saya tidak berpikir saya pernah melihatencode
sebelumnya; itu cara pengindeksan yang rapi!2
diembed
denganmin(n,2)
?n
alih-alih{}
untuk loop sementara karenan
tidak melakukan apa-apa. :)0:n+2*1:0
sama dengan1+0:n+c(1,-1)
-4 byte.any(print(...) != s)
setara denganany(print(...)-s)
-1 byte. Aaand jika kita dapat membuktikan bahwam[1]==1
hanya pada akhir algoritme, maka kita dapat menjatuhkannyaany
, sehingga kita dapatkanwhile(print(...)-1)
dan kita dapat menghapuss
, sehingga kita mendapatkan 62 byte,n=scan();m=1:n;w=0:n+2*1:0;while(print(m<-rev(m)[w[w<=n]])-1)n
Japt ,
20181512 byteCobalah (
-R
tandai hanya untuk tujuan visualisasi)1 byte disimpan berkat produk ETH.
sumber
w ò mw
bisaò2n)w
Sekam , 9 byte
Cobalah online!
sumber
Ruby ,
64 57 5250 byteCobalah online!
Bagaimana itu bekerja:
Pertama buat rentang, lalu ulangi permutasi x kali: gunakan indeks negatif, tapi balikkan bit terakhir, jadi kita mendapatkan urutan -2, -1, -4, -3 ... jika x genap, ini akan berakhir yah, kalau tidak kita akan menambahkan elemen yang tersisa di akhir. Langkah terakhir: filter keluar array berulang (jadi kami membahas semua kasus: x = 1, x = 2, angka ganjil dan genap)
sumber
Haskell,
7574 byteCobalah online!
g
apakah pasangan bertukar,h
satu langkah (mundur + menyusun ulang),!
berulang kali berlakuh
(dan mengumpulkan hasil antara) sampai pesanan dikembalikan. Catatan:!
ambil parameter tambahan tambahan yang tidak digunakan0
hanya untuk menjadikannya operator infiks. Fungsi utamap
memulai itu.Sunting: Terima kasih kepada @Angs untuk satu byte.
sumber
0!x
alih-alihf x
menyimpan byte - Cobalah secara online!Java 8,
215214 byteSaya mencoba bermain golf menggunakan array yang sebenarnya, bukan List, tetapi keduanya membalik dan bertukar akan memakan terlalu banyak byte .. Mungkin itu dapat digabungkan dalam satu loop (bukan pertama membalikkan, lalu bertukar), tapi saya belum cari tahu ini.
Ini pasti bisa bermain golf lagi.
Penjelasan:
Coba di sini.
sumber
Java (OpenJDK 8) ,
257245243226206205 byteCobalah online!
sumber
n->{java.util.Arrays x=null;int i=0,k,f,a[]=new int[n],t[]=new int[n];for(;i<n;a[i]=t[i]=++i);do{for(f=0;f<n/2;k=t[f],t[f]=t[n+~f],t[n+~f++]=k);for(k=1;k<n;t[k]=t[--k],t[k]=f,k+=3)f=t[k];System.out.println(x.toString(t));}while(!x.equals(a,t));}
( 245 byte ) Ringkasan perubahanjava.util.Arrays x=null;
:;n-f-1
untukn+~f
; menghapus kurung loop; Berubah 2xk-1
untuk--k
(dan juga berubahk+=2
untukk+=3
menetralkan ini.,f
dan menggunakan kembalii
.for(i=0;i<n/2;k=t[i],t[i]=t[n+~i],t[n+~i++]=k);
kefor(i=0;i<n/2;t[i]=t[n+~i],t[n+~i++]=k)k=t[i];
MATL , 17 byte
Cobalah online!
Penjelasan
sumber
Stax , 17 byte
Jalankan dan debug itu
Penjelasan
Terkejut ia bekerja secepat itu, diuji hingga 399 sebelum saya tidak ingin temp browser saya lagi.
sumber
JavaScript (ES6), 122 byte
r.push(a)
dapat digunakan alih-alihr.push(b)
menempatkan permutasi asli di depan.sumber
Haskell , 97 byte
Ini terasa agak lama :(
Cobalah online!
Penjelasan / Tidak Diundang
sumber
Ditumpuk , 42 byte
Cobalah online!
Melakukan transformasi yang diberikan menggunakan
periodsteps
builtin. Namun, bawaan ini mengembalikan semua elemen, yang mencakup rentang input sebagai elemen pertama dan terakhir. Karena itu kami memenggal daftar, mengembalikan semua kecuali elemen pertama.sumber
AWK , 123 byte
Tidak terlalu ketat, tapi ini yang terbaik yang bisa saya lakukan.
Cobalah online!
sumber
Python 2 ,
16515913881 byteCobalah online!
-20 byte terima kasih kepada @ChasBrown . (Sigh, saya membuat seluruh tantangan tentang sintaksis slicing yang diperluas)
Wah! GolfStorm (-57 byte)! Terima kasih kepada Ian Gödel, tsh, dan Jonathan Frech.
sumber
list(reversed(a))
mencobaa[::-1]
.' '*[2-(x<3),x][x%2]
[b,0][b==a]
->b*(a!=b)
.JavaScript, 136 byte
sumber