Tentang Seri
Pertama, Anda dapat memperlakukan ini seperti tantangan golf kode lainnya, dan menjawabnya tanpa khawatir tentang seri sama sekali. Namun, ada papan peringkat di semua tantangan. Anda dapat menemukan papan peringkat bersama dengan beberapa informasi lebih lanjut tentang seri di posting pertama .
Meskipun saya memiliki banyak ide untuk seri ini, tantangan di masa depan belum ditetapkan. Jika Anda memiliki saran, beri tahu saya di pos kotak pasir yang relevan .
Lubang 3: Partisi Integer
Saatnya menambah kesulitan sedikit.
Sebuah partisi dari bilangan bulat positif n
didefinisikan sebagai multiset bilangan bulat positif yang sum untuk n
. Sebagai contoh jika n = 5
, partisi berikut ada:
{1,1,1,1,1}
{2,1,1,1}
{2,2,1}
{3,1,1}
{3,2}
{4,1}
{5}
Perhatikan bahwa ini adalah multiset, jadi tidak ada urutannya {3,1,1}
,, {1,3,1}
dan {1,1,3}
semuanya dianggap identik.
Tugas Anda, diberikan n
, untuk menghasilkan partisi acak n
. Berikut aturan terperinci:
Distribusi partisi yang dihasilkan harus seragam . Artinya, dalam contoh di atas, setiap partisi harus dikembalikan dengan probabilitas 1/7.
Tentu saja, karena keterbatasan teknis PRNG, keseragaman yang sempurna tidak mungkin terjadi. Untuk tujuan menilai keseragaman kiriman Anda, operasi berikut akan dianggap menghasilkan distribusi seragam yang sempurna:
- Memperoleh nomor dari PRNG (pada rentang berapa pun), yang didokumentasikan sebagai (kurang-lebih) seragam.
- Memetakan distribusi seragam pada set angka yang lebih besar ke set yang lebih kecil melalui modulo atau multiplikasi (atau operasi lain yang mendistribusikan nilai secara merata). Set yang lebih besar harus mengandung setidaknya 1024 kali lebih banyak nilai yang mungkin dari set yang lebih kecil.
Karena partisi adalah multiset, Anda dapat mengembalikannya dalam urutan apa pun, dan urutan ini tidak harus konsisten. Namun, untuk tujuan distribusi acak, urutannya diabaikan. Yaitu, dalam contoh di atas
{3,1,1}
,,{1,3,1}
dan{1,1,3}
bersama - sama harus memiliki probabilitas 1/7 untuk dikembalikan.- Algoritme Anda harus memiliki runtime deterministik. Secara khusus, Anda tidak dapat membuat multiset acak dan menolaknya jika tidak dijumlahkan
n
. - Kompleksitas waktu algoritma Anda harus polinomial dalam
n
. Secara khusus, Anda tidak dapat hanya menghasilkan semua partisi dan memilih yang acak (karena jumlah partisi tumbuh secara eksponensial dengann
). Anda dapat berasumsi bahwa PRNG yang Anda gunakan dapat mengembalikan nilai yang didistribusikan secara seragam dalam O (1) per nilai. - Anda tidak boleh menggunakan fungsi bawaan yang menyelesaikan tugas ini.
Anda dapat menulis program atau fungsi lengkap dan mengambil input melalui STDIN atau alternatif terdekat, argumen baris perintah atau argumen fungsi dan menghasilkan output melalui nilai balik atau dengan mencetak ke STDOUT (atau alternatif terdekat).
Anda dapat mengasumsikan bahwa n ≤ 65
(sehingga jumlah partisi kurang dari 21 ). Output mungkin dalam format string atau daftar yang mudah, tidak ambigu.
Jika Anda mengirimkan fungsi, harap pertimbangkan juga untuk menyediakan program uji kecil yang memanggil fungsi beberapa kali dan mencetak hasilnya. Tidak apa-apa jika parameter harus di-tweak dalam kode. Ini agar orang dapat memeriksa bahwa solusinya setidaknya sekitar seragam.
Ini adalah kode golf, jadi pengiriman terpendek (dalam byte) menang. Dan tentu saja, pengiriman terpendek per pengguna juga akan masuk ke papan peringkat keseluruhan seri.
Papan peringkat
Pos pertama dari seri ini menghasilkan papan peringkat.
Untuk memastikan jawaban Anda muncul, mulailah setiap jawaban dengan tajuk utama, menggunakan templat Penurunan harga berikut:
# Language Name, N bytes
di mana N
ukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:
# Ruby, <s>104</s> <s>101</s> 96 bytes
(Bahasa saat ini tidak ditampilkan, tetapi cuplikan memang membutuhkan dan menguraikannya, dan saya dapat menambahkan leaderboard berdasarkan bahasa di masa mendatang.)
sumber
u/\. y
dalam waktu dekat?GolfScript, 90 byte
Demo online
Ini adalah adaptasi dari kode penghitungan partisi saya (yang lebih sederhana) yang alih-alih hanya melacak trek hitungan baik hitungan maupun yang dipilih secara seragam dari salah satu elemen yang dihitung.
Perbandingan keduanya secara berdampingan:
Perbedaan:
~
adalah karena ini adalah program daripada potongan.[1.]
mengganti1
berkorespondensi dengan perubahan apa yang dilacak.{(\{)}%+}%
setiap elemen di partisi itu, dan{1+}%
menambah1
partisi.0
menjadi[0]
(digerakkan ke1,
) sebagai bagian dari perubahan pada apa yang dilacak, tetapi karena itu perlu tetap menjadi array ketika ditambahkan ke yang lain itu membutuhkan ekstra[ ]
.{+}*
menjadi pilihan tertimbang dari partisi, dikombinasikan dengan penjumlahan jumlah mereka.(;`
menghilangkan count dari output dan menempatkan partisi ke dalam format yang bagus.Kerangka uji
Tweak awal 7000 jika Anda ingin menjalankan jumlah percobaan yang berbeda. Perhatikan bahwa ini terlalu lambat untuk demo online.
sumber
Java,
285267 byteIni adalah metode yang sama dengan jawaban TheBestOne, tetapi menggunakan array sederhana alih-alih peta. Selain itu, alih-alih mengembalikan partisi acak sebagai a
List
, partisi tersebut mencetaknya ke konsol.Di bawah ini adalah program pengujian yang menjalankannya 100.000 kali. Sebagai contoh
n=5
, semua set berada dalam 0,64% dari 1/7 sempurna pada putaran terakhir saya.sumber
Math.min
panggilan ke(k<n?k:n)
, Anda dapat pergi lebih jauh dengan membolos itu sepenuhnya dan hanya melakukan dua cek:b<k&b++<n
. Anda juga dapat dengan mudah membuangn>0
bagian dari pengulangan bersyarat (karenan>0&b<n
mengurangi hinggab<n
saatb
dijamin non-negatif).int
deklarasi terpisah juga.CJam,
6456 byteAnda dapat mengujinya dengan skrip ini:
Penjelasan
sumber
Pyth, 64 byte
Menggunakan /programming//a/2163753/4230423 kecuali bahwa a) Tidak ada cache karena Pyth secara otomatis memoize, b) Mencetak masing-masing alih-alih menambahkan daftar, dan c) diterjemahkan ke Pyth.
Saya akan memposting penjelasan tentang ini ketika saya punya waktu, tetapi di sini adalah kode python yang sesuai:
Sunting: Saya akhirnya sempat melakukan penjelasan:
sumber
Oktaf, 200
Tidak Disatukan:
Bangun sebuah matriks persegi di mana setiap sel (m, n) mencerminkan jumlah partisi
m
yang memiliki jumlah terbesarn
, menurut ekstrak Knuth @feersum yang dikutip dengan baik. Sebagai contoh,5,2
beri kami 2 karena ada dua partisi yang valid2,2,1
dan2,1,1,1
.6,3
memberi kita 3 untuk3,1,1,1
,3,2,1
dan3,3
.Kita sekarang dapat secara deterministik menemukan partisi p'th. Di sini, kami menghasilkan
p
sebagai angka acak tetapi Anda dapat sedikit mengubah skrip sehinggap
merupakan parameter:Kami sekarang dapat secara deterministik menunjukkan bahwa setiap hasil semata-mata bergantung pada p:
Dengan demikian, kembali ke aslinya di mana p dihasilkan secara acak, kita dapat yakin bahwa setiap hasil memiliki kemungkinan yang sama besar.
sumber
(2,2,1)
dan(2,1,1,1,1)
(karena dua yang Anda daftarkan memiliki angka lebih besar dari2
).2
. Maksud saya yang terakhir.R, 198 byte
Tidak Disatukan:
Ini mengikuti struktur yang sama dengan solusi hebat @ dcsohl di Octave , dan karenanya juga berdasarkan pada ekstrak Knuth yang diposting oleh @feersum.
Saya akan mengedit ini nanti jika saya dapat menemukan solusi yang lebih kreatif di R. Sementara itu, setiap masukan tentu saja diterima.
sumber
Java, 392 byte
Panggil dengan
a(n)
. MengembalikanList
dariInteger
sBertakuk:
Diadaptasi dari /programming//a/2163753/4230423 dan golf
Bagaimana ini bekerja: Kita dapat menghitung berapa banyak partisi bilangan bulat n ada dalam waktu O ( n 2 ). Sebagai efek samping, ini menghasilkan tabel ukuran O ( n 2 ) yang kemudian dapat kita gunakan untuk menghasilkan partisi k dari n , untuk setiap bilangan bulat k , dalam waktu O ( n ).
Jadi mari total = jumlah partisi. Pilih angka acak k dari 0 hingga total - 1. Hasilkan partisi k .
Seperti biasa , saran dipersilahkan :)
sumber
Python 2, 173 byte
Secara rekursif membuat kamus
d
, dengan kunci yangk
mewakili pasangan(n,m)
dengank=67*n+m
(menggunakan dijaminn<=65
). Entri adalah tuple dari jumlah partisin
menjadim
beberapa bagian, dan partisi acak seperti itu. Hitungan dihitung dengan rumus rekursif (terima kasih kepada feersum karena menunjukkannya)f(n,m) = f(n-1,m-1) + f(n,n-m)
,dan partisi acak diperbarui dengan memilih salah satu dari dua cabangnya dengan probabilitas yang sebanding dengan jumlahnya. Pembaruan dilakukan dengan menambahkan dilakukan dengan menambahkan
1
untuk cabang pertama dan menambah setiap elemen untuk yang kedua.Saya mengalami banyak kesulitan untuk mendapatkan nilai di luar batas
m
dann
untuk memberikan jumlah nol. Pada awalnya, saya menggunakan kamus yang default ke hitungan 0 dan daftar kosong. Di sini, saya menggunakan daftar dan menambahkannya dengan entri default ini sebagai gantinya. Indeks negatif menyebabkan daftar dibaca dari akhir, yang memberikan entri default tidak mendekati akhir seperti yang pernah dicapai, dan sampul hanya menyentuh wilayah di manam>n
.sumber
80386 kode mesin, 105 byte
Hexdump kode:
Sebagai fungsi C:
void random_partition(int n, int result[]);
. Ini mengembalikan hasilnya sebagai daftar angka dalam buffer yang disediakan; itu tidak menandai akhir daftar dengan cara apa pun, tetapi pengguna dapat menemukan akhirnya dengan mengumpulkan angka - daftar berakhir ketika jumlahnya sama dengann
.Cara menggunakan (dalam Visual Studio):
Contoh output (dengan n = 64):
Ini membutuhkan banyak penjelasan ...
Tentu saja saya menggunakan algoritma yang digunakan orang lain juga; tidak ada pilihan dengan persyaratan tentang kompleksitas. Jadi saya tidak perlu menjelaskan algoritme terlalu banyak. Bagaimanapun:
Saya tunjukkan dengan
f(n, m)
jumlah partisin
elemen menggunakan bagian tidak lebih besar darim
. Saya menyimpannya dalam array 2-D (dinyatakan dalam C asf[65][64]
), di mana indeks pertaman
, dan yang keduam-1
. Saya memutuskan bahwa mendukungn=65
terlalu banyak masalah, jadi mengabaikannya ...Berikut adalah kode C yang menghitung tabel ini:
Kode ini memiliki beberapa gaya yang dikaburkan, sehingga dapat dikonversi ke bahasa assembly dengan mudah. Ini menghitung elemen hingga
f(n, n)
, yang merupakan jumlah partisin
elemen. Ketika kode ini selesai, variabel sementarac
berisi nomor yang diperlukan, yang dapat digunakan untuk memilih partisi acak:Kemudian, ini
index
dikonversi ke format yang diperlukan (daftar angka) menggunakan tabel yang dihasilkan.Kode ini juga dioptimalkan untuk konversi ke bahasa assembly. Ada "bug" kecil: jika partisi tidak berisi
1
angka apa pun di akhir, loop terakhir bertemun = 0
, dan menampilkan1
elemen yang tidak dibutuhkan . Tidak ada salahnya, karena kode pencetakan melacak jumlah angka, dan tidak mencetak nomor asing ini.Ketika dikonversi ke perakitan inline, kode ini terlihat seperti ini:
Beberapa hal menyenangkan yang perlu diperhatikan:
rdrand
instruksi)ah
, yang memberi saya perkalian otomatis dengan 256. Untuk mengambil keuntungan dari ini, saya mengorbankan dukungan untukn = 65
. Saya harap saya dapat dimaafkan untuk dosa ini ...Mengalokasikan ruang pada tumpukan dilakukan dengan mengurangi 0x4100 dari register penunjuk tumpukan
esp
. Ini adalah instruksi 6-byte! Saat menambahkan nomor ini kembali, saya berhasil melakukannya dalam 5 byte:Ketika men-debug fungsi ini di MS Visual Studio, saya menemukan bahwa itu crash ketika menulis data ke ruang yang dialokasikan pada tumpukan! Setelah beberapa penggalian di sekitar, saya menemukan semacam perlindungan overrun stack: OS tampaknya hanya mengalokasikan kisaran yang sangat terbatas dari alamat virtual untuk stack; jika suatu fungsi mengakses suatu alamat yang terlalu jauh, OS menganggap itu suatu overrun dan membunuh program. Namun, jika suatu fungsi memiliki banyak variabel lokal, OS melakukan beberapa "sihir" tambahan untuk membuatnya berfungsi. Jadi saya harus memanggil fungsi kosong yang memiliki array besar yang dialokasikan pada stack. Setelah fungsi ini kembali, tumpukan halaman VM dialokasikan dan dapat digunakan.
sumber