動的プログラミング固有のサブセット生成の実装

Question

この問題は、nの部分集合（nはユーザーの入力）を形成できる方法の総数を求める必要があるところで発生しました。サブセット条件は次のとおりです。サブセット内の数字を区別し、サブセット内の数字を降順にする必要があります。

例：可能な組み合わせが（6,1）（5,2）（4,3）（4,2,1）であるため、n = 7の場合、出力は4です。ただし、（4,1,1,1）でも7を加算しますが、繰り返し数があります。したがって、有効なサブセットではありません。

指数関数的な複雑さを持つバックトラッキング法を使用してこの問題を解決しました。しかし、私はDynamic Progを使用してこの問題をどのように解決できるのか把握しようとしていますか？一番近いのはシリーズです：n = 0,1,2,3,4,5,6,7,8,9,10の場合、出力は0,0,0,1,1です。それぞれ2,3,4,5,7,9である。しかし、私はf（n）を計算するために使用できる一般的な公式を考え出すことができません。インターネットを通っている間、私はhttps://oeis.org/search?q=0%2C0%2C0%2C1%2C1%2C2%2C3%2C4%2C5%2C7%2C9%2C11%2C14&sort=&language=&go=Searchにこの種の整数列を見つけました。しかし、私は彼らがここで提供した公式を理解することができません。どんな助けもありがとう。指数関数的複雑さを改善する他の洞察も高く評価されます。

Answer 1

「ユニークサブセット生成」と呼ばれるものは、integer partitions with distinct partsとしてよく知られています。 Mathworldにはthe Q functionというエントリがあり、別個の部分を持つパーティションの数がカウントされます。

しかし、あなたの関数は少なくとも2つのの異なる部分にsequence that you linked in your questionパーティションの--the数を生成する、些細なパーティション（すなわちn -> (n)）をカウントするので、あなたが探しているのは、実際にQ(n) - 1ではありません。 This answerには数学に関する同様の質問には、より大きな値に簡単に適合させることができるn = 200までのシーケンスを計算するためのJavaの効率的なアルゴリズムが含まれています。ここで

---

は、参照されたアルゴリズムの組み合わせの説明です：

は彼らの合計によってグループ化された{1, 2, 3}のすべてのサブセットのテーブルで始まるのをしてみましょう：

index (sum) partitions  count 
    0   ()     1 
    1   (1)    1 
    2   (2)    1 
    3   (1+2), (3)   2 
    4   (1+3)    1 
    5   (2+3)    1 
    6   (1+2+3)   1 

は、我々が構築したいとしサブテーブルのすべての新しいテーブル{1, 2, 3, 4}。 {1, 2, 3}のすべてのサブセットも{1, 2, 3, 4}のサブセットであるため、上記の各サブセットは新しいテーブルに表示されます。実際には、新しいテーブルを等しいサイズの2つのカテゴリに分けることができます。ではなくであるサブセットには、4が含まれます。私たちができることは、上記の表から始めて、それをコピーしてから、それを4で "伸ばす"ことです。ここで{1, 2, 3, 4}のためのテーブルです：

index (sum) partitions  count 
    0   ()     1 
    1   (1)    1 
    2   (2)    1 
    3   (1+2), (3)   2 
    4   (1+3), [4]   2 
    5   (2+3), [1+4]  2 
    6   (1+2+3),[2+4]  2 
    7   [1+2+4],[3+4]  2 
    8   [1+3+4]   1 
    9   [2+3+4]   1 
    10   [1+2+3+4]   1 

4が含まれるすべてのサブセットは、角括弧で囲まれて、それらは括弧で囲まれている古いサブセットの4に正確に1を加えることによって形成されています。このプロセスを繰り返して{1,2,..,5}、{1,2,..,6}などの表を作成することができます。

実際にはサブセット/パーティションを格納する必要はありません。各インデックス/合計のカウントが必要です。たとえば、{1, 2, 3}の表にカウントだけがある場合、{1, 2, 3, 4}のカウント表を作成するには、index + 4の現在のカウントにcountを追加して、それぞれ(index, count)のペアを古い表から取得します。考えられるのは、3の合計である{1, 2, 3}という2つのサブセットがある場合、これらの2つのサブセットのそれぞれに4を追加すると、7の2つの新しいサブセットが作成されるということです。 - ゼロに合計空set--

def c(n): 
    counts = [1] 

    for k in range(1, n + 1): 
     new_counts = counts[:] + [0]*k 

     for index, count in enumerate(counts): 
      new_counts[index + k] += count 

     counts = new_counts 

    return counts 

我々はただ一つのサブセットを持つ{}用のテーブル、で始まる：これを考慮して

が、ここでは、このプロセスのPython実装です。次に、 {1}のテーブルを作成し、次に {1, 2}のテーブルを構築します。 {1,2,..,n}まですべてのパーティションを nに数えます。 nのパーティションには、 nより大きい整数を含めることはできません。今

、我々はコードに2つの主要な最適化を行うことができます。

1. リミットテーブルをするだけでは、我々が興味を持っているすべてのだから、nまでのエントリを含めるindex + kがnを超えた場合、我々は。それを無視してください。各繰り返しで大きなテーブルを作成するのではなく、最終的なテーブルのスペースを事前に割り当てることもできます。

2. は、代わりに、我々は慎重に後方古いテーブルを反復処理する場合は、各反復でゼロから新しいテーブルを作成するのは、我々は実際に更新することができ、それインプレース新しい値のいずれかをめちゃくちゃにせずに。これらの最適化により

、あなたが効果的に機能を生成することにより、動機た先に参照されたthe Mathematics answerから同じアルゴリズムを、持っています。それはO(n^2)時間で実行され、O(n)スペースしかかかりません。 Pythonでどのように見えるかは次のとおりです。

def c(n): 
    counts = [1] + [0]*n 

    for k in range(1, n + 1): 
     for i in reversed(range(k, n + 1)): 
      counts[i] += counts[i - k] 

    return counts 

def Q(n): 
    "-> the number of subsets of {1,..,n} that sum to n." 
    return c(n)[n] 

def f(n): 
    "-> the number of subsets of {1,..,n} of size >= 2 that sum to n." 
    return Q(n) - 1