Hasilkan permutasi gelisah

13

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
Zgarb
sumber
Bisakah program mengambil representasi integer dari masing-masing vektor biner?
mbomb007
1
@ mbomb007 Tidak, karena nol di depannya signifikan. 0 1dan 0 0 1harus memberikan output dengan panjang yang berbeda.
Zgarb

Jawaban:

3

Jelly , 12 11 10 byte

ḟẋLṭ+
0;ç/

Cobalah online! atau menghasilkan semua permutasi dengan panjang 4 .

Bagaimana itu bekerja

0;ç/   Main link. Argument: B (bit array)

0;     Prepend a 0 to B.
  ç/   Reduce [0] + B by the helper link.


ḟẋLṭ+  Helper link. Left argument: A (array or 0). Right argument: b (bit)

 ẋ     Repeat A b times, yielding A or [].
ḟ      Filter false; remove the elements of A or [] from A.
  L    Get the length of the resulting array.
       This yield len(A) if b = 0 and 0 if b = 1.
    +  Add b to all elements of A.
   ṭ   Tack; append the result to the left to the result to the right.
Dennis
sumber
3

Python 2, 62 60 byte

x=0,
for n in input():x=[t-n+1for t in x]+[n*len(x)]
print x

Terima kasih kepada @xnor karena bermain golf 2 byte!

Uji di Ideone .

Dennis
sumber
Apakah Anda memerlukan koma x=0,?
ETHproduk
0,adalah tuple. Tanpa koma, pemetaan lebih dari x akan gagal.
Dennis
Saya pikir Anda dapat membalik nuntuk melakukan [n*len(x)]dan mengubah peta ke daftar comp.
xnor
@ xnor Memang. Terima kasih!
Dennis
3

Python, 54 byte

lambda l:[i-i*x+sum(l[i:])for i,x in enumerate([1]+l)]

Gunakan prosedur berikut:

  1. Tambahkan 1 ke daftar.
  2. Untuk setiap entri 0, tulis posisinya di daftar 0-diindeks.
  3. Untuk setiap entri, tulis angka 1 di sebelah kanannya, jangan dihitung sendiri.
  4. Tambahkan hasil langkah 2 dan 3 secara berturut-turut.

Misalnya, l=[1,0,1,0]memberif(l) == [2,1,3,0,4]

List with prepended 1         1 1 0 1 0

0-indexed position for 0's        2   4
Number of 1's to right        2 1 1 0 0
Sum of above two              2 1 3 0 4

Mempertahankan 0 juga akan memberikan hasil yang sama. The enumeratekikuk, saya akan melihat apakah hal itu bisa dilakukan dengan lebih baik secara rekursif.

Tidak
sumber
Teknik pintar! Sangat menarik betapa berbagai teknik terbaik dalam setiap bahasa. Saya mencoba porting ini ke JS, tetapi berakhir pada 57 karena kurangnya sumdan mengiris sintaks.
ETHproduk
3

JavaScript (ES6), 48 47 45 byte

a=>[h=l=0,...a.map(c=>c?--l:++h)].map(e=>e-l)

Ini 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:

a=>a.reduce((r,b)=>[...r.map(e=>b+e),r.length*!b],[0])
Neil
sumber
2

Perl, 33 byte

Termasuk +1 untuk -p

Berikan vektor sebagai string tanpa spasi di STDIN:

antsy.pl <<< 110

antsy.pl:

#!/usr/bin/perl -p
s%^|.%y/0//+($&?++$a:$b--).$"%eg
Ton Hospel
sumber
2

JavaScript (ES6), 52 byte

v=>[...v,l=0].map(x=>x?l++:h--,h=v.length).reverse()

Uji itu:

f=v=>[...v,l=0].map(x=>x?l++:h--,h=v.length).reverse()
g=v=>console.log(f((v.match(/[01]/g)||[]).map(x=>+x)))
<input oninput="g(this.value)" value="010">

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 0dan item yang lebih rendah sebagai 1, 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 57 51 byte:

v=>v.reduce((x,n)=>[...x.map(i=>i+n),!n*++j],[j=0])
v=>v.map(n=>x=[...x.map(i=>i+n),!n*++j],x=[j=0])&&x

Solusi xnor adalah 56 (disimpan 1 byte berkat @Neil):

l=>[1,...l].map((x,i)=>i*!x+eval(l.slice(i).join`+`||0))
Produksi ETH
sumber
i-i*xbisa jadi i*!x.
Neil
@ Neil Ah ya, terima kasih.
ETHproduk
0

Haskell, 40 byte

foldl(\r a->map(+0^a)r++[a*length r])[0]

Solusi Python Dennis golf luar biasa di Haskell dengan mapdan fold. Ini lebih pendek daripada upaya saya untuk mem-porting konstruksi langsung masuk saya :

f l=[i*0^x+sum(drop i l)|(i,x)<-zip[0..]$0:l]
f l=[a+c-b*c|(a,c,b)<-zip3(scanr(+)0l)[0..]$0:l]
Tidak
sumber
0

Batch, 127 byte

@set s=%*
@set/an=h=l=%s: =+%
@for %%b in (%*)do @call:%%b
:0
@echo %n%
@set/an=h+=1
@exit/b
:1
@echo %n%
@set/an=l-=1

Mengambil input sebagai parameter baris perintah, output dipisahkan oleh garis. (Dimungkinkan untuk dimasukkan sebagai ruang-terpisah pada STDIN tanpa biaya tambahan.)

Neil
sumber