Print all combinations of a number N, as a sum of positive integers?
They should be unique
例
3 =
1 2
1 1 1
.
4=
3 1
2 2
1 1 2
1 1 1 1
バックトラッキングを使用してこれに対する解決策を作成しましたが、問題は、たとえば3の重複も与えることです
私は得ています
1 1 2
2 1 1
ユニークな組み合わせだけを取得するには?
事前に多くの感謝
あなたが背中を作るとき、あなたは常に最後の数字から始めます（初めて1を最後の数字と見なします）（基本的にあなたはソートされたソリューションを維持します）これはあなたが常にユニークなソリューションを維持する方法です。
#include <iostream>
const int N = 4;
int sol[N];
int sum = 0;
int nr_of_elements;
void back(int lastElement)
{
if (sum == N)
{
for (int i = 0 ; i < nr_of_elements; i++)
std :: cout << sol[i] << " ";
std :: cout << "\n";
return ;
}
for ( int i = lastElement ; i <= N - sum ; i++)
{
sum += i;
sol[nr_of_elements++] = i;
back(i);
sum -= i;
nr_of_elements--;
}
}
int main ()
{
back(1);
return 0;
}
各数値について、それ以上の数値のみを確認する必要があります。例えば：
1 1 1 1
1 1 2
1 2 1 (not this, as the third 1 is less than is precedent 2)
1 3
2 1 1 (not this)
2 2
3 1 (not this)
4
Ionescu Robertsの回答のJavaバージョンは次のとおりです。
static Set<List<Integer>> getNums(int last, int target) {
Set<List<Integer>> toReturn = new HashSet<List<Integer>>();
if (target == 0) {
toReturn.add(new ArrayList<Integer>());
return toReturn;
}
for (int i = last; i <= target; i++) {
for (List<Integer> subSolution : getNums(i, target - i)) {
List<Integer> seq = new ArrayList<Integer>(subSolution);
seq.add(i);
toReturn.add(seq);
}
}
return toReturn;
}
この回答は、equals と hashcode をオーバーライドできる Java や C# などに適用されます。
最も簡単な方法は、2^N の可能な組み合わせを生成する既存のアルゴリズムを活用することですが、Set を使用して重複を排除するように微調整します。メソッドはすべての組み合わせの Set を返し、重複はありません。次に、2 つの重複する組み合わせを認識する方法を Set に指示する必要があります。リストを使用し、equals メソッドと hashcode メソッドをオーバーライドします。
組み合わせをリストに格納したい場合は、java.util.ArrayList をラップする UniqueList を呼び出しましょう。
class UniqueList {
ArrayList data = new ArrayList();
void add(Integer item) {
data.add(item);
}
//more wrapper calls if you want
@Override
public boolean equals(UniqueList anotherList) {
if (data.size() != anotherList.data.size()) return false
//only need to sort once in each list
Collections.sort(data);
Collections.sort(anotherList.data);
for (int i = 0; i < data.size(); i++) {
if (data.get(i) != anotherList.data.get(i)) return false
}
return true;
}
//optionally override hashcode for performance on hashtable
}
今、既存の生成アルゴリズムで、
Set<UniqueList<Integer>>
組み合わせのセットを保持するために、Set は組み合わせを許可する前に equals() メソッドを使用してチェックするため、重複がないことが保証されます。
繰り返しソートを避けるために、リストがすでにソートされているかどうかを示すブール値フラグを追加できます。つまり、重複をチェックする目的で、各リストを一度だけソートする必要があります。
このアプローチは明らかに最適ではありませんが、既存のアルゴリズムにプラグインして、最小限のコード変更で重複をゼロにすることができます。
特定の問題を解決するバックトラッキングのよりクリーンな実装 (アルゴリズム設計マニュアルを参照: ここで使用される同じテンプレート)。
#define V(x) vector<x >
typedef V(int) VI;
bool isSolutionReached(VI & input, VI & partial, int k,int data) {
if (k==data) return true;
return false;
}
void processSolution(VI & input,VI & partial, int k,int data) {
int sum=0,i=0;
for(i=0;i<=data;i++)
if(partial[i]!=0 ) {
sum+=i;
}
if(sum == k) {
for(i=0;i<=data;i++)
if(partial[i]!=0) cout <<i<<"\t";
cout <<"\n";
}
}
void constructNext(VI & input,VI & candidateVector,int k,int data) {
candidateVector.push_back(0);
candidateVector.push_back(1);
}
bool finished=false;
void backTrack(VI & inp, VI &partial, int k,int data ) {
VI candidateVector;
int i=0;
if( isSolutionReached(partial,inp,k,data)) {
processSolution(inp,partial,k,data);
}else {
k=k+1;
constructNext(inp,candidateVector,k,data);
for(i=0;i<candidateVector.size();i++) {
partial[k]=candidateVector[i];
backTrack(inp,partial,k,data);
}
}
}
int main() {
int n=5; //This is x+1
VI inp(5,0);
VI partial(5,0);
backTrack(inp,partial,0,n-1);
return 0;
}