pengantar
Saya mendefinisikan kelas permutasi gelisah dalam tantangan sebelumnya . Sebagai pengingat, permutasi p dari angka 0 hingga r-1 gelisah, jika untuk setiap entri p [i] kecuali yang pertama, ada beberapa entri sebelumnya p [ik] sedemikian rupa sehingga p [i] == p [ ik] ± 1 . Sebagai fakta yang menyenangkan, saya juga menyatakan bahwa untuk r ≥ 1 , ada persis 2 r-1 permutasi panjang gelisah r . Ini berarti bahwa ada korespondensi satu-ke-satu antara permutasi panjang gelisah r dan vektor biner panjang r-1. Dalam tantangan ini, tugas Anda adalah mengimplementasikan korespondensi seperti itu.
Tugas
Tugas Anda adalah menulis sebuah program atau fungsi yang menggunakan vektor biner dengan panjang 1 ≤ n ≤ 99 , dan menghasilkan permutasi yang gelisah dengan panjang n +1 . Permutasi dapat berbasis 0 dari 1 (tetapi ini harus konsisten), dan input dan output dapat dalam format yang masuk akal. Lebih lanjut, input yang berbeda harus selalu memberikan output yang berbeda; selain itu, Anda bebas untuk mengembalikan permutasi gelisah yang Anda inginkan.
Hitungan byte terendah menang.
Contoh
Permutasi gelisah (berbasis 0) dengan panjang 4 adalah
0 1 2 3
1 0 2 3
1 2 0 3
1 2 3 0
2 1 0 3
2 1 3 0
2 3 1 0
3 2 1 0
dan program Anda harus mengembalikan salah satu dari mereka untuk masing-masing vektor delapan bit dengan panjang 3:
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
sumber
0 1
dan0 0 1
harus memberikan output dengan panjang yang berbeda.Jawaban:
Jelly ,
121110 byteCobalah online! atau menghasilkan semua permutasi dengan panjang 4 .
Bagaimana itu bekerja
sumber
Python 2,
6260 byteTerima kasih kepada @xnor karena bermain golf 2 byte!
Uji di Ideone .
sumber
x=0,
?0,
adalah tuple. Tanpa koma, pemetaan lebih dari x akan gagal.n
untuk melakukan[n*len(x)]
dan mengubah peta ke daftar comp.Python, 54 byte
Gunakan prosedur berikut:
Misalnya,
l=[1,0,1,0]
memberif(l) == [2,1,3,0,4]
Mempertahankan 0 juga akan memberikan hasil yang sama. The
enumerate
kikuk, saya akan melihat apakah hal itu bisa dilakukan dengan lebih baik secara rekursif.sumber
sum
dan mengiris sintaks.JavaScript (ES6),
484745 byteIni ternyata mirip dengan metode @ETHproductions ', kecuali saya sudah mulai dengan langsung menghitung elemen pertama dan kemudian menggunakan vektor biner untuk menentukan apakah setiap digit adalah tinggi baru atau rendah baru. Sunting: Disimpan 1 byte berkat produk @ETH. Disimpan 2 byte dengan memulai dengan nol dan menyesuaikan sesudahnya. Metode saya sebelumnya ternyata mirip dengan metode @ Dennis, tetapi mengambil 54 byte:
sumber
Perl, 33 byte
Termasuk +1 untuk
-p
Berikan vektor sebagai string tanpa spasi di STDIN:
antsy.pl
:sumber
JavaScript (ES6), 52 byte
Uji itu:
Penjelasan
Ini mengambil keuntungan dari fakta bahwa ketika permutasi yang gelisah dibalik, setiap item dapat 1 lebih dari maksimum entri rendah sebelumnya, atau 1 kurang dari minimum entri tinggi sebelumnya. Dengan menunjukkan item yang lebih tinggi sebagai a
0
dan item yang lebih rendah sebagai1
, kita dapat membuat korespondensi satu-ke-satu yang tepat antara permutasi antsy dari panjang n dan vektor biner dengan panjang n - 1 .Yang terbaik yang bisa saya lakukan dengan teknik Dennis adalah
5751 byte:Solusi xnor adalah 56 (disimpan 1 byte berkat @Neil):
sumber
i-i*x
bisa jadii*!x
.Haskell, 40 byte
Solusi Python Dennis golf luar biasa di Haskell dengan
map
danfold
. Ini lebih pendek daripada upaya saya untuk mem-porting konstruksi langsung masuk saya :sumber
Batch, 127 byte
Mengambil input sebagai parameter baris perintah, output dipisahkan oleh garis. (Dimungkinkan untuk dimasukkan sebagai ruang-terpisah pada STDIN tanpa biaya tambahan.)
sumber