当你想在你的代码中找到一个错误时,这很难;当你认为你的代码是不会有错误时,这就更难了。

枚举Mathematica中的所有分区

admin 77℃
就像 Select[Tuples[Range[0, n], d], Total[#] == n &] ,但更快?

更新

下面是3个解和它们的时间图,整数部分后排列似乎是最快的。递归解、frobeniussolve解和积分部分解分别在1、7、0.03时计时

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

您的功能:

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}}
partition[n_, 1] := {{n}}
partition[n_, d_] := Flatten[ Table[ Map[Join[{k}, #] &, partition[n - k, d - 1]], {k, 0, n}], 1]

这比frobeniussolve还要快:)

编辑:如果用haskell编写,可能会更清楚发生了什么-功能性的:

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

转载请注明:我的代码 » 枚举Mathematica中的所有分区