IntegerPartition 的变体? [英] A variation of IntegerPartition?

问题描述

IntegerPartitions[n, {3, 10}, Prime ~Array~ 10]

在 Mathematica 中，这将给出将 n 作为前十个素数的三到十之和的所有方法的列表，根据需要允许重复.

In Mathematica this will give a list of all the ways to get n as the sum of from three to ten of the first ten prime numbers, allowing duplicates as needed.

如何有效地找到等于 n 的总和，从而允许每个元素只使用一次?

How can I efficiently find the sums that equal n, allowing each element to only be used once?

使用前十个素数只是一个玩具示例.我寻求对任意论点有效的解决方案.在实际情况下，生成所有可能的和，即使使用多项式系数，也会占用太多内存.

Using the first ten primes is only a toy example. I seek a solution that is valid for arbitrary arguments. In actual cases, generating all possible sums, even using polynomial coefficients, takes too much memory.

我忘记说明我使用的是 Mathematica 7.

I forgot to include that I am using Mathematica 7.

推荐答案

下面将构建一个二叉树，然后对其进行分析并提取结果:

The following will build a binary tree, and then analyze it and extract the results:

Clear[intParts];
intParts[num_, elems_List] /; Total[elems] < num := p[];
intParts[num_, {fst_, rest___}] /; 
   fst < num := {p[fst, intParts[num - fst, {rest}]], intParts[num, {rest}]};
intParts[num_, {fst_, rest___}] /; fst > num := intParts[num, {rest}];
intParts[num_, {num_, rest___}] := {pf[num], intParts[num, {rest}]};


Clear[nextPosition];
nextPosition = 
  Compile[{{pos, _Integer, 1}},
     Module[{ctr = 0, len = Length[pos]},
       While[ctr < len && pos[[len - ctr]] == 1, ++ctr];
       While[ctr < len && pos[[len - ctr]] == 2, ++ctr];
       Append[Drop[pos, -ctr], 1]], CompilationTarget -> "C"];

Clear[getPartitionsFromTree, getPartitions];
getPartitionsFromTree[tree_] :=
  Map[Extract[tree, #[[;; -3]] &@FixedPointList[nextPosition, #]] &, 
     Position[tree, _pf, Infinity]] /. pf[x_] :> x;
getPartitions[num_, elems_List] := 
    getPartitionsFromTree@intParts[num, Reverse@Sort[elems]];

例如，

In[14]:= getPartitions[200,Prime~Array~150]//Short//Timing

Out[14]= {0.5,{{3,197},{7,193},{2,5,193},<<4655>>,{3,7,11,13,17,19,23,29,37,41},      
       {2,3,5,11,13,17,19,23,29,37,41}}}

这并不是非常快，也许算法可以进一步优化，但至少分区的数量不会像 IntegerPartitions 那样快速增长.

This is not insanely fast, and perhaps the algorithm could be optimized further, but at least the number of partitions does not grow as fast as for IntegerPartitions.

有趣的是，在我之前使用的示例中，简单的记忆将解决方案的速度提高了大约两倍:

It is interesting that simple memoization speeds the solution up about twice on the example I used before:

Clear[intParts];
intParts[num_, elems_List] /; Total[elems] < num := p[];
intParts[num_, seq : {fst_, rest___}] /; fst < num := 
    intParts[num, seq] = {p[fst, intParts[num - fst, {rest}]], 
          intParts[num, {rest}]};
intParts[num_, seq : {fst_, rest___}] /; fst > num := 
    intParts[num, seq] = intParts[num, {rest}];
intParts[num_, seq : {num_, rest___}] := 
    intParts[num, seq] = {pf[num], intParts[num, {rest}]};

现在，

In[118]:= getPartitions[200, Prime~Array~150] // Length // Timing

Out[118]= {0.219, 4660}

这篇关于IntegerPartition 的变体?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！