python - 整数分割のためのエレガントな Python コード

Question

標準の整数分割問題 (ウィキペディア) を解決するコードを作成しようとしました。私が書いたコードはめちゃくちゃでした。コーディング スタイルを改善したいので、問題を解決するための洗練されたソリューションが必要です。これは宿題の質問ではありません。

Answer 1

この回答は問題ありませんが、以下の skovorodkin の回答をお勧めします。

>>> def partition(number):
...     answer = set()
...     answer.add((number, ))
...     for x in range(1, number):
...         for y in partition(number - x):
...             answer.add(tuple(sorted((x, ) + y)))
...     return answer
... 
>>> partition(4)
set([(1, 3), (2, 2), (1, 1, 2), (1, 1, 1, 1), (4,)])

すべての順列（つまり、（1、3）と（3、1））が必要な場合は、次のように変更answer.add(tuple(sorted((x, ) + y))しますanswer.add((x, ) + y)

Answer 2

受け入れられた応答よりもはるかに速く、見栄えも悪くありません。受け入れられた応答は、より低い整数のパーティションを複数回計算するため、多くの同じ作業を複数回実行します。たとえば、n=22 の場合、差は0.0467 秒に対して 12.7 秒です。

def partitions_dp(n):
    partitions_of = []
    partitions_of.append([()])
    partitions_of.append([(1,)])
    for num in range(2, n+1):
        ptitions = set()
        for i in range(num):
            for partition in partitions_of[i]:
                ptitions.add(tuple(sorted((num - i, ) + partition)))
        partitions_of.append(list(ptitions))
    return partitions_of[n]

コードは基本的に同じですが、小さい整数のパーティションを保存するため、何度も計算する必要はありません。

Answer 3

これは、パーティションの番号を昇順で格納するスタックを使用する再帰関数です。それは十分に速く、非常に直感的です。

# get the partitions of an integer

Stack = []
def Partitions(remainder, start_number = 1):
    if remainder == 0:
        print(" + ".join(Stack))
    else:
        for nb_to_add in range(start_number, remainder+1):
            Stack.append(str(nb_to_add))
            Partitions(remainder - nb_to_add, nb_to_add)
            Stack.pop()

スタックがいっぱいになると (スタックの要素の合計が必要なパーティションの数に対応します)、それを出力し、最後の値を削除して、スタックに格納される次の値をテストします。次のすべての値がテストされると、スタックの最後の値が再度ポップされ、最後に呼び出した関数に戻ります。出力の例を次に示します (8 を使用):

Partitions(8)
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 2
1 + 1 + 1 + 1 + 1 + 3
1 + 1 + 1 + 1 + 2 + 2
1 + 1 + 1 + 1 + 4
1 + 1 + 1 + 2 + 3
1 + 1 + 1 + 5
1 + 1 + 2 + 2 + 2
1 + 1 + 2 + 4
1 + 1 + 3 + 3
1 + 1 + 6
1 + 2 + 2 + 3
1 + 2 + 5
1 + 3 + 4
1 + 7
2 + 2 + 2 + 2
2 + 2 + 4
2 + 3 + 3
2 + 6
3 + 5
4 + 4
8

再帰関数の構造は理解しやすく、以下に示されています (整数 31 の場合)。

remainderパーティションに必要な残りの数の値に対応します (上記の例では 31 と 21)。 start_numberパーティションの最初の番号に対応し、デフォルト値は 1 です (上記の例では 1 と 5)。

結果をリストで返し、パーティションの数を取得したい場合は、次のようにすることができます。

def Partitions2_main(nb):
    global counter, PartitionList, Stack
    counter, PartitionList, Stack = 0, [], []
    Partitions2(nb)
    return PartitionList, counter

def Partitions2(remainder, start_number = 1):
    global counter, PartitionList, Stack
    if remainder == 0:
        PartitionList.append(list(Stack))
        counter += 1
    else:
        for nb_to_add in range(start_number, remainder+1):
            Stack.append(nb_to_add)
            Partitions2(remainder - nb_to_add, nb_to_add)
            Stack.pop()

最後に、Partitions上記の関数の大きな利点は、自然数のすべての構成を見つけるのに非常に簡単に適応できることです (2 つの構成が同じ数のセットを持つことができますが、この場合は順序が異なります): ドロップするだけです。変数をループ内start_numberで 1 に設定します。for

# get the compositions of an integer

Stack = []
def Compositions(remainder):
    if remainder == 0:
        print(" + ".join(Stack))
    else:
        for nb_to_add in range(1, remainder+1):
            Stack.append(str(nb_to_add))
            Compositions(remainder - nb_to_add)
            Stack.pop()

出力例:

Compositions(4)
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
1 + 3
2 + 1 + 1
2 + 2
3 + 1
4

Answer 4

ここのレシピはエレガントと言えるかもしれません。これは無駄がなく (20 行の長さ)、高速で、その中で参照されている Kelleher と O'Sullivan の作業に基づいています。

def aP(n):
    """Generate partitions of n as ordered lists in ascending
    lexicographical order.

    This highly efficient routine is based on the delightful
    work of Kelleher and O'Sullivan.

    Examples
    ========

    >>> for i in aP(6): i
    ...
    [1, 1, 1, 1, 1, 1]
    [1, 1, 1, 1, 2]
    [1, 1, 1, 3]
    [1, 1, 2, 2]
    [1, 1, 4]
    [1, 2, 3]
    [1, 5]
    [2, 2, 2]
    [2, 4]
    [3, 3]
    [6]

    >>> for i in aP(0): i
    ...
    []

    References
    ==========

    .. [1] Generating Integer Partitions, [online],
        Available: http://jeromekelleher.net/generating-integer-partitions.html
    .. [2] Jerome Kelleher and Barry O'Sullivan, "Generating All
        Partitions: A Comparison Of Two Encodings", [online],
        Available: http://arxiv.org/pdf/0909.2331v2.pdf

    """
    # The list `a`'s leading elements contain the partition in which
    # y is the biggest element and x is either the same as y or the
    # 2nd largest element; v and w are adjacent element indices
    # to which x and y are being assigned, respectively.
    a = [1]*n
    y = -1
    v = n
    while v > 0:
        v -= 1
        x = a[v] + 1
        while y >= 2 * x:
            a[v] = x
            y -= x
            v += 1
        w = v + 1
        while x <= y:
            a[v] = x
            a[w] = y
            yield a[:w + 1]
            x += 1
            y -= 1
        a[v] = x + y
        y = a[v] - 1
        yield a[:w]

Answer 5

私のコードが最もエレガントかどうかはわかりませんが、研究目的でこれを何度も解決する必要がありました。を変更すると、

sub_nums

変数を使用すると、パーティションで使用される番号を制限できます。

def make_partitions(number):
    out = []
    tmp = []
    sub_nums = range(1,number+1)
    for num in sub_nums:
        if num<=number:
            tmp.append([num])
        for elm in tmp:
            sum_elm = sum(elm)
            if sum_elm == number:
                out.append(elm)
            else:
                for num in sub_nums:
                    if sum_elm + num <= number:
                         L = [i for i in elm]
                         L.append(num)
                         tmp.append(L)
    return out

Answer 6

F(x,n) = \union_(i>=n) { {i}U g| g in F(x-i,i) }

この再帰を実装するだけです。F(x,n) は、合計が x で、その要素が n 以上のすべてのセットのセットです。