2

合計Nの整数パーティションの数を探しています。パーツの数はSで、最大パーツは正確にXであり、すべてを列挙することはありません。

例：10個のパーツと42個が最大のパーツを持つ100個のすべてのパーティション。

この質問に対処する定理または分割IDは見つかりませんでした。これは、既知の定理から簡単に導き出せない重要な問題であると思われます（Nijenhuis and Wilf 1978、Andrews et al。2004、Bona 2006など）。

例：正確にSの部分を持つNのパーティションの数は、正確にSが最大の部分であるNのパーティションの数に等しくなります。

この質問は、純粋数学をはるかに超えた私の研究に関連しています。

更新：この質問は以下で回答されていますが、実装に使用したPythonスクリプトを投稿したいと思いました。速度を上げるために、おそらくCythonにプッシュします。

n = 100 # the total
s = 10  # number of parts
x = 20  # largest part
print Partitions(n,length=s,max_part=x).cardinality() # Sage is very slow at this

def parts_nsx(n,s,x):
    if n==0 and s==0:return 1
    if n<=0 or s<=0 or x<=0:return 0
    if n>0 and s>0 and x>0:
        _sum = 0
        for i in range(0,s+1):
            _sum += parts_nsx(n-i*x, s-i, x-1)
        return _sum    
print parts_nsx(n,s,x)
4

1 に答える 1

1

この数のパーティションでは、再帰P(n,s,x)が保持されます。

P(n,s,x) = sum P(n-i*x, s-i, x-1), for i=0,...,s 
P(0,0,x) = 1
P(n,s,x) = 0, if n <= 0 or s <= 0 or x <= 0

計算は効率的ではありません。おそらくあなたの例では、それは十分に速いでしょう。

メモ化を使用して実装するのが最適です。

編集：

メモ化を使用したPythonの実装：

D = {}
def P(n,s,x):
  if n > s*x or x <= 0: return 0
  if n == s*x: return 1
  if (n,s,x) not in D:
    D[(n,s,x)] = sum(P(n-i*x, s-i, x-1) for i in xrange(s))
  return D[(n,s,x)]

P(100, 10, 42)
2685871

アップデート：

パラメータを満たすパーティションは、最大サイズのパーティションをn,s,x持つことができます。これらのパーツをサイズで削除すると、パラメータで同じ問題が発生します 。たとえば、10個のパーツと42個のパーツが最大のパーツである100個のパーティションは、サイズ42の0個、1個、または2個のパーツを持つことができます。ixixn-i*x, s-i, x-1

P(0,0,x) = 1これは、前の反復ですでにパーティションがあることを意味します。

P(n,s,x) = 0, if n>s*x means that we can't partition n with all partitions of maximal size, so it is not possible combination of parameters. Boundary conditions are

于 2012-09-16T14:25:49.227 に答える