Pemetaan bijective dari integer ke sejumlah variabel bit

11

Sejumlah variabel bit adalah array 0 atau lebih bit. Jadi [0, 1]adalah sejumlah variabel bit, tetapi begitu juga [].

Tulis fungsi atau program yang, dengan integer nonnegatif mengembalikan sejumlah variabel bit sehingga setiap integer memiliki pemetaan satu-ke-satu (bijektif) dengan array.

Ada jumlah tak terbatas dari pemetaan semacam itu, Anda bebas membuat satu sesuka Anda, tetapi itu harus satu-ke-satu. Pemetaan Anda harus secara konseptual satu-ke-satu untuk bilangan bulat berukuran sewenang-wenang, tetapi tidak apa-apa jika implementasi Anda gagal untuk bilangan bulat besar karena batas numerik jenis dalam bahasa pilihan Anda (misalnya C int).

Sebagai contoh dari apa yang bukan pemetaan satu-ke-satu, hanya daftar digit biner dari bilangan bulat. Dalam sistem seperti 5 menjadi [1, 0, 1](atau 0b101), tetapi itu tidak satu-ke-satu, karena 0b0101atau [0, 1, 0, 1]juga berarti 5.

Seharusnya cukup jelas bahwa pemetaan bukan satu-ke-satu jika ia melewatkan bilangan bulat (misalnya tidak bekerja untuk 5), tapi saya ingin memperjelas bahwa melewatkan array bit variabel juga bukan satu -untuk satu. Anda harus memetakan ke setiap bit array variabel yang mungkin, termasuk [].


Kode terpendek dalam byte menang.

orlp
sumber
Bisakah kita mengembalikan string 0 dan 1?
xnor
@ xnatau Ya, string 0s dan 1s baik-baik saja.
orlp

Jawaban:

4

Jelly, 3 byte

‘BḊ

Gagasan yang sama dengan xnor: maps 0 1 2 3 4 ...to [] [0] [1] [0 0] [0 1] ...; kodenya pada dasarnya increment → binary → remove first.

Cobalah online .

Lynn
sumber
10

Python, 20 byte

lambda n:bin(~n)[4:]

Uji:

>> [bin(~n)[4:] for n in range(16)]
['', '0', '1', '00', '01', '10', '11', '000', '001', '010', '011', '100', '101', '110', '111', '0000']

Melakukan lambda n:bin(n+1)[3:]penambahan input, kemudian mengambil representasi biner dengan simbol pertama dihapus ( [3:]karena awalannya 0badalah dua karakter chars). Karena bilangan positif dimulai dengan 1 dalam biner, ini secara unik memberikan representasi biner.

Satu byte disimpan dengan menggunakan komplemen bit ~nuntuk mendapatkan negasi -(n+1), dan menghilangkan tanda negatif dengan memotong satu simbol lagi.

Tidak
sumber
1
Inverse: lambda s:int('1'+s,2)-1.
orlp
2

Pyth, 5 byte

t.BhQ

Cukup terjemahan jawaban xnor ke Pyth.

Qadalah eval () 'd input (), hmenambahkannya, .Bmengubahnya menjadi string biner, dan tmengambil "tail" (yang merupakan segalanya kecuali karakter pertama).

Gagang pintu
sumber
2

Haskell, 41 38 30 29 byte

l="":[b:x|x<-l,b<-"01"]
(l!!)

Contoh penggunaan: (l!!) 4-> "10".

Dimulai dengan daftar kosong sebagai elemen pertama, berjalan malas melalui daftar dan menambahkan elemen saat ini dengan 0dan dengan 1di depannya.

Edit: @xnatau disimpan 3 11 byte. Terima kasih!

nimi
sumber
Ide yang menarik. Fungsi iterated dapat ditulis[(0:),(1:)]<*>
xnor
@ xnor: Oh, Anda sudah menunjukkan <*>trik sebelumnya, tapi saya lupa. Terima kasih lagi!
nimi
Ooh, Anda dapat menentukan seluruh daftar malas: l=[]:[b:x|x<-l,b<-[0,1]];(l!!).
xnor
@ xnor: Luar biasa! Terima kasih banyak! Oh, beralih ke string menghemat satu byte lagi.
nimi
Saya merasa harus ada cara yang lebih singkat untuk berekspresi [b:x|x<-l,b<-"01"]dengan produk atau concat-map, tetapi ekspresi produk (:)<$>[0,1]<*>lberjalan dengan urutan yang salah, pertama-tama mengawali 0 ke semuanya, tidak pernah sampai ke 1 karena daftarnya tidak terbatas. Apakah Anda punya ide?
xnor
1

JavaScript (ES6), 29 byte

x=>(~x).toString(2).slice(2)

Gagasan yang sama dengan xnor.

f=x=>(~x).toString(2).slice(2);
[...Array(100)].map((v,x)=>A.textContent+=x + ': ' + f(x) + '\n')
<pre id=A></pre>

andlrc
sumber
Ini mudah diperluas ke pangkalan-pangkalan lain sesuai codegolf.stackexchange.com/q/78990
Neil
1

Jolf, 4 byte

Coba di sini!

wBhj
  hj  input + 1
 B    converted to binary
w     with first removed.

Strategi yang sangat sederhana, juga merupakan yang terpendek.

Conor O'Brien
sumber
1

Haskell, 35 byte

h 1=[]
h n=mod n 2:h(div n 2)
h.(+1)

Haskell tidak memiliki biner bawaan, sehingga konversi (terbalik) dilakukan secara manual. Untuk menghapus awal 1, kasing dasar telah 1berubah ke daftar kosong.

Sunting: Disimpan byte dengan konjugasi oleh yang +1bukan.

h 0=[]
h m=1-mod m 2:h(div(m+1)2-1)
Tidak
sumber
1

C, 40 byte

f(n){if(++n/2)putchar(n%2+48),f(n/2-1);}

Mengonversi input ke basis bijective 2 (dengan simbol 0dan 1), seperti jawaban lainnya.

ideone itu!

sebuah kata benda slim kontrak
sumber