# List all ordered partitions of n

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]))):[[]]

• 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 Sep 22 '16 at 9:08
• @Fatalize Here [2 1 1] is different from [1 2 1], unlike there. I suspect the approaches may be significantly different – Luis Mendo Sep 22 '16 at 9:14
• To 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 Sep 22 '16 at 9:30
• I'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 Sep 22 '16 at 9:50
• The usual term for these ordered partitions is "compositions". – Greg Martin Sep 22 '16 at 17:54

# 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

• Amazing. This is the smallest one I've seen so far! – driima Sep 22 '16 at 12:38

f 0=[[]]
f n=[a:x|a<-[1..n],x<-f$n-a]  xnor saved two bytes. • It looks like the more straightforward f n=[a:x|a<-[1..n],x<-f$n-a] is shorter. – xnor Sep 22 '16 at 10:06
• you don't need the zero check (given positive integer n ... numbers from 1 to n) – nyro_0 Sep 22 '16 at 10:16
• f 0=[[]] just happens to be a shorter base case than f 1=[[1]] :) – Lynn Sep 22 '16 at 11:14
• @xyLe_ It's used a recursive base case. – xnor Sep 22 '16 at 17:13
• ah sure, you are right, my bad – nyro_0 Sep 23 '16 at 5:41

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

• Simple, small and yet still amazingly readable. That's what I love about Python. – driima Sep 26 '16 at 7:28

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

• 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 Sep 22 '16 at 13:08
• An explanation with the code would really make it beautiful. – noman pouigt Sep 22 '16 at 16:14

## JavaScript (Firefox 30-57), 63 bytes

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

• Firefox 30+ sounds like a special browser for the more mature users of the internet. – Martin Ender Sep 22 '16 at 10:08
• Probably doesn't get shorter than this... – ETHproductions Sep 22 '16 at 14:08
• Any way this can be ungolfed for JavaScript in other browsers? – driima Sep 22 '16 at 14:10
• @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 Sep 22 '16 at 17:34

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

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

• 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 Sep 22 '16 at 20:51

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


# 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. ## 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]]  • Hiya! Could you add a little bit of explanation for people (like me) who aren't familiar with Ruby? – AdmBorkBork Sep 22 '16 at 12:58 • x<<i is shorter than [i]+x. – m-chrzan Sep 22 '16 at 16:34 • @TimmyD I added an ungolfed code and the usage. – cia_rana Sep 22 '16 at 16:40 • @ m-chrzan Thanks for your advice! I edited that. – cia_rana Sep 22 '16 at 16:43 • Any reason .flatten(1) isn't .flatten 1 ? – Cyoce Sep 23 '16 at 1:09 # 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  • 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 Sep 22 '16 at 14:55 • @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 Sep 22 '16 at 15:06
• 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 Sep 22 '16 at 15:21

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


# 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

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

• @alephalpha No, that wouldn't help as then I'd have to change the MapAt index to -1. – feersum Sep 23 '16 at 12:04

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

• You can use — instead of iy, :). – Adnan Sep 22 '16 at 15:08
• @Adnan: Thanks! Forgot about that one. – Emigna Sep 22 '16 at 15:49

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. # 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. • 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 Sep 22 '16 at 18:42 • What does @@ do? – Cyoce Sep 23 '16 at 1:07 • 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 Sep 23 '16 at 4:11 ## Retina, 32 bytes Byte count assumes ISO 8859-1 encoding. .+$*
+%11
!$'¶$,!
!+
$.& 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

+%11
!$'¶$,!


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 ,. # 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  ## 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 • 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. Sep 22 '16 at 19:46 • @AlexA. ah, sorry the f(N)= got lost at copying, I've had it in when counting bytes – nyro_0 Sep 23 '16 at 5:43 # 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  # Lua 214203 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 # 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));


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

# 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


# Actually, 17 16 bytes

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

;╗R╜R∙iMΣ╜=░


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.


# Actually, 1716 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@Σ£ƒkM


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