List all ordered partitions of n

23

2

The challenge is to list all ordered partitions (composition (combinatorics)) of a given positive integer n. These are the lists of numbers from 1 to n whose sum is n. For example, given input n = 4, the result should be:

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

The result can be in any order, but must contain each ordered partition once. This means that for n = 4, [1, 1, 2], [1, 2, 1] and [2, 1, 1] must all be part of the result.

Here's my own JavaScript code which achieves this:

function range(n) {
    for (var range = [], i = 0; i < n; range.push(++i));
    return range;
}

function composition(n) {
    return n < 1 ? [[]] : range(n).map(function(i) {
        return composition(n - i).map(function(j) {
            return [i].concat(j);
        });
    }).reduce(function(a, b) {
        return a.concat(b);
    });
}

Golfed, ES6 (169 167 119 109 105 89 85 bytes):

n=>n?[].concat(...[...Array(n)].map((x,i)=>i+1).map(b=>m(n-b).map(a=>[b,...a]))):[[]]

driima

Posted 2016-09-22T09:01:35.817

Reputation: 451

3

Welcome to the site! You need to specify a winning criterion. Code-golf maybe? Also, does it have to be in that specific order? If so, how is the order defined in general? I think lexicographical order would be more meaningful; or better yet, allow any order. You may want to use the sandbox for future challenges before posting them here

– Luis Mendo – 2016-09-22T09:08:51.123

This is not strictly a duplicate since this one requires to output all lists, even those that are the same up to the ordering, whereas the previous one requires that only one of those is printed. – Fatalize – 2016-09-22T09:14:07.727

3@Fatalize Here [2 1 1] is different from [1 2 1], unlike there. I suspect the approaches may be significantly different – Luis Mendo – 2016-09-22T09:14:10.343

3To those who closed as dupe: are you sure the difference indicated in comments is not relevant? I'm not voting to reopen, as I think the hammer would work in that direction too – Luis Mendo – 2016-09-22T09:30:20.820

3I'd suggest not accepting an answer yet (even though you can change it at any time) because seeing the question accepted on the front page might make people think it's over and not participate. – xnor – 2016-09-22T09:50:35.613

5

The usual term for these ordered partitions is "compositions".

– Greg Martin – 2016-09-22T17:54:27.873

2Some languages might be well-suited to the following "stars and bars" algorithm: starting with a string of n 1s, there are n-1 possible places to insert a separator character such as _, and thus 2^(n-1) possible choices of separator insertions. These correspond to the 2^(n-1) compositions of n. For example, the eight compositions of 4 in the OP correspond to the eight strings 1111, 1_111, 111_1, 11_11, 11_1_1, 1_11_1, 1_1_11, and 1_1_1_1. – Greg Martin – 2016-09-22T18:31:27.633

Answers

7

Pyth, 7 6 bytes

7 byte solution:

Pyth has an integer partition builtin ./, so 5 of the 7 bytes is getting the orderings.

{s.pM./

Try it online!

Explanation:

     ./  Integer partition (sorted by default)
  .pM    get all the orderings of each of the partitions as a nested list of lists of orderings
 s       Flatten by one layer
{        Remove duplicates

6 byte solution:

If you have a list, ./ will compute with orderings; all that remains is to make the lists numbers again.

lMM./m

Try it online!

Explanation:

     m  Get lists by gathering a list of [0, 1,...input] (I could use U as well)

   ./   Partition with orderings
 MM     Map an operation across each of the orderings lists of elements
l       where that operation is the length of the sublists

Steven H.

Posted 2016-09-22T09:01:35.817

Reputation: 2 841

Amazing. This is the smallest one I've seen so far! – driima – 2016-09-22T12:38:03.853

11

Haskell, 37 bytes

f 0=[[]]
f n=[a:x|a<-[1..n],x<-f$n-a]

xnor saved two bytes.

Lynn

Posted 2016-09-22T09:01:35.817

Reputation: 55 648

1It looks like the more straightforward f n=[a:x|a<-[1..n],x<-f$n-a] is shorter. – xnor – 2016-09-22T10:06:00.633

you don't need the zero check (given positive integer n ... numbers from 1 to n) – nyro_0 – 2016-09-22T10:16:11.583

2f 0=[[]] just happens to be a shorter base case than f 1=[[1]] :) – Lynn – 2016-09-22T11:14:31.650

@xyLe_ It's used a recursive base case. – xnor – 2016-09-22T17:13:52.970

ah sure, you are right, my bad – nyro_0 – 2016-09-23T05:41:11.290

10

Python, 56 bytes

f=lambda n:[x+[n-i]for i in range(n)for x in f(i)]or[[]]

A recursive solution: The ordered partitions of n are a partition of some smaller i with 0<=i<n, followed by the remainder n-i as the last element. For a base case, n=0 only has the empty partition.

xnor

Posted 2016-09-22T09:01:35.817

Reputation: 115 687

Simple, small and yet still amazingly readable. That's what I love about Python. – driima – 2016-09-26T07:28:33.763

10

Python 2, 61 bytes

f=lambda n,s='1,':1/n*[eval(s)]or f(n-1,'1+'+s)+f(n-1,'1,'+s)

This isn't the shortest, but I really like the method because it's so weird.

Recursively generates and evaluates 2**(n-1) strings, like

1+1+1+1,
1,1+1+1,
1+1,1+1,
1,1,1+1,
1+1+1,1,
1,1+1,1,
1+1,1,1,
1,1,1,1,

for n=4. These strings evaluate to tuples representing all the partitions. Between any two 1's is either a +, joining them into a single number, or a ,, splitting adjacent sections.

xnor

Posted 2016-09-22T09:01:35.817

Reputation: 115 687

Best non-recursive version I could do was import re lambda n:map(lambda n:map(len,re.finall('10*',bin(n))),range(1<<n-1,1<<n)) – Neil – 2016-09-22T13:08:55.743

1An explanation with the code would really make it beautiful. – noman pouigt – 2016-09-22T16:14:47.803

8

JavaScript (Firefox 30-57), 63 bytes

f=n=>n?[for(i of Array(n).keys())for(a of f(i))[n-i,...a]]:[[]]

Neil

Posted 2016-09-22T09:01:35.817

Reputation: 95 035

12Firefox 30+ sounds like a special browser for the more mature users of the internet. – Martin Ender – 2016-09-22T10:08:46.163

Probably doesn't get shorter than this... – ETHproductions – 2016-09-22T14:08:26.440

Any way this can be ungolfed for JavaScript in other browsers? – driima – 2016-09-22T14:10:40.443

@Eternity I can port @xnor's other answer for you: f=n=>n<2?[[1]]:f(n-1).map(([n,...a])=>r.push([1+n,...a],[1,n,...a]),r=[])&&r. – Neil – 2016-09-22T17:34:54.547

6

Mathematica, 40 bytes

Join@@Permutations/@IntegerPartitions@#&

Mathematica's built-in for integer partitions doesn't give all ordered partitions, so we have to generate all possible permutations of each of them, and then flatten the result.

Martin Ender

Posted 2016-09-22T09:01:35.817

Reputation: 184 808

6

CJam, 17 14 bytes

ri"X)"m*{~]p}/

Try it online!

Explanation

I know I said that using the Cartesian product is longer, but I ended up finding a way to use it more efficiently. I think that both approaches are interesting in their own right, so I'm putting them in separate posts.

This is still based on the idea that, we can choose n times between appending a 1 to the current partition or to increment the last element of the current partition. In this solution, we do this by generating 2n-1 different programs which correspond to these different choices.

ri      e# Read input and convert to integer N.
        e# Decrement.
"X)"m*  e# Get all strings of length N which consist of 'X' and ')'. If
        e# we treat these strings as CJam code then 'X' pushes a 1 and ')'
        e# increments the top of the stack.
        e# Note that some of these strings will begin with an increment that
        e# doesn't have anything on the stack to work with. This will result in
        e# an error and terminate the program. Luckily, the programs are ordered
        e# such that all programs starting with 'X' are first in the list, so
        e# we get to print all the 2^(N-1) permutations before erroring out.
{       e# For each of these programs (well for the first half of them)...
  ~     e#   Evaluate the string as CJam code. This leaves the partition as
        e#   individual integers on the stack.
  ]p    e#   Wrap the stack in a list and pretty-print it.
}/

Martin Ender

Posted 2016-09-22T09:01:35.817

Reputation: 184 808

I looked at this and thought "That can't be right, it would give an error when it evaluates the first string which starts with )". So I added ed and tested. +1 for creative abuse of error. – Peter Taylor – 2016-09-22T20:51:31.070

6

Jelly, 7 6 bytes

-1 byte thanks to @Dennis (convert from unary ḅ1, rather than sum for each for each S€€)

1ẋŒṖḅ1

TryItOnline

How?

1ẋŒṖḅ1 - Main link: n          e.g. 4
1ẋ     - repeat 1 n times          [1,1,1,1]
  ŒṖ   - partitions of a list     [[[1],[1],[1],[1]], [[1],[1],[1,1]], [[1],[1,1],[1]],
                                   [[1],[1,1,1]],     [[1,1],[1],[1]], [[1,1],[1,1]],
                                   [[1,1,1],[1]],     [[1,1,1,1]]]
    ḅ1 - from base 1 (vectorises)  [[1,1,1,1],        [1,1,2],         [1,2,1],
                                   [1,3],             [2,1,1],         [2,2],
                                   [3,1],             [4]]

Jonathan Allan

Posted 2016-09-22T09:01:35.817

Reputation: 67 804

5

Pure Bash, 51

This is a port of @xnor's brilliant answer, using multiple levels of bash expansions to achieve the desired result:

a=$[10**($1-1)]
eval echo \$[${a//0/{+,']\ $[}1'}],

Ideone.

  • The first line is simply an arithmetic expansion to create a variable $a containing 1 followed by n-1 zeros.
  • The first expansion ${a//0/{+,']\ $[}1'} replaces each 0 in $a with copies of the string {+,']\ $[}1'. Thus n=4 we get the string 1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1'
  • This is prefixed with $[ and postfixed with ], to give $[1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1]
  • This is a brace expansion that expands to $[1+1+1+1], $[1+1+1] 1, $[1+1] $[1+1], $[1+1] 1 1,...
  • This is finally arithmetically expanded to give the required result.

Careful use of quotes, backslash escaping and eval ensures that the expansions occur in the correct order.

Digital Trauma

Posted 2016-09-22T09:01:35.817

Reputation: 64 644

4

Ruby, 61 bytes

f=->n{n<1?[[]]:(1..n).map{|i|f[n-i].map{|x|x<<i}}.flatten(1)}

ungolfed

f=->n{
  n < 1 ?
    [[]]
  :
    (1..n).map { |i|
      f[n-i].map { |x|
        x << i
      }
    }.flatten(1)
}

usage

p f[4]
# => [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]

cia_rana

Posted 2016-09-22T09:01:35.817

Reputation: 441

2Hiya! Could you add a little bit of explanation for people (like me) who aren't familiar with Ruby? – AdmBorkBork – 2016-09-22T12:58:06.620

x<<i is shorter than [i]+x. – m-chrzan – 2016-09-22T16:34:32.823

@TimmyD I added an ungolfed code and the usage. – cia_rana – 2016-09-22T16:40:44.983

@ m-chrzan Thanks for your advice! I edited that. – cia_rana – 2016-09-22T16:43:01.303

Any reason .flatten(1) isn't .flatten 1 ? – Cyoce – 2016-09-23T01:09:09.903

@Cyoce If we use .flatten 1, but .flatten(1), syntax error occurs, doesn't it? – cia_rana – 2016-09-23T11:24:36.500

@cia_rana that's weird. Not sure why that's invalid syntax. – Cyoce – 2016-09-23T15:01:58.893

@Cyoce Probably something to do with the ternary condition. Ruby's ternary parsing has given a lot of trouble in the past. – Sherlock9 – 2016-09-24T03:58:33.920

3

05AB1E, 14 12 bytes

Saved 2 bytes thanks to Adnan

>G¹LNãvyO¹Q—

Explanation

>G              # for N in range(1..input)
  ¹L            # range(1, input)
    Nã          # cartesian product with N (all combinations of length N)
      v         # for each resulting list
       yO¹Q—    # if it's sum equals the input print it

Try it online!

The corresponding solution is 2 bytes shorter in 2sable.

2sable, 10 bytes

>GLNãvyOQ—

Try it online!

Emigna

Posted 2016-09-22T09:01:35.817

Reputation: 50 798

You can use instead of iy, :). – Adnan – 2016-09-22T15:08:26.953

@Adnan: Thanks! Forgot about that one. – Emigna – 2016-09-22T15:49:29.990

3

Brachylog, 20 bytes

~lL#++?,L:=f:{:0x}ad

Try it online!

Explanation

This is a situation where you would think declarative languages would do well, but because of the overloading of + and the difficutly in writing a summing predicate which propagates constraints properly, they do not.

~lL                     L is a list of length Input
  L#+                   L is a list of non-negative integers
  L  +?,                The sum of the elements of L results in the Input
        L:=f            Find all values for the elements of L which satisfy those constraints
            :{:0x}a     Remove all 0s from each sublist of the result of Findall
                   d    Remove all duplicate sublists

Fatalize

Posted 2016-09-22T09:01:35.817

Reputation: 32 976

I think this would propagate a lot faster if you focus on positive integers, and let the length of L be between 1 and input. – mat – 2016-09-22T14:55:11.373

@mat This is what I originally did but this is longer. Since + also works on a single integer, I need to force . to be a list with ##, and since + also works on list of lists, I need to impose that the elements of . are integers with :#$a.

– Fatalize – 2016-09-22T15:06:19.347

So the key issue is the defaultyness of the data structures: When a variable appears as arguments of operations that vectorize, you cannot tell whether the variable stands for a single integer or a (possibly nested) list. This is a tough issue, and there may be an elegant way to solve this, starting from your original version and searching for suitable language constructs that could simplify this. Nice work in any case! – mat – 2016-09-22T15:21:10.170

3

CJam, 19 bytes

Lari{_1af.+1@f+|}*p

Try it online!

Explanation

CJam doesn't have a useful combinatorics built-in for integer partitions. So we'll do this manually. To find all the ordered partitions of an integer n, we can look at a list of n ones and consider every possible way to insert separators. Then we'll sum the 1s in each section. Example for n = 3:

1 1 1 => 3
1 1|1 => 2|1
1|1 1 => 1|2
1|1|1 => 1|1|1

I tried using a Cartesian product to generate all of these separators, but that ended up at 21 bytes. Instead I went back to this old technique for generating power sets (this is based on an old answer of Dennis's but I can't find it right now). The idea is this: to generate all partitions we can start from an empty list. Then n times we can make a binary decision: either we append a 1 (corresponds to a separator in the above example) or we increment the last value of the list (corresponds to not having a separator). To generate all partitions, we simply perform both operations at each step and keep all possible outputs for the next step. It turns out that in CJam, prepending and incrementing the first element is shorter, but the principle remains the same:

La       e# Push [[]] onto the stack. The outer list will be the list of
         e# all possible partitions at the current iteration, and we initialise
         e# it to one empty partition (basically all partitions of 0).
ri       e# Read input and convert to integer N.
{        e# Repeat this N times...
  _      e#   Duplicate the list of partitions of i-1.
  1af.+  e#   Increment the first element in each of these. This is done
         e#   by performing a pairwise addition between the partition and [1].
         e#   There is the catch that in the first iteration this will turn
         e#   the empty array into [1], so it's equivalent to the next step.
  1@f+   e#   Pull up the other copy of the list of partitions of i-1 and
         e#   prepend a 1 to each of them.
  |      e#   Set union. This gets rid of the duplicate result from the first
         e#   iteration (in all other iterations this is equivalent to concatenating
         e#   the two lists).
         e#   Voilà, a list of all partitions of i.
}*
p        e# Pretty-print the result.

Martin Ender

Posted 2016-09-22T09:01:35.817

Reputation: 184 808

3

Julia, 113 Bytes

f(N)=unique(reduce(vcat,(map(x->[permutations(x)...],[vcat([1 for _=i+1:N],sum([1 for _=N-i:N-1])) for i=1:N]))))

Non-recursive solution

Explained:

  1. [vcat([1 for _=i+1:N],sum([1 for _=N-i:N-1])) for i=1:N] build a set of lists that sum to N, whose permutations will resemble the solution (e.g. for N=4: [[1,1,1,1],[1,1,2],[1,3],[4]])
  2. map(x->[permutations(x)...],) Calculate all permutations
  3. reduce(vcat,) combine them into a list of lists
  4. unique() filter duplicates

nyro_0

Posted 2016-09-22T09:01:35.817

Reputation: 281

We require submissions to be full programs or functions, so in this case you'll have to take N as input. You can make a lambda function by prepending N-> at the cost of 3 bytes. – Alex A. – 2016-09-22T19:46:06.190

@AlexA. ah, sorry the f(N)= got lost at copying, I've had it in when counting bytes – nyro_0 – 2016-09-23T05:43:28.257

3

T-SQL, 203 bytes

Golfed:

USE master
DECLARE @ INT=12

;WITH z as( SELECT top(@)cast(number+1as varchar(max))a FROM spt_values WHERE'P'=type),c as(SELECT a*1a,a b FROM z UNION ALL SELECT c.a+z.a,b+','+z.a FROM c,z WHERE c.a+z.a*1<=@)SELECT b FROM c WHERE a=@

Ungolfed:

USE master --needed to make sure it is executed from the correct database
DECLARE @ INT=12

;WITH z as
(
  SELECT top(@)cast(number+1as varchar(max))a
  FROM spt_values
  WHERE'P'=type
),c as
(
  SELECT a*1a,a b
  FROM z
  UNION ALL
  SELECT c.a+z.a,b+','+z.a
  FROM c,z
  WHERE c.a+z.a*1<=@
)
SELECT b 
FROM c
WHERE a=@

Fiddle

t-clausen.dk

Posted 2016-09-22T09:01:35.817

Reputation: 2 874

3

Mathematica 10.0, 44 bytes

An attempt without using partition-related builtins. From each ordered partition of size k, two successor partitions of k + 1 are generated: one by prepending 1, and the other by incrementing the first value.

Nest[##&[{1,##},{#+1,##2}]&@@@#&,{{1}},#-1]&

A funnier, but sadly 2 bytes longer way of implementing the same idea:

#@{1}&/@Tuples[Prepend[1]@*MapAt[#+1&,1],#-1]&

feersum

Posted 2016-09-22T09:01:35.817

Reputation: 29 566

@alephalpha No, that wouldn't help as then I'd have to change the MapAt index to -1. – feersum – 2016-09-23T12:04:53.677

3

Haskell, 41 bytes

f 1=[[1]]
f n=do a:b<-f$n-1;[1:a:b,a+1:b]

Not the shortest Haskell solution, but I like that it doesn't use [..] ranges. Instead, it recursively computes the partitions of n as the partitions of n-1 with either a new 1 at the start or the first value one higher. This makes explicit why there's 2^(n-1) of them.

xnor

Posted 2016-09-22T09:01:35.817

Reputation: 115 687

3

Mathematica, 53 bytes

Doesn't beat Martin Ender's answer, which uses the built-in IntegerPartitions function (and built-ins are totally fine by me). (Nor does it beat feersum's answer, which I didn't see until too late.) But I wanted to practice a golfed recursive function.

If[#<1,{{}},Join@@Table[#~Append~j&/@#0[#-j],{j,#}]]&

Recursively generates all compositions, by generating all possible final numbers j and then calling itself on #-j where # is the input.

Greg Martin

Posted 2016-09-22T09:01:35.817

Reputation: 13 940

You can save a few bytes by defining an operator using Array instead of Table and avoiding the Append by using a list and Apply: ±0={{}};±n_:=Join@@Array[{##,n-+##}&@@@±#&,n,0] – Martin Ender – 2016-09-22T18:42:27.987

What does @@ do? – Cyoce – 2016-09-23T01:07:05.033

It replaces the "head" of an expression. For example, f@@g[a,b] evaluates to f[a,b]. Here we're using the fact that a list like { { {1,1,1}, {2,1} } , { {1,2} }, { {3} } } invisibly has head List; so Join@@{ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } } evaluates to Join@@List[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ] evaluates to Join[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ] evaluates to { {1,1,1}, {2,1}, {1,2}, {3} }. – Greg Martin – 2016-09-23T04:11:40.807

3

Retina, 32 bytes

Byte count assumes ISO 8859-1 encoding.

.+
$*
+%1`1
!$'¶$`,!
!+
$.&
A`^,

Try it online!

Explanation

This works similar to my CJam answer. We go through a list N ones and at each position we take both branches of the binary decision a) increment the last value or b) start a new value at 1.

Stage 1

.+
$*

Convert the input to unary.

Stage 2

+%1`1
!$'¶$`,!

The + tells Retina to execute this stage in a loop until the output stops changing. The % tells it to split the input into lines before applying the stage and join them back together afterwards. By putting the % after the +, Retina splits and rejoins after each iteration. One iteration of the stage makes one of those decisions I mentioned and thereby bifurcates the current set of partitions.

How it actually works is that it matches a 1 (but only the first one as indicated by the 1 in front of the backtick), and replaces it with ! (which we'll use as the unary digit of our output), followed by the remaining 1s on this row (this increments the last value). Then on another line () it prints the prefix of the current line, followed by ,!, which inserts a separator and then starts the next value at 1.

Stage 3

!+
$.&

This converts the runs of ! to decimal integers by replacing them with their length.

Stage 4

A`^,

And finally, we notice that we've generated twice as many lines as we wanted, and half of them start with a , (those where we initially made the decision of splitting, even though there wasn't anything to split after yet). Therefore, we discard all lines that start with a ,.

Martin Ender

Posted 2016-09-22T09:01:35.817

Reputation: 184 808

3

Perl, 44 bytes

Includes +3 for -n (code uses $' and $0 so it can't be run as a -e commandline)

Give number to partition on STDIN:

partitions.pl <<< 4

partitions.pl

#!/usr/bin/perl -n
$_=$&-$_.",$_$'",do$0for/\d+/..$&-1;print

If you don't mind extra spaces at the end of a line and an extra newline this 42 byte solution works too (run as perl -M5.010 partitions.pl):

#!/usr/bin/perl -n
$_=$`-$_." $_ $'",do$0for/\s/..$_-1;say

Ton Hospel

Posted 2016-09-22T09:01:35.817

Reputation: 14 114

2

MATL, 15 bytes

:"G:@Z^t!XsG=Y)

Try it online!

Explanation

Given input n, this computes the Cartesian power with increasing exponents k from 1 to n; and for each exponent k selects the tuples that have a sum equal to the input.

:       % Take input n implicitly and push range [1 2 ... n]
"       % For each k in that range
  G:    %   Push [1 2 ... n] again
  @     %   Push k
  Z^    %   Cartesian power. Gives 2D array, say A, with each k-tuple in a row.
  t     %   Duplicate
  !     %   Transpose
  Xs    %   Sum of each column. Gives a row vector
  G=    %   True for entries that equal the input
  Y)    %   Use as logical vector into the rows of array A
        % End implicitly
        % Display stack implicitly

Luis Mendo

Posted 2016-09-22T09:01:35.817

Reputation: 87 464

1

PHP, 125 Bytes

for($i=$n=$argv[1];$i<=str_repeat(1,$n);$i++)if(array_sum($a=str_split($i))==$n&!strpos($i,"0"))$r[]=$a;echo json_encode($r);

-4 Bytes for print_r($r); instead of echo json_encode($r); for the output

a recursive solution with 250 Bytes

function f($n){global$a;foreach($a as$x)foreach(range(1,$n)as$y)$a[]=array_merge((array)$x,[$y]);if(--$n)f($n);}$a=range(1,$w=$argv[1]);f($w-1);foreach($a as$z)if(array_sum((array)$z)==$w)$c[join("-",(array)$z)]=$z;echo json_encode(array_values($c));

Jörg Hülsermann

Posted 2016-09-22T09:01:35.817

Reputation: 13 026

1

Lua 214 203 182 bytes

function g(m, l, n,c)for i=1,m do if i+n < m then l[#l+1]=i;g(m,l,n+i,c+1)elseif i+n == m then l[#l+1]=i;print(unpack(l))end end for k=c,#l do l[k]=nil end end g(io.read()*1,{},0,0)

Ungolved version.

function g(m, l, n,c)
    for i=1,m do 
        if i+n < m then 
            l[#l+1]=i
            g(m,l,n+i,c+1)
        elseif i+n == m then 
            l[#l+1]=i
            print(unpack(l))
        end 
    end 
    for k=c,#l do 
        l[k]=nil 
    end 
end 
g(io.read()*1,{},0,0)

Found a stray whitespace and removed an unnecessary variable to safe 11 bytes. as it turns out, table.insert() is byte inefficient

lenscas

Posted 2016-09-22T09:01:35.817

Reputation: 31

1

Prolog, 81 bytes + 6 bytes to call

L*L.
[H|T]*L:-H>1,M is H-1,[M,1|T]*L.
[H,K|T]*L:-H>1,M is H-1,N is K+1,[M,N|T]*L.

Try it online!
Call with [4]*L., repeat with ; until all solutions have been presented.

Alternatively, if repeatedly pressing ; is not okay (or should be added to the byte count), call with bagof(L,[4]*L,M). which adds 17 bytes for the call.

SQB

Posted 2016-09-22T09:01:35.817

Reputation: 681

1

J, 30 26 bytes

#&1<@(+/;.1)~2#:@(+i.)@^<:

Works by splitting the list of unary n by using the binary values of 2n.

Try it online!

Explanation

#&1<@(+/;.1)~2#:@(+i.)@^<:  Input: n
                        <:  Decrement n
             2         ^    Compute 2^(n-1)
                 (   )@     Operate on that
                   i.         Make the range [0, 1, ..., 2^(n-1)-1]
                  +           Add 2^(n-1) to each in that range
              #:@           Convert each in that range to binary
#&1                         Make n copies of 1 (n in unary)
     (     )~               Operate over each row on RHS and unary n on LHS
        ;.1                   Chop unary n starting at each 1
      +/                        Reduce by addition on each chop
   <@                           Box the sums of each chop

miles

Posted 2016-09-22T09:01:35.817

Reputation: 15 654

0

Actually, 17 16 bytes

This answer is partially based on Luis Mendo's MATL answer. Golfing suggestions welcome. Try it online!

;╗R`╜R∙i`M`Σ╜=`░

Ungolfing

         Implicit input n.
;╗       Duplicate n and save a copy of n to register 0.
R        Take the range of [1..n].
`...`M   Map the following function over the range. Variable k.
  ╛R       Push n from register 0 and take the range [1..n] again.
  ∙        Take the k-th Cartesian power of the range.
  i        Flatten that product.
`...`░   Push values of the previous map where the following function returns a truthy value.
          Variable L.
  Σ        Push sum(L).
  ╜        Push n from register 0.
  =        Check if sum(L) == n.
         Implicit return.

Sherlock9

Posted 2016-09-22T09:01:35.817

Reputation: 11 664

0

Actually, 17 16 15 bytes

This is an interesting fork of Martin Ender's CJam answer (the one with the Cartesian product), with a difference in implementation that I thought was interesting. When one of Martin's strings start with an increment, the errors prevent that string from being evaluated. In Actually, the error is suppressed and the string is evaluated anyway. This ends up giving the compositions of every k in the range [1..n].

Rather than try to remove the extra compositions, I took the n-1th Cartesian power of "1u" appended a "1" to the beginning of each string. This trick gives only the compositions of n. It is, unfortunately, longer than Martin's answer.

Golfing suggestions welcome. Try it online!

D"1u"∙`1@Σ£ƒk`M

Ungolfing

         Implicit input n.
D        Decrement n.
"1u"∙    Take the (n-1)th Cartesian power of the string "1u".
          In Actually, 1 pushes 1 to the stack and u is increment.
`...`M   Map the following function over the Cartesian power. Variable s.
  1@       Push a 1 to be used later.
  Σ        Summing a list of chars joins the chars into one string.
  £ƒ       Turn s into a function and call it immediately on the 1 in the stack.
  k        Take the whole stack and wrap in a list. This is a composition of n.
         Implicit return.

Sherlock9

Posted 2016-09-22T09:01:35.817

Reputation: 11 664