List all ordered partitions of n

Question

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

Answer 1

Haskell, 37 bytes

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

xnor saved two bytes.

Answer 2

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.

Answer 3

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.

Answer 4

JavaScript (Firefox 30-57), 63 bytes

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

Answer 5

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

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

Answer 7

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 2^n-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.
}/

Answer 8

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

Answer 9

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.

Answer 10

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

Answer 11

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

Answer 12

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.

Answer 13

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

Answer 14

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

Answer 15

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!

Answer 16

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.

Answer 17

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.

Answer 18

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

Answer 19

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

Answer 20

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

Answer 21

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

Answer 22

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

Answer 23

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

Answer 24

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.

Answer 25

J, 30 26 bytes

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

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

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

Answer 26

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.

Answer 27

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.