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\$$ 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 modelled 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? Dec 9, 2015 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, 2015 at 21:11
• Although it isn't necessary to change, we usually have a looser output format than this. Dec 9, 2015 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. Dec 9, 2015 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. Dec 9, 2015 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. Dec 10, 2015 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. :) Jelly, 11 bytes ṗS=¥Ƈ⁸j€”,Y  Try it online! Boo to restrictive output formats. +5 bytes because of that. How it works ṗS=¥Ƈ⁸j€”,Y - Main link. Takes m on the left and n on the right ṗ - Take the cartesian power of m and n This returns all lists of length n consisting of the integers 1,...,m ¥Ƈ - Keep those where the following is true: S - Their sum... = - Is equal to... ⁸ - m ”, - Yield "," j€ - Join each sublist by "," Y - Join by newlines  Python 2.7, 174170 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(" ","")  • You can remove the spaces around >, after replace, and after the comma. Dec 9, 2015 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  Husk, 14 bytes moJ',msfo=¹Σπ²  Try it online! with the correct output format. Husk, 7 bytes fo=¹Σπ²  Try it online! Inputs are taken as $$\n,m\$$. Explanation fo=¹Σπ² π cartesian power of n, with range 1..m f filter the terms where Σ sum = equals ¹ m  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