Daftar semua partisi multiplikasi dari n

28

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 * 5juga 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}
orlp
sumber
Urutan OEIS terkait.
Martin Ender
Terkait
miles

Jawaban:

6

Brachylog , 16 byte

>~l:{1<}a.*?,.=o

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.

>       A is smaller than the input
~l      B has length A
  1<    X is 1, Y is larger
:{1<}a  For each element X of B, it corresponds to an element Y of C
.       C, the output, and D are all identical
*       E is the product of D's elements
?       E, the input, and F are all identical
,       There's no constraint between F and G
.       G, the output, and H are all identical
=       H and I are identical, and need to be evaluated early
o       The output can be produced by sorting I

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:

  • A adalah panjang B dan output, dan lebih kecil dari input.
  • B terdiri dari semua 1s, dan tidak terlalu berguna (itu bagian dari program hanya karena dalam penerjemah Brachylog yang ada,:{1<}a perlu argumen kirinya memiliki panjang yang terbatas, atau jika penerjemah masuk ke loop tak terbatas).
  • Output seluruhnya terdiri dari angka-angka lebih besar dari 1 (yaitu lebih besar dari elemen B yang sesuai ).
  • Produk dari elemen-elemen output sama dengan input.
  • Output tidak berubah dengan menyortirnya (yaitu dalam urutan diurutkan).

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
6

Brachylog 1, 14 byte

:{$pp~c:*ao}fd

Cobalah online!

Brachylog 2, 11 10 byte, tantangan tanggal akhir bahasa

{ḋp~c×ᵐo}ᵘ

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

$pp~c:*ao  ḋp~c×ᵐo
$p         ḋ        Prime factor decomposition of the input
  p         p       Generate all permutations
   ~c        ~c     Generate all inverse concatenations (i.e. partitions)
     :*a       ×ᵐ   Take the product of each list element in each partition
        o        o  Sort each partition

Ini hampir menyelesaikan masalah, tetapi kami akhirnya menghasilkan banyak partisi setiap kali. Jadi kita membutuhkan pembungkus untuk menduplikasi solusi:

:{…}fd
:{…}f     Convert generator to list
     d    Remove duplicate elements

{…}ᵘ      Convert generator to list of unique elements

sumber
Mengapa tidak mengedit jawaban Anda?
Downgoat
3
@Downgoat: Dua jawaban menggunakan pendekatan yang sama sekali berbeda; algoritme berbeda, fitur bahasa yang digunakan sebagian besar independen, dan sejenisnya. Tidak masuk akal untuk mengganti yang lebih lama dengan yang baru (dan saya mungkin telah memposting yang baru bahkan jika lebih lama). Posting meta ini menunjukkan bahwa memposting jawaban yang terpisah lebih disukai dalam situasi seperti ini.
1
Saya tidak tahu apakah Anda tahu ini, tetapi Anda dapat mengambil output dengan menetapkan argumen pada TIO menjadi variabel (yaitu huruf besar). Sebagai contoh .
Fatalkan
5

Mathematica, 61 byte

±1={{}}
±n_:=Union@@(Sort/@Append[n/#]/@±#&/@Most@Divisors@n)

Menentukan operator (rekursif) unary ±yang mengembalikan daftar partisi.

Martin Ender
sumber
Bukankah matematika tidak membutuhkan titik koma di akhir?
Pavel
@Pavel no, titik koma hanya menekan output di notebook interaktif. Terima kasih telah menunjukkan ini, btw, saya tidak sengaja meninggalkan tanda titik koma di akhir.
Martin Ender
4

Pyth - 17 byte

Mengambil semua permutasi dari faktorisasi utama, lalu mempartisi masing-masing dan kemudian menghasilkan semua partisi, kemudian hanya mempertahankan partisi yang berbeda.

{mS-*Md1s./M.p+1P

Test Suite .

Maltysen
sumber
4

Python 2, 70 byte

f=lambda n,k=2,l=[]:n/k and(n%k<1)*f(n/k,k,l+[k])+f(n,k+1,l)or 1/n*[l]

Outputs daftar daftar diurutkan. Sebagai contoh f(20)adalah [[2, 2, 5], [2, 10], [4, 5], [20]].

Tidak
sumber
Karena tipe integer bawaan Python tidak memiliki batas, floating point bukanlah solusi yang dapat diterima karena ketidakakuratan akan memecahkan jawaban untuk input yang terlalu besar.
orlp
@ orl Ok, kembali ke Python 2 lalu.
xnor
TL; DR Saya pikir 998 bukan input yang terlalu besar ;-) IMO kode yang benar-benar keren, lebih seperti latensi O(n)dan membandingkan dengan pesaing Python 2 mungkin lebih O(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 untuk N > 998yang RecursionError: maximum recursion depth exceeded in comparisonberhenti di atas Python 3 kode ... happy golf :-)
penggemar
@Dilettant Tidak yakin apakah 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 mana rtumbuh secara linear dari 2, dan n adalah 9 - 2. Tapi hei, setidaknya Anda tidak perlu mengubah batas rekursi ...
Yytsi
@TuukkaX Peringatan: Saya tidak menganalisis kode, hanya membaca sepintas lalu dan membandingkan perkembangan run time di antara dua kandidat untuk beberapa N hingga 41 kemudian berpikir saya hanya melakukan komentar ;-) tumpukan dan rekursi sering kali mudah, tetapi kemudian panggilan untuk seberapa dalam pertanyaan tipe dalam situasi yang tidak menyenangkan ... harap saya ciptakan itu cukup kabur untuk jumlah penelitian yang masuk.
Dilettant
3

Jelly , 14 13 11 byte

Ḋx³ŒPQP=¥Ðf

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

Ḋx³ŒPQP=¥Ðf
Ḋ              List of integers from 2 to the input (apparently undocumented)
 x³            Make a number of copies of each that's equal to the input
   ŒP          Take all (possibly noncontiguous) subsequences of that list (!)
     Q         Remove duplicates
         Ðf    Filter, keeping elements where:
      P=         their product is equal to {the original input, by default}
        ¥      Parse preceding two links as a unit

Karena output Ḋxdiurutkan, 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
Tolong, seseorang menemukan karakter penghematan di sini. Saya suka "perang byte" di mana entri terus mendapatkan satu byte lebih pendek setiap kali. Ada cukup byte yang terbuang pada bagian struktural dari program di sini sehingga sepertinya ini bisa diperbaiki.
1
Heh, aku baru saja akan memposting sesuatu yang sangat mirip. (Harus menyegarkan lebih sering.) 2rDapat menjadi , dan P=³$$dapat menjadi P=¥.
Dennis
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 :-)
1
Tidak memperhatikan detail lainnya. Anda harus mengganti µdengan ¹juga, seperti µmembuat berbagai mengulangi argumen kiri baru.
Dennis
Oh tentu. Jadi sekarang kita ke 11, dengan karakter yang jauh lebih sedikit, yang membuat saya merasa jauh lebih baik. (Saya menggunakan ³bukan ¹hanya untuk varietas.)
2

JavaScript (ES6), 74 67 byte

f=(n,m=2,a=[])=>n>1?m>n?[]:f(n,m+1,a).concat(f(n/m,m,[...a,m])):[a]

for (var i = 1; i < 31; i++) console.log(JSON.stringify(f(i)));

Secara 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.

Produksi ETH
sumber
1

Python2, 198 191 172 180 byte

from itertools import*
n=input()
for i in range(2,len(bin(n))):
 for P in combinations_with_replacement(range(2,n),i):
  if reduce(lambda a,b:a*b,P)==n:print(P)
print[(n,),()][n<2]

Program lengkap. Ini bisa ditingkatkan banyak, jadi saran sangat diterima!

Output dari rentang 1 hingga 31 (inklusif):

(1,)
(2,)
(3,)
(2, 2), (4,)
(5,)
(2, 3), (6,)
(7,)
(2, 4), (2, 2, 2), (8,)
(3, 3), (9,)
(2, 5), (10,)
(11,)
(2, 6), (3, 4), (2, 2, 3), (12,)
(13,)
(2, 7), (14,)
(3, 5), (15,)
(2, 8), (4, 4), (2, 2, 4), (2, 2, 2, 2), (16,)
(17,)
(2, 9), (3, 6), (2, 3, 3), (18,)
(19,)
(2, 10), (4, 5), (2, 2, 5), (20,)
(3, 7), (21,)
(2, 11), (22,)
(23,)
(2, 12), (3, 8), (4, 6), (2, 2, 6), (2, 3, 4), (2, 2, 2, 3), (24,)
(5, 5), (25,)
(2, 13), (26,)
(3, 9), (3, 3, 3), (27,)
(2, 14), (4, 7), (2, 2, 7), (28,)
(29,)
(2, 15), (3, 10), (5, 6), (2, 3, 5), (30,)
(31,)
Yytsi
sumber
Apakah ini berhasil? Ada test case yang 4 -> {2, 2}, {4}dimaksud, saya tidak melihat output seperti itu di log Anda.
Borsunho
@ Borsunho Saat saya memutar kembali versi lama, saya lupa menambahkan +1 int(math.log(n,2)), yang menyebabkannya. +2 byte dan itu akan berhasil. Terima kasih!
Yytsi
Anda belum mengimpor mathtetapi sedang menggunakan math.log.
orlp
@ Atau saya punya ...? Di baris ketiga.
Yytsi
@ TuukkaX Maaf, saya, saya hanya melihat baris paling atas untuk impor, karena mereka hampir selalu ada ... Yang dikatakan, len(bin(n))-2lebih pendek dari int(math.log(n,2)).
orlp
1

Clojure, 91 byte

(defn f[n](conj(set(for[i(range 2 n):when(=(mod n i)0)j(f(/ n i))](sort(flatten[i j]))))n))

Contoh berjalan:

(map f [20 84])
(#{20 (2 2 5) (4 5) (2 10)} #{(7 12) (2 2 3 7) (2 3 14) (2 2 21) (2 6 7) (6 14) (3 4 7) (3 28) (4 21) (2 42) 84})

Nilai itu sendiri dikembalikan sebagai angka tunggal (bukan a list), yang lain keluar sebagai daftar. Di nbagian akhir dapat diganti dengan [n]membuatnya menjadi urutan juga, atau (list n)untuk membuatnya daftar.

NikoNyrh
sumber
0

J, 35 byte

([:~.]<@/:~@(*//.)"$~#\#:i.@!@#)@q:

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

([:~.]<@/:~@(*//.)"$~#\#:i.@!@#)@q:  Input: integer n
                                 q:  Prime factorization
(                              )@    Operate on them
                              #        Length
                            !@         Factorial
                         i.@           Range [0, i)
                     #\                Range [1, i]
                       #:              Mixed based conversion - Creates factoradic values
     ]                                 Get factors
            (    )"$~                  For each factoradic value
               /.                        Partition the factors based on equal
                                         digits in the factoradic value
             */                          Get the product of each block
        /:~@                             Sort it
      <@                                 Box it
 [:~.                                  Deduplicate
mil
sumber
0

D, 95 byte

void g(int n,int[]r){for(int i=r[0];i*i<=n;i++)(n%i)?0:g(n/i,i~r);r.back=n;r.writeln;}g(n,[2]);

Hanya solusi rekursif. In g(n,r), radalah partisi sejauh ini, dan nnilai masih tersisa untuk masuk ke faktor. Untuk mendapatkan setiap partisi yang tidak diurutkan hanya sekali, kami mengurutkan faktor-faktor dalam rurutan yang tidak meningkat. Elemen terakhir rdimulai pada2 sebagai faktor yang paling tidak mungkin, dan ditimpa olehn di setiap salinan sebelum setiap operasi output.

Untuk n = 60, outputnya adalah sebagai berikut:

[3, 2, 2, 5]
[2, 2, 15]
[3, 2, 10]
[5, 2, 6]
[2, 30]
[4, 3, 5]
[3, 20]
[4, 15]
[5, 12]
[6, 10]
[60]

Cobalah online!

Gassa
sumber
Gunakan templat, Gassa, gunakan templat: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])
Zacharý
Bagaimanapun, ini bahkan bukan jawaban yang valid, karena Anda perlu mengimpor std.stdiodan std.range, input tidak 1boleh mencetak apa pun, tidak [1].
Zacharý
0

D, 109 byte

import std.stdio;void g(T)(T n,T[]r=[2]){if(n-1){for(T i=r[0];i*i<=n;i++)n%i?0:g(n/i,i~r);r[$-1]=n;r.write;}}

Cobalah online!

Zacharý
sumber