Temukan kumpulan jumlah

15

Saya senang membaca situs ini; ini pertanyaan pertamaku. Suntingan dipersilakan.

Diberikan bilangan bulat positif n dan m , hitung semua partisi m yang diurutkan menjadi persis n bagian bilangan bulat positif, dan cetaklah dipisahkan oleh koma dan baris baru. Urutan apa pun baik-baik saja, tetapi setiap partisi harus muncul tepat sekali.

Misalnya, mengingat m = 6 dan n = 2, partisi yang mungkin adalah pasangan bilangan bulat positif yang berjumlah 6:

1,5
2,4
3,3
4,2
5,1

Perhatikan bahwa [1,5] dan [5,1] adalah partisi dengan urutan berbeda. Output harus persis dalam format di atas, dengan baris tambahan opsional. (EDIT: Urutan partisi tidak penting). Input / output melalui standar kode-golf I / O .

Contoh output lain untuk m = 7, n = 3:

1,1,5
1,2,4
2,1,4
1,3,3
2,2,3
3,1,3
1,4,2
2,3,2
3,2,2
4,1,2
1,5,1
2,4,1
3,3,1
4,2,1
5,1,1

Kode terkecil dalam byte setelah 1 minggu menang.

Sekali lagi, harap edit jika perlu.

Tambahan:

@TimmyD bertanya berapa ukuran input integer yang harus didukung oleh program. Tidak ada minimum keras di luar contoh; memang, ukuran output meningkat secara eksponensial, secara kasar dimodelkan oleh: lines = e ^ (0.6282 n - 1.8273).

n | m | lines of output
2 | 1 | 1
4 | 2 | 2
6 | 3 | 6
8 | 4 | 20
10 | 5 | 70
12 | 6 | 252
14 | 7 | 924
16 | 8 | 3432
18 | 9 | 12870
20 | 10 | 48620
22 | 11 | 184756
24 | 12 | 705432
cuniculus
sumber
Apakah jawaban perlu mendukung bilangan bulat besar yang sewenang-wenang, atau apakah batas atas yang wajar seperti 2 ^ 31-1 cocok?
AdmBorkBork
4
Istilah "set" membingungkan karena pesanan penting. Saya pikir istilah yang Anda cari adalah partisi yang dipesan.
xnor
2
Meskipun tidak perlu diubah, kami biasanya memiliki format output yang lebih longgar daripada ini.
lirtosiast
Saya telah mengubah kata-kata Anda untuk memungkinkan I / O melalui argumen fungsi, prompt, dan metode I / O lainnya yang biasanya kami anggap dapat diterima.
lirtosiast
@TimmyD, ukuran output tumbuh lebih eksplosif sehingga tidak praktis untuk mencoba m dan n melewati beberapa ratus, apalagi 2 ^ 31-1.
cuniculus

Jawaban:

7

Pyth, 14 byte

V^SQEIqsNQj\,N

Cobalah online: Peragaan atau Test Suite

Penjelasan:

V^SQEIqsNQj\,N   implicit: Q = first input number
  SQ             create the list [1, 2, ..., Q]
    E            read another number
 ^               cartesian product of the list
                 this creates all tuples of length E using the numbers in SQ
V                for each N in ^:
     IqsNQ          if sum(N) == Q:
          j\,N         join N by "," and print
Jakube
sumber
Juga 14 byte, pendekatan yang berbeda: jjL\,fqsTQ^SQE.
PurkkaKoodari
6

Python 3, 77 byte

def f(n,m,s=''):[f(i,m-1,',%d'%(n-i)+s)for i in range(n)];m|n or print(s[1:])

Fungsi rekursif yang membangun setiap string output dan mencetaknya. Mencoba setiap angka pertama yang mungkin, berulang untuk menemukan solusi dengan jumlah penurunan yang sesuai n, dan satu jumlah yang lebih sedikit m, dan awalan string sdengan nomor itu. Jika jumlah yang diperlukan dan jumlah istilah sama dengan 0, kami telah mencapai sasaran, jadi kami mencetak hasilnya, memotong koma awal. Ini dicentang sebagai m|n0 (Falsey).

79 karakter dengan Python 2:

def f(n,m,s=''):
 if m|n==0:print s[1:]
 for i in range(n):f(i,m-1,','+`n-i`+s)
Tidak
sumber
4

CJam, 22 byte

q~:I,:)m*{:+I=},',f*N*

Cobalah online di penerjemah CJam .

Bagaimana itu bekerja

q~                      Read and evaluate all input. Pushes n and m.
  :I                    Save m in I.
    ,:)                 Turn it into [1 ... I].
       m*               Push all vectors of {1 ... I}^n.
         {    },        Filter; for each vector:
          :+I=            Check if the sum of its elements equals I.
                        Keep the vector if it does.
                ',f*    Join all vectors, separating by commas.
                    N*  Join the array of vectors, separating by linefeeds.
Dennis
sumber
3

Pyth, 20 18 byte

-2 byte oleh @Dennis!

jjL\,fqQlT{s.pM./E

Ini diambil nsebagai input baris pertama, dan msebagai input kedua.

Coba di sini .

lirtosiast
sumber
3

Haskell, 68 byte

n#m=unlines[init$tail$show x|x<-sequence$replicate n[1..m],sum x==m]

Contoh penggunaan:

*Main> putStr $ 2#6
1,5
2,4
3,3
4,2
5,1

Cara kerjanya: sequence $ replicate n listmembuat semua kombinasi nelemen yang ditarik bentuk list. Kami mengambil semua seperti xdari [1..m]mana sumsama m. unlinesdan init$tail$showmenghasilkan format output yang dibutuhkan.

nimi
sumber
3

Dyalog APL , 33 byte

{↑1↓¨,/',',¨⍕¨↑⍺{⍵/⍨⍺=+/¨⍵},⍳⍵/⍺}

Dibawa msebagai argumen kiri, nsebagai argumen kanan.

Hampir setengah (antara {dan ) untuk pemformatan yang diperlukan.

Adm
sumber
2

Mathematica, 65 byte

StringRiffle[Permutations/@#~IntegerPartitions~{#2},"
","
",","]&

IntegerPartitionsmelakukan tugas. Sisanya hanya untuk memesan tupel dan memformat hasilnya.

LegionMammal978
sumber
2

Python 3, 112

from itertools import*
lambda m,n:'\n'.join(','.join(map(str,x))for x in product(range(m),repeat=n)if sum(x)==m)

Saya belum berhasil 1 liner dalam beberapa saat. :)

Morgan Thrapp
sumber
1

Python 2.7, 174 170 152 byte

Jawaban gemuk. Setidaknya itu bisa dibaca :)

import sys,itertools
m=int(sys.argv[1])
for k in itertools.product(range(1,m),repeat=int(sys.argv[2])):
    if sum(k)==m:print str(k)[1:-1].replace(" ","")
Gabriele D'Antona
sumber
Anda dapat menghapus spasi di sekitar >, setelah replace, dan setelah koma.
Alex A.
1

Julia, 105 byte

f(m,n)=for u=∪(reduce(vcat,map(i->collect(permutations(i)),partitions(m,n)))) println("$u"[2:end-1])end

Ini adalah fungsi yang membaca dua argumen integer dan menulis hasilnya ke STDOUT dengan satu baris feed trailing.

Tidak Disatukan:

function f(m::Integer, n::Integer)
    # Get the integer partitions of m of length n
    p = partitions(m, n)

    # Construct an array of all permutations
    c = reduce(vcat, map(i -> collect(permutations(i)), p))

    # Loop over the unique elements
    for u in unique(c)
        # Print the array representation with no brackets
        println("$u"[2:end-1])
    end
end
Alex A.
sumber
0

Perl 6 , 54 byte

Jika outputnya bisa berupa daftar daftar

{[X] (1..$^m)xx$^n .grep: $m==*.sum} # 36 bytes
my &code = {[X] (1..$^m)xx$^n .grep: $m==*.sum}
say .join(',') for code 7,3;

Cara ini saat ini worded saya harus menambahkan joinke dalam lambda.

{say .join(',')for [X] (1..$^m)xx$^n .grep: $m==*.sum} # 54 bytes
{...}( 7,3 );
1,1,5
1,2,4
1,3,3
1,4,2
1,5,1
2,1,4
2,2,3
2,3,2
2,4,1
3,1,3
3,2,2
3,3,1
4,1,2
4,2,1
5,1,1
Brad Gilbert b2gills
sumber