c++ - C++のパーティション関数

Question

パーティションの問題のためにc++のアルゴリズムソリューションが必要です

簡単な説明：数nを得るすべての合計を見つけます。例えば

• 入力：5
• 出力：
  • 11111
  • 2111
  • 311
  • 41
  • 5
  • 221
  • 23

この問題はとても簡単に思えますが、解決策を見つけることができませんでした。最高の入力は11であるため、私はこのブルートフォース攻撃に近づいています。その問題に関する記事は非常に数学的なものであり、実際にはわかりません。

皆さん、ありがとうございました！

Answer 1

関数Fを使用して再帰的アプローチを試して、指定された数Xのすべての第1レベルのパーティションを見つけることができます。つまり、Xは2つの整数a、b <Xの合計として表され、aとbでFを再度呼び出すことができます。もう分割されます。これは、C++で独自の記述を行う際に役立つPythonの例です。

Answer 2

明確に定義された順序でそれらを配置するだけです。次に、この順序で最初のエントリを検索する関数を記述します。次に、その順序で次のエントリを検索する関数を記述します。その場合、問題は些細なことです。

たとえば、5の場合、最初のエントリには11111または5の2つの選択肢があります。これらのエントリのいずれかを生成するのは簡単です。次に、特定のエントリから「次のエントリ」を取得するための操作が必要です。失敗して完了するまで、その操作を繰り返します。

私はこの順序を提案します：

 11111
 1112
 113
 122
 14
 23
 5

Answer 3

/*
E.g.
input number:5
5
1 4
1 1 3
1 1 1 2
1 1 1 1 1
1 2 2
2 3
*/
#include <iostream>
#include <vector>

using namespace std;

void print (vector<int>& v, int level){
    for(int i=0;i<=level;i++)
        cout << v[i] << " ";
    cout << endl;
}

void part(int n, vector<int>& v, int level){
    int first; /* first is before last */

    if(n<1) return ;
    v[level]=n;
    print(v, level);

    first=(level==0) ? 1 : v[level-1];

    for(int i=first;i<=n/2;i++){
        v[level]=i; /* replace last */
        part(n-i, v, level+1);
    }
}

int main(){
    int N;
    cout << "input number:";
    cin >> N;

    vector<int> v(N);

    part(N, v, 0);
}