0

k 個の部分で n のすべてのパーティションを列挙しようとしています。

したがって、p(5,3) の場合、k = 3 => (3,1,1)、(2,2,1) の 2 つのパーティションが得られます。

stackoverflow を検索して調べた結果、次のことがわかりました。

def p(n,k):
    lst = []
    if n < k:
        return lst
    elif k == 1:
        return lst
    elif k == n:
        return lst
    else:
        p(n-1, k-1) 
        p(n-k, k)
    return lst

^^^^これは私が望む形です。

そのままで、k 個の部分の合計を見つけるのは簡単です。p(n-1, k-1) + p(nk,k) を返します。私の場合、[(3,1,1), (2,2,1)] のように各要素をリストする必要があります。

私の主な問題は、これらのパーティションを再帰的に「構築」することです。これにどのように取り組みますか？

編集

基本ケース k = 1 を取得する場合は、+ 1、k-1 回を追加します。(4,1) 次に (4,1,1)

基本ケース k = n の場合は、分割して各部分に 1 つを削除します。

そのように：（3,3）次に（3,3,3）そして（2,2,2）

基本ケース k < n の場合、何もありません

基本的に、私の問題は、ベースケースからトップまでのものを「積み重ね」、完全なリストを取得することです p(6,3) = [(2,2,2), (4,1,1), (3,2 、1)]

ここに画像の説明を入力

4

1 に答える 1

2

再帰関数にm、要素がパーティション内で持つことができる最大値である 3 番目のパラメーターを追加します。次に、次のように関数を定義します。

def p(n, k, m=None):
    if m is None:
        m = n - k + 1 # maximum can be n - k + 1 since minimum is 1
    if k == 0:
        if n == 0:
            yield ()
        return
    for i in xrange(1, m + 1): # first could be from 1 to the maximum
        # the rest of the sum will be n - i among k - 1 elements with
        # maximum i
        for t in p(n - i, k - 1, i):
            yield (i, ) + t

例:

>>> list(p(10, 3))
[(4, 3, 3), (4, 4, 2), (5, 3, 2), (5, 4, 1), (6, 2, 2), (6, 3, 1), (7, 2, 1), (8 , 1, 1)]
>>> list(p(6, 2))
[(3, 3), (4, 2), (5, 1)]
于 2015-04-16T21:04:50.233 に答える