Diberi angka positif n , output semua partisi multiplikasi yang berbeda dari n dalam format apa pun yang nyaman.
Partisi multiplikasi n adalah seperangkat bilangan bulat, semuanya lebih besar dari satu, sehingga produk mereka adalah n . Sebagai contoh, 20 memiliki partisi multiplikasi yang berbeda berikut:
2 * 2 * 5
2 * 10
4 * 5
20
Urutan tidak masalah, begitu 2 * 2 * 5
juga dengan partisi yang sama 2 * 5 * 2
.
Contoh:
1 -> {}
2 -> {2}
4 -> {2, 2}, {4}
20 -> {2, 2, 5}, {2, 10}, {4, 5}, {20}
84 -> {2, 2, 3, 7}, {2, 2, 21}, {2, 14, 3}, {2, 6, 7}, {2, 42}, {4, 3, 7}, {28, 3}, {4, 21}, {6, 14}, {12, 7}, {84}
Jawaban:
Brachylog , 16 byte
Ini adalah fungsi (bukan program lengkap) yang mengambil angka positif sebagai input dan menghasilkan semua partisi multiplikatif darinya. (Saya juga menghindari penggunaan faktorisasi bawaan utama dalam solusi ini, sebagian besar karena saya tidak yakin mereka akan membantu; Saya mungkin akan mencoba solusi yang lebih berat juga pada beberapa titik.)
Cobalah online! (Kode tambahan telah ditambahkan di sekitar fungsi di sini untuk membuatnya menjadi program penuh; jika Anda memberikan fungsi yang ditunjukkan di atas untuk TIO secara langsung, itu akan menjalankan fungsi tetapi tidak mencetak outputnya di mana saja, yang tidak berguna sebagai demonstrasi .)
Program ini benar-benar mengecewakan saya, karena sebagian besar bekerja di sekitar bug di penerjemah Brachylog dan kekurangan dalam spesifikasinya, daripada benar-benar menyelesaikan masalah; tapi penerjemahnya apa adanya. (Bahkan dengan program seperti ini, penerjemah menggunakan lebih banyak memori daripada yang seharusnya secara logis, dan macet karena kehabisan memori, tetapi untungnya pada masalah kecil ia berhasil menghasilkan output yang diinginkan terlebih dahulu.) Dalam sebuah hipotesa "versi sempurna dari Brachylog" Anda bisa menulis
~*.o.:{>1}a,
, yang akan menjadi 4 byte lebih pendek, tapi saya perlu menambahkan kendala tambahan untuk membantu penerjemah sedikit. (Saya tidak terlalu suka Brachylog, dan lebih suka berpegang pada Prolog, tetapi membutuhkan petunjuk serupa untuk membuat program bekerja dan mereka jauh lebih lama untuk menulis. Jadi Brachylog memang begitu.)Penjelasan:
Seperti biasa, program Brachylog adalah serangkaian kendala; secara default, kendala pertama membatasi input terhadap yang tidak dikenal (yang saya sebut A ), batasan kedua membatasi A terhadap kedua yang tidak diketahui B , dan seterusnya hingga kami mencapai output. Beberapa karakter, seperti
{}
, dapat mengubah aliran umum ini, jadi saya menggunakan serangkaian huruf yang berbeda (misalnya X / Y ) untuk mewakili yang tidak dikenal dalam predikat bersarang.Masih belum jelas bagaimana program ini bekerja, jadi mari kita coba sedikit menyederhanakan kendala. C , D , G , H , dan saya semuanya sama (dan sama dengan output). E dan F juga sama (dan sama dengan input). Jadi kendala kita sampai pada ini:
:{1<}a
perlu argumen kirinya memiliki panjang yang terbatas, atau jika penerjemah masuk ke loop tak terbatas).Kebetulan, saya tidak secara eksplisit menentukan bahwa semua elemen output adalah bilangan bulat, sesuatu yang mungkin diperlukan; namun, pemecah kendala Brachylog tidak dapat menangani non-bilangan bulat, sehingga hanya akan menghasilkan solusi yang melibatkan bilangan bulat.
Jelas, "panjang output lebih kecil dari input" akan benar setiap kali output adalah partisi multiplikatif dari input (karena 2 x > x untuk semua x non negatif , yaitu positif 2 x ). Jadi kita bisa mengabaikan batasan itu; hanya ada di sana untuk memberi penerjemah Brachylog strategi kerja untuk mengevaluasi program. Kendala lain (bahwa output diurutkan, bahwa produknya adalah input, dan bahwa elemen-elemennya semuanya lebih besar dari 1) adalah definisi partisi multiplikatif, dan oleh karena itu fungsi ini pada dasarnya hanyalah implementasi langsung dari pertanyaan.
sumber
Brachylog 1, 14 byte
Cobalah online!
Brachylog 2,
1110 byte, tantangan tanggal akhir bahasaCobalah online!
Maltysen menjawab pertanyaan ini dalam 17 byte Pyth, jadi saya menghasilkan solusi Brachylog 16-byte yang berfungsi dengan menerjemahkan spesifikasi pertanyaan ke Brachylog. Ketika saya melakukan itu, Dennis menulis solusi Jelly 15-byte. Jadi saya harus turun ke 14 byte. Ini adalah fungsi yang mengambil input sebagai argumen, dan mengembalikan daftar semua partisi (bukan generator, seperti solusi saya yang lain).
Beberapa waktu setelah saya menulis jawaban ini, Dennis dan saya secara kooperatif mendapatkan solusi Jelly hingga 11 byte. Ternyata ada versi baru dari Brachylog, dengan sintaks terser; itu mengatasi tantangan, jadi tidak benar-benar masuk hitungan, tetapi bisa mengatur total 11-byte terlalu banyak segera setelah dirilis; revisi bahasa selanjutnya (terinspirasi oleh tantangan lain) dapat mencapai 10, seperti yang terlihat di sini. Kedua program itu identik, dengan satu-satunya perbedaan adalah sintaksisnya.
Tidak seperti solusi saya yang lain, yang tidak banyak menggunakan "primitif golf" tetapi lebih menyatakan masalah secara langsung, yang satu ini mengabaikan hampir semua kekuatan kendala Brachylog dan melakukan kesan Jelly yang terbaik sebagai gantinya, menulis rantai kendala yang argumen kiri sudah diketahui (dan dengan demikian kendala hanya bertindak seperti Jelly monad daripada kendala penuh). Karena itu ia menggunakan algoritma yang sama dengan solusi Pyth @ Maltysen, yang mungkin merupakan cara termudah untuk menyelesaikan ini menggunakan primitif golf biasa. (Yang menarik, solusi "sebutkan saja masalah" dalam jawaban saya yang lain akan lebih pendek jika bukan karena bug / kekurangan dalam penerjemah Brachylog, meskipun kurangnya penggunaan golf primitif. Suatu hari saya perlu menulis "Brachylog yang diperbaiki" untuk mendapatkan solusi yang baik untuk masalah seperti ini; sebagai bahasa golf pergi, Brachylog sebenarnya sangat bertele-tele.)
Program ini terdiri dari generator, dan pembungkus di sekitarnya. Pertama, inilah penjelasan generatornya:
Ini hampir menyelesaikan masalah, tetapi kami akhirnya menghasilkan banyak partisi setiap kali. Jadi kita membutuhkan pembungkus untuk menduplikasi solusi:
sumber
Mathematica, 61 byte
Menentukan operator (rekursif) unary
±
yang mengembalikan daftar partisi.sumber
Pyth - 17 byte
Mengambil semua permutasi dari faktorisasi utama, lalu mempartisi masing-masing dan kemudian menghasilkan semua partisi, kemudian hanya mempertahankan partisi yang berbeda.
Test Suite .
sumber
Python 2, 70 byte
Outputs daftar daftar diurutkan. Sebagai contoh
f(20)
adalah[[2, 2, 5], [2, 10], [4, 5], [20]]
.sumber
O(n)
dan membandingkan dengan pesaing Python 2 mungkin lebihO(n^4)
gaya - sementara f (998) mungkin meniup memori atau perangkat keras dapat mati dalam menjalankan waktu sekitar 80 hari dengan algoritma lainnya, yang ini menyatu setelah kira-kira. 7 mili detik di mesin saya untuk menghasilkan hasilnya[[2, 499], [998]]
. IMO masalah bisa lebih bahwa untukN > 998
yangRecursionError: maximum recursion depth exceeded in comparison
berhenti di atas Python 3 kode ... happy golf :-)O(n^4)
bahkan cukup untuk pengiriman Python2 saya: D Mempertimbangkan test case 998, kode saya akan berjalan 9 kali, dan menghitung(n+r-1)! / r! / (n-1)!
jumlah tuple setiap kali, di manar
tumbuh secara linear dari 2, dan n adalah9 - 2
. Tapi hei, setidaknya Anda tidak perlu mengubah batas rekursi ...Jelly ,
141311 byteCobalah online!
Saya cukup yakin solusi Jelly @ Dennis bisa diperbaiki. Sayangnya, saya tidak berhasil mengalahkan rekor Brachylog, tetapi saya berhasil mengikatnya. Memperbarui : Dengan bantuan @Dennis, kini ditingkatkan; Saya kira Jelly mengambil kembali mahkota.
Program ini sangat tidak efisien, memiliki O (2 n 2 kinerja ) (itulah sebabnya test case di atas menunjukkannya untuk input 4). Ini selesai dengan cepat pada 4, sangat lambat pada 5, dan mungkin tidak mungkin dijalankan untuk nomor yang lebih besar.
Menariknya, Brachylog diperbaiki dengan beralih dari solusi yang menggambarkan masalah (yang mana Brachylog pandai) menjadi solusi yang menggunakan algoritma berdasarkan faktor-faktor input (yang pandai Jelly); Sementara itu, solusi Jelly ditingkatkan dengan bergerak menjauh dari nya kekuatan, dan akan kembali ke solusi yang hanya menggambarkan masalah.
Penjelasan:
Karena output
Ḋx
diurutkan, setiap urutan juga harus diurutkan, dan dengan demikian kita tidak perlu mengurutkannya secara individual. Jadi "output yang sama dalam pesanan yang berbeda adalah duplikat" bagian dari masalah, dan "semua nilai dalam output adalah> 1" bagian dari masalah, diselesaikan oleh generasi. Terlepas dari itu, apa yang pada dasarnya kita lakukan di sini adalah "temukan semua daftar yang manaP=³
", yang kami lakukan (dengan cara yang sangat tidak efisien) dengan membuat semua daftar yang dipermasalahkan dan kemudian menyaring daftar yang salah.(Jelas, seseorang perlu menciptakan hibrida Jelly dan Brachylog, ditambah pemecah kendala yang sangat baik , sehingga kita bisa menulis sesuatu di sepanjang baris
{P=³}~
ditambah beberapa kode deduplikasi, dan menyelesaikan program dalam waktu yang jauh lebih pendek. Itu mungkin agak jauh.)sumber
2r
Dapat menjadiḊ
, danP=³$$
dapat menjadiP=¥
.P=¥
tidak berfungsi ketika saya mencobanya di penerjemah, walaupun saya tidak sepenuhnya yakin mengapa (secara logis, itu harus bekerja, dan itu adalah salah satu hal yang saya coba saat menulis posting; Saya hanya mencoba lagi untuk memastikan, pasti tidak melakukan apa yang saya harapkan).Ḋ
tidak, jadi, saya kira ada penghematan satu-byte kami :-)µ
dengan¹
juga, sepertiµ
membuat berbagai mengulangi argumen kiri baru.³
bukan¹
hanya untuk varietas.)JavaScript (ES6),
7467 byteSecara langsung menyelesaikan masalah secara rekursif: untuk setiap bilangan bulat m dari 2 hingga n , kami mengambil masing-masing partisi n / m dengan elemen minimum m (untuk menghindari duplikat partisi) dan menambahkan m . (Untuk setiap m yang tidak membagi n , ini memberikan array kosong, karena tidak ada pengaturan bilangan bulat mengalikan desimal.) Kami mendefinisikan kasus dasar array kosong untuk 1 sehingga untuk menghindari rekursi tak terbatas.
sumber
Python2,
198191172180 byteProgram lengkap. Ini bisa ditingkatkan banyak, jadi saran sangat diterima!
Output dari rentang 1 hingga 31 (inklusif):
sumber
4 -> {2, 2}, {4}
dimaksud, saya tidak melihat output seperti itu di log Anda.int(math.log(n,2))
, yang menyebabkannya. +2 byte dan itu akan berhasil. Terima kasih!math
tetapi sedang menggunakanmath.log
.len(bin(n))-2
lebih pendek dariint(math.log(n,2))
.Jelly , 15 byte
Cobalah online!
sumber
Clojure, 91 byte
Contoh berjalan:
Nilai itu sendiri dikembalikan sebagai angka tunggal (bukan a
list
), yang lain keluar sebagai daftar. Din
bagian akhir dapat diganti dengan[n]
membuatnya menjadi urutan juga, atau(list n)
untuk membuatnya daftar.sumber
Bahasa Wolfram (Mathematica) ,
585652 byteCobalah online!
Diadaptasi dari solusi Mathematica saya untuk Membagi Pembagi Pembagi . Mengembalikan
Sequence
partisi.sumber
J, 35 byte
Berdasarkan solusi terhadap tantangan faktorisasi yang dibatasi waktu.
Versi ini jauh lebih tidak efisien dan berjalan dalam waktu faktorial berdasarkan jumlah faktor prima. Membuat partisi dengan menghasilkan angka faktoradik.
Cobalah online! (Jangan coba nilai besar secara online!)
Penjelasan
sumber
D, 95 byte
Hanya solusi rekursif. In
g(n,r)
,r
adalah partisi sejauh ini, dann
nilai masih tersisa untuk masuk ke faktor. Untuk mendapatkan setiap partisi yang tidak diurutkan hanya sekali, kami mengurutkan faktor-faktor dalamr
urutan yang tidak meningkat. Elemen terakhirr
dimulai pada2
sebagai faktor yang paling tidak mungkin, dan ditimpa olehn
di setiap salinan sebelum setiap operasi output.Untuk
n = 60
, outputnya adalah sebagai berikut:Cobalah online!
sumber
void g(T)(T n,T[]r){for(T i=r[0];i*i<=n;i++)n%i0:r;r.back=n;r.writeln;}g(n,[2])
std.stdio
danstd.range
, input tidak1
boleh mencetak apa pun, tidak[1]
.D, 109 byte
Cobalah online!
sumber