並べ替えアルゴリズムの一種を開発しようとしています

Question

私はそれを正しく得ることができない次のputを開発したいと思います。 私はN長のベクトルを持っています。各要素は0からKになることができます。ここでNとKはユーザーによって与えられます。今私はすべての可能な解決策を歩くことができる関数を作成しようとしています。

Nが4でK = 2とすると、すべての置換（？）をループしたいとします。

私は、0000でベクトルを埋めることが、その後1000年にベクトルを埋めるテスト、それをテストしたい0100など

それは0100と0010が異なっていることを知っておくことが重要です。 1100と0011など

これはループが印刷する必要があります（すべての可能なシーケンスがすべて出現する限り、0001または1000は0000以降になります）。

0000、1000年、0100、0010、0001、1100、1010、1001、1110、1101、0111、0101、...、2012、2211など。

私は組み合わせを試してみましたforループは、実際にそれを得ることはできません。 アプリケーションは、C++

であるあなたがきちんとそれを行うにはrecursiveソリューションをお勧めします、TNX

Answer 1

を助けてください。
すべての可能性を最初の要素に置き、再帰的にサイズを小さくして呼び出します。

擬似コード：

permutations(int n, int k, solution): 
    if (n==0): //base clause 
     print solution //or append to some extra data structure 
     return 
    for (i = 0 ; i <= k ; i++): 
     solution.append(i) 
     permutations(n-1,k,solution) //recursive call 
     solution.removeLast() //clean up environment before moving to the next possibility 

はpermutations(n,k,v)と起動 - n、kあなたのパラメータであり、vが空std::vector

EDITある：C++コード：

void permutations(int n, int k,vector<int> &solution) { 
    if (n==0) { //base clause 
     print(solution); 
     return; 
    } 
    for (int i = 0 ; i <= k ; i++) { 
     solution.push_back(i); 
     permutations(n-1,k,solution); //recursive call 
     solution.pop_back(); //clean up environment before moving to the next possibility 
    } 
} 

を含むデモ関数が見つかりました​​3210

Answer 2

私はあなたが探している単語ではないと思います。あなたが一年生に

First value 0 0 0 0 
Add 1    1 
       ======= 
Second Value 0 0 0 1 
Add 1    1 
       ======= 
Third Value 0 0 1 0 

をしたとして、あなたはまた、長い手をやっていたのであれば、あなたはこのようにsomethignを行いたいだけのようなので、何がやりたいことは、本質的に、ベクトルをインクリメントされ、カウントの話をしています： 1000年、0100、1100、0010、1010、0110、1110、0001、1001、0101、1101、0011：

// returns false when you've seen all of the possible values for this vector 
bool increment(std::vector<int> & vector, int k) { 
    for (int i = 0; i < vector.size(); ++i) { 
    int j = vector[i] + 1; 
    if (j <= k) { 
     vector[i] = j; 
     return true; 
    } 
    else vector[i] = 0; 
    // and carry a 1 by looping back again 
    } 
    return false; 
} 

これは、0000ベクターで始めると仮定すると、k=1ために、次の順序で値を返します。 、1011、0111、1111. （2進数での絵画 - 私は単に数字を逆にして、普通のベクトルのビューをlefこのように右にトン。）

Answer 3

何かが私の心

bool increase(vector<int> &d, int index, int k){ 

    if(index == d.size()){ 
    return false; 
    } 

    if(d[index] == k){ 
    d[index] = 0; 
    increase(d, index+1, k); 
    }else{ 
    d[index]++; 
    } 

    return true; 
} 

void printvector(vector<int> v){ 
    cout<<" "; 
    for(int i=0;i<v.size();i++){ 
    cout<<v[i]; 
} 
} 

int main(){ 
//int N, K predefined, and initialised. 

    vector<int> D(N, 0); 

    do{ 
    printvector(d); 
    }while(increase(d, 0, K); 


}