2010-08-25 80 views
6

Select[Tuples[Range[0, n], d], Total[#] == n &],但速度更快?枚舉Mathematica中的所有分區

更新

這裏有3個解決方案和他們那個時代的情節,IntegerPartitions其次是排列組合似乎是最快的。定時1,7,0.03遞歸,FrobeniusSolve和IntegerPartition解決方案分別

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

回答

7

您的功能:

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

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

Out[22]= {0.219, Null} 

嘗試FrobeniusSolve

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

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

Out[24]= {0.031, Null} 

的結果是一樣的:

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

Out[25]= True 

你可以把它與IntegerPartitions更快,雖然你不會在同一順序的結果:

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

的排序結果都是一樣的:

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

Out[46]= True 

它的速度要快得多:

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

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

感謝phadej快速回復讓我再次看起來。

注意你只需要調用Permutations(和Flatten)如果你真的希望所有的不同的有序排列,也就是說,如果你想

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

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

,而不是

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

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

這比FrobeniusSolve更快:)

編輯:如果writ十個在Haskell,它可能更清楚發生了什麼 - 功能如下:

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