List all ordered partitions of n
Haskell, 37 bytes
f 0=[[]]
f n=[a:x|a<-[1..n],x<-f$n-a]
xnor saved two bytes.
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.
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.