# Find the sets of sums

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.

@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

• Do the answers need to support arbitrarily large integers, or is a reasonable upper bound like 2^31-1 suitable? – AdmBorkBork Dec 9 '15 at 21:05
• The term "sets" is confusing because order matters. I think the term you're looking for is ordered partitions. – xnor Dec 9 '15 at 21:11
• Although it isn't necessary to change, we usually have a looser output format than this. – lirtosiast Dec 9 '15 at 21:16
• I've changed your wording to allow I/O through function arguments, prompts, and other I/O methods we usually consider acceptable. – lirtosiast Dec 9 '15 at 21:25
• @TimmyD, the size of the output grows rather explosively so that it's not practical to try m and n past a few hundred, let alone 2^31-1. – cuniculus Dec 9 '15 at 21:33

# 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]
^               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

• Also 14 bytes, different approach: jjL\,fqsTQ^SQE. – PurkkaKoodari Dec 10 '15 at 2:22

## 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)


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


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

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. # Dyalog APL, 33 bytes {↑1↓¨,/',',¨⍕¨↑⍺{⍵/⍨⍺=+/¨⍵},⍳⍵/⍺}  Takes m as left argument, n as right argument. Almost half (between { and ⍺) is for the required formatting. ## Mathematica, 65 bytes StringRiffle[Permutations/@#~IntegerPartitions~{#2}," "," ",","]&  IntegerPartitions does the task. The rest is just to order the tuples and format the result. # 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. :) ## Python 2.7, 174170 152 bytes Fat answer. At least it's readable :) import sys,itertools m=int(sys.argv) for k in itertools.product(range(1,m),repeat=int(sys.argv)): if sum(k)==m:print str(k)[1:-1].replace(" ","")  • You can remove the spaces around >, after replace, and after the comma. – Alex A. Dec 9 '15 at 21:22 # 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  # 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