enumerating all partitions in Mathematica

Question

Like Select[Tuples[Range[0, n], d], Total[#] == n &], but faster?

Update

Here are the 3 solutions and plot of their times, IntegerPartitions followed by Permutations seems to be fastest. Timing at 1, 7, 0.03 for recursive, FrobeniusSolve and IntegerPartition solutions respectively

partition[n_, 1] := {{n}};
partition[n_, d_] := 
  Flatten[Table[
    Map[Join[{k}, #] &, partition[n - k, d - 1]], {k, 0, n}], 1];
f[n_, d_, 1] := partition[n, d];
f[n_, d_, 2] := FrobeniusSolve[Array[1 &, d], n];
f[n_, d_, 3] := 
  Flatten[Permutations /@ IntegerPartitions[n, {d}, Range[0, n]], 1];
times = Table[First[Log[Timing[f[n, 8, i]]]], {i, 1, 3}, {n, 3, 8}];
Needs["PlotLegends`"];
ListLinePlot[times, PlotRange -> All, 
 PlotLegend -> {"Recursive", "Frobenius", "IntegerPartitions"}]
Exp /@ times[[All, 6]]

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)