enumerating all partitions in Mathematica

Answer 1

Your function:

In[21]:= g[n_, d_] := Select[Tuples[Range[0, n], d], Total[#] == n &]

In[22]:= Timing[g[15, 4];]

Out[22]= {0.219, Null}

Try FrobeniusSolve:

In[23]:= f[n_, d_] := FrobeniusSolve[ConstantArray[1, d], n]

In[24]:= Timing[f[15, 4];]

Out[24]= {0.031, Null}

The results are the same:

In[25]:= f[15, 4] == g[15, 4]

Out[25]= True

You can make it faster with IntegerPartitions, though you don't get the results in the same order:

In[43]:= h[n_, d_] := 
 Flatten[Permutations /@ IntegerPartitions[n, {d}, Range[0, n]], 1]

The sorted results are the same:

In[46]:= Sort[h[15, 4]] == Sort[f[15, 4]]

Out[46]= True

It is much faster:

In[59]:= {Timing[h[15, 4];], Timing[h[23, 5];]}

Out[59]= {{0., Null}, {0., Null}}

Thanks to phadej's fast answer for making me look again.

Note you only need the call to Permutations (and Flatten) if you actually want all the differently ordered permutations, i.e. if you want

In[60]:= h[3, 2]

Out[60]= {{3, 0}, {0, 3}, {2, 1}, {1, 2}}

instead of

In[60]:= etc[3, 2]

Out[60]= {{3, 0}, {2, 1}}

Answer 2

partition[n_, 1] := {{n}}
partition[n_, d_] := Flatten[ Table[ Map[Join[{k}, #] &, partition[n - k, d - 1]], {k, 0, n}], 1]

This is even quicker than FrobeniusSolve :)

Edit: If written in Haskell, it's probably clearer what is happening - functional as well:

partition n 1 = [[n]]
partition n d = concat $ map outer [0..n]
  where outer k = map (k:) $ partition (n-k) (d-1)