37

正の数の可能なすべてのパーティションを生成するアルゴリズムが必要でした.1つ（回答として投稿）を思いつきましたが、それは指数関数的な時間です。

アルゴリズムは、数値がそれ自体以下の正の数値の合計として表現できるすべての可能な方法を返す必要があります。たとえば、数値5の場合、結果は次のようになります。

  • 5
  • 4+1
  • 3+2
  • 3+1+1
  • 2+2+1
  • 2+1+1+1
  • 1+1+1+1+1

だから私の質問は: これのためのより効率的なアルゴリズムはありますか?

編集：これが何と呼ばれているのか本当にわからなかったので、質問のタイトルは「数値の和分解」でした。ShreevatsaR は、それらが「パーティション」と呼ばれていることを指摘したので、それに応じて質問のタイトルを編集しました。

4

9 に答える 9

28

これはパーティションと呼ばれます。[ウィキペディア:パーティション (数論)も参照してください。]

パーティション p(n) の数は指数関数的に増加するため、すべてのパーティションを生成するために何をするにしても、必ず指数関数的な時間がかかります。

とはいえ、自分のコードよりもうまくやることはできます。この、またはDavid EppsteinによるPython Algorithms and Data Structuresの更新版を参照してください。

于 2008-12-30T16:50:12.613 に答える
23

Pythonでの私のソリューション（指数時間）は次のとおりです。

q = { 1: [[1]] }

def decompose(n):
    try:
        return q[n]
    except:
        pass

    result = [[n]]

    for i in range(1, n):
        a = n-i
        R = decompose(i)
        for r in R:
            if r[0] <= a:
                result.append([a] + r)

    q[n] = result
    return result

 

>>> decompose(5)
[[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
于 2008-12-30T16:45:56.320 に答える
5

より効率的なアルゴリズムを求めると、どれを比較すればよいかわかりません。しかし、これは単純な方法で書かれたアルゴリズムの 1 つです (Erlang):

-module(partitions).

-export([partitions/1]).

partitions(N) -> partitions(N, N).

partitions(N, Max) when N > 0 ->
    [[X | P]
     || X <- lists:seq(min(N, Max), 1, -1),
        P <- partitions(N - X, X)];
partitions(0, _) -> [[]];
partitions(_, _) -> [].

時間的には指数関数的 ( Python での Can Berk Güder のソリューションと同じ) であり、スタック空間では線形です。しかし、同じトリックであるメモ化を使用すると、メモリを節約し、指数を減らすことで大幅な改善を実現できます。(N=50 で 10 倍高速)

mp(N) ->
    lists:foreach(fun (X) -> put(X, undefined) end,
          lists:seq(1, N)), % clean up process dictionary for sure
    mp(N, N).

mp(N, Max) when N > 0 ->
    case get(N) of
      undefined -> R = mp(N, 1, Max, []), put(N, R), R;
      [[Max | _] | _] = L -> L;
      [[X | _] | _] = L ->
          R = mp(N, X + 1, Max, L), put(N, R), R
    end;
mp(0, _) -> [[]];
mp(_, _) -> [].

mp(_, X, Max, R) when X > Max -> R;
mp(N, X, Max, R) ->
    mp(N, X + 1, Max, prepend(X, mp(N - X, X), R)).

prepend(_, [], R) -> R;
prepend(X, [H | T], R) -> prepend(X, T, [[X | H] | R]).

とにかく、言語と目的をベンチマークする必要があります。

于 2008-12-30T22:29:03.430 に答える
-1

Java の実装。メモ化の恩恵を受けることができます。

public class Partition {

    /**
     * partition returns a list of int[] that represent all distinct partitions of n.
     */
    public static List<int[]> partition(int n) {
        List<Integer> partial = new ArrayList<Integer>();
        List<int[]> partitions = new ArrayList<int[]>();
        partition(n, partial, partitions);
        return partitions;
    }

    /**
     * If n=0, it copies the partial solution into the list of complete solutions.
     * Else, for all values i less than or equal to n, put i in the partial solution and partition the remainder n-i.
     */
    private static void partition(int n, List<Integer> partial, List<int[]> partitions) {
        //System.out.println("partition " + n + ", partial solution: " + partial);
        if (n == 0) {
            // Complete solution is held in 'partial' --> add it to list of solutions
            partitions.add(toArray(partial));
        } else {
            // Iterate through all numbers i less than n.
            // Avoid duplicate solutions by ensuring that the partial array is always non-increasing
            for (int i=n; i>0; i--) {
                if (partial.isEmpty() || partial.get(partial.size()-1) >= i) {
                    partial.add(i);
                    partition(n-i, partial, partitions);
                    partial.remove(partial.size()-1);
                }
            }
        }
    }

    /**
     * Helper method: creates a new integer array and copies the contents of the list into the array.
     */
    private static int[] toArray(List<Integer> list) {
        int i = 0;
        int[] arr = new int[list.size()];
        for (int val : list) {
            arr[i++] = val;
        }
        return arr;
    }
}
于 2013-05-28T18:20:40.250 に答える