2

数値を受け取り、合計がその数値 (パーティション) になる数値のリストの をn返す再帰関数を定義しました。list

def P(n):
    # base case of recursion: zero is the sum of the empty list
    if n == 0:
        yield []
        return

    for p in P(n-1):        
        p.append(1)
        yield p
        p.pop()
        if p and (len(p) < 2 or p[-2] > p[-1]):
            p[-1] += 1
            yield p

関数がnumberのパーティション数を返すようにする方法を考えていましたn。

たとえば、P(6)を返し10ます。

4

3 に答える 3

4

ウィキペディアのPartiton（数論）ページの「Partitionfunctionformulas」セクションを見ると、パーティション番号を見つける簡単な方法がないことがわかります。

代わりに、あなたの最善の策はおそらく次のとおりです。

sum(1 for _ in P(6))

または、少し単純ですが、大量のメモリを占有します

len(list(P(6)))

既存の関数を使用します。

また、によって返された値を保存できるようにしたい場合は、そうではないことに注意してくださいP。コピーyieldを作成し、同じリスト（変更したもの）を何度も生成しないようにします。そうすると、その理由がわかります。同じ空のリストが何度も繰り返されたリストが返されます。p[:]plist(P(6))

パーティショニングの詳細については、Pythonによるパーティショニングを参照してください。

于 2011-10-18T04:15:03.810 に答える
0

Wolfram Mathworld :

P(n, k) は、正確に k 項の合計として n を記述する方法の数、または同等に、最大が正確に k である部分への分割の数を示します。(「正確に k」を「k 以下」に変更し、「最大は正確に k」を「k より大きい要素なし」に変更すると、分割関数 q が得られることに注意してください。) たとえば、P(5 , 3) = 2、長さ 3 の 5 のパーティションは {3, 1, 1} と {2, 2, 1} であり、最大要素 3 の 5 のパーティションは {3, 2} と {3, 1、1}。
... P(n, k) は再帰関係P(n, k) = P(n-1, k-1) + P(nk, k)
から計算できます (Skiena 1990, p. 58; Ruskey)ここで、k > n の場合は P(n, k) = 0、P(n, n) = 1、および P(n, 0) = 0 です。

したがって、n の書き方の数を合計として計算したい場合は、次のように計算する必要があります。

ここに画像の説明を入力

P(n, k) を定義しましょう:

def p(n, k):
    """Gives the number of ways of writing n as a sum of exactly k terms or, equivalently, 
    the number of partitions into parts of which the largest is exactly k.  
    """
    if n < k:
        return 0
    if n == k:
        return 1
    if k == 0:
        return 0

    return p(n-1, k-1) + p(n-k, k)

nこれで、書き方の数を合計として計算できます。

n = 6
partitions_count = 0

for k in range(n + 1):
    partitions_count += p(n, k)

print(partitions_count)

# Output:
# 11

再帰関数と同様p(n, k)に、それぞれの値をディクショナリに保存することで速度を上げ(高速なハッシュベースの検索のp(n, k)おかげで!)、計算する前に値が計算されたかどうかを確認します (値がディクショナリにあるかどうかを確認します)。 :

dic = {}
def p(n, k):
    """Gives the number of ways of writing n as a sum of exactly k terms or, equivalently, 
        the number of partitions into parts of which the largest is exactly k.  
    """
    if n < k:
        return 0
    if n == k:
        return 1
    if k == 0:
        return 0

    key = str(n) + ',' + str(k)
    try:
        temp = dic[key]
    except:
        temp = p(n-1, k-1) + p(n-k, k)
        dic[key] = temp
    finally:
        return temp

フル機能:

def partitions_count(n):
    """Gives the number of ways of writing the integer n as a sum of positive integers,
    where the order of addends is not considered significant.
    """
    dic = {}
    def p(n, k):
        """Gives the number of ways of writing n as a sum of exactly k terms or, equivalently, 
        the number of partitions into parts of which the largest is exactly k.  
        """
        if n < k:
            return 0
        if n == k:
            return 1
        if k == 0:
            return 0
        
        key = str(n) + ',' + str(k)
        try:
            temp = dic[key]
        except:
            temp = p(n-1, k-1) + p(n-k, k)
            dic[key] = temp
        finally:
            return temp
    
    partitions_count = 0
    for k in range(n + 1):
        partitions_count += p(n, k)
    return partitions_count

便利なリンク：

于 2020-09-04T09:48:22.353 に答える
-2

目的の結果を計算するための Java の例を次に示します。

/**
 * Returns the number of ways the number n can be partitioned
 * into sums of positive integers larger than k. 
 * @param k
 * @param n
 * @return
 */
public static long partition(long k, long n){
    long sum = 0;
    if(k > n) return 0;
    if(k == n) return 1;
    sum += partition(k+1, n) + partition(k, n-k);
    return sum;
}
于 2012-08-03T21:19:45.620 に答える