Find the sets of sums

Question

I've enjoyed reading this site; this is my first question. Edits are welcome.

Given positive integers n and m, compute all ordered partitions of m into exactly n parts positive integer parts, and print them delimited by commas and newlines. Any order is fine, but each partition must appear exactly once.

For example, given m=6 and n=2, possible partitions are pairs of positive integers that sum to 6:

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

Note that [1,5] and [5,1] are different ordered partitions. Output should be exactly in the format above, with an optional trailing newline. (EDIT: The exact order of the partitions does not matter). Input/output are via standard code-golf I/O.

Another example output for 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

The smallest code in bytes after 1 week wins.

Again, please edit if necessary.

Addendum:

@TimmyD asked what size of integer input the program has to support. There is no hard minimum beyond the examples; indeed, the output size increases exponentially, roughly modeled by: 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

Answer 1

Pyth, 14 bytes

V^SQEIqsNQj\,N

Try it online: Demonstration or Test Suite

Explanation:

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

Answer 2

Python 3, 77 bytes

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

A recursive function that builds each output string and prints it. Tries every possible first number, recursing down to find a solution with the corresponding decreased sum n, and one fewer summand m, and a string prefix s with that number. If both the required sum and the number of terms are equal 0, we've hit the mark, so we print the result, cutting off the initial comma. This is checked as m|n being 0 (Falsey).

79 chars in 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)

Answer 3

CJam, 22 bytes

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

Try it online in the CJam interpreter.

How it works

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.

Answer 4

Pyth, 20 18 bytes

-2 bytes by @Dennis!

jjL\,fqQlT{s.pM./E

This takes n as the first line of input, and m as the second.

Try it here.

Answer 5

Haskell, 68 bytes

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

Usage example:

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

How it works: sequence $ replicate n list creates all combinations of n elements drawn form list. We take all such x of [1..m] where the sum equals m. unlines and init$tail$show produce the required output format.

Answer 6

Dyalog APL, 33 bytes

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

Takes m as left argument, n as right argument.

Almost half (between { and ⍺) is for the required formatting.

Answer 7

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)

I haven't managed a 1 liner in a while. :)

Answer 8

Mathematica, 65 bytes

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

IntegerPartitions does the task. The rest is just to order the tuples and format the result.

Answer 9

Python 2.7, 174 170 152 bytes

Fat answer. At least it's readable :)

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(" ","")

Answer 10

Julia, 105 bytes

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

This is a function that reads two integer arguments and writes the results to STDOUT with a single trailing line feed.

Ungolfed:

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

Answer 11

Perl 6, 54 bytes

If the output could be a list of lists

{[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;

---

The way it's currently worded I have to add a join into the 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