15
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Do the answers need to support arbitrarily large integers, or is a reasonable upper bound like 2^31-1 suitable? \$\endgroup\$ – AdmBorkBork Dec 9 '15 at 21:05
  • 4
    \$\begingroup\$ The term "sets" is confusing because order matters. I think the term you're looking for is ordered partitions. \$\endgroup\$ – xnor Dec 9 '15 at 21:11
  • 2
    \$\begingroup\$ Although it isn't necessary to change, we usually have a looser output format than this. \$\endgroup\$ – lirtosiast Dec 9 '15 at 21:16
  • \$\begingroup\$ I've changed your wording to allow I/O through function arguments, prompts, and other I/O methods we usually consider acceptable. \$\endgroup\$ – lirtosiast Dec 9 '15 at 21:25
  • \$\begingroup\$ @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. \$\endgroup\$ – cuniculus Dec 9 '15 at 21:33

11 Answers 11

7
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Also 14 bytes, different approach: jjL\,fqsTQ^SQE. \$\endgroup\$ – PurkkaKoodari Dec 10 '15 at 2:22
6
\$\begingroup\$

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)
\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Dyalog APL, 33 bytes

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

Takes m as left argument, n as right argument.

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

\$\endgroup\$
2
\$\begingroup\$

Mathematica, 65 bytes

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

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

\$\endgroup\$
2
\$\begingroup\$

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. :)

\$\endgroup\$
1
\$\begingroup\$

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(" ","")
\$\endgroup\$
  • \$\begingroup\$ You can remove the spaces around >, after replace, and after the comma. \$\endgroup\$ – Alex A. Dec 9 '15 at 21:22
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.