試圖開發一種排列算法

我想開發下面的把不能得到它的權利。我有一個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++

請幫幫忙，TNX

來源

2012-02-20 Michiel

的命令是重要的？（例如1101必須在0002之前） – kennytm 2012-02-20 13:03:04

聽起來像，對於給定的N，K ...打印Base K + 1中的所有N位數字 – Pheonix 2012-02-20 13:06:06

也許你應該試試std :: next_permutation？看看http://stackoverflow.com/questions/4972470/what-is-the-time-complexity-of-stdnext-permutation-function-in-c – innochenti 2012-02-20 13:14:29

你可能需要一個recursive解決整齊地做到這一點。
將所有可能性放在第一個元素上，並遞減調用大小。

僞代碼：

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

編輯：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 
    } 
}

一演示包括print()功能可以找到3210

來源

2012-02-20 13:04:31 amit

非常感謝你，對於遲到的回覆感到抱歉。這適用於小問題，但是當我嘗試使用這個大問題時，遞歸不是要走的路。有人可以幫助做同樣的事情，但使用動態編程？ – Michiel 2012-03-20 12:54:18

@Michiel：不客氣。你所要求的所有排列組合都是指數數字，任何產生它們的算法都會遭受長時間運行的影響。 – amit 2012-03-20 12:56:08

我不認爲排列是你正在尋找的詞。你說的是計數，你想這樣做有什麼本質上是增加的載體，就像如果你是做加法長的手，你在一年級

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這樣做的：

// 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; 
}

這將在下面的順序返回值，k=1，假設在開始用該載體0000：1000，0100，1100，0010，1010，0110，1110，0001，1001，0101，1101，0011 ，1011，0111，1111. （圖片以二進制計數 - 我只是將每個數字都顛倒過來以適應我們對於向量的普通視圖，即從左到右噸至右側）

來源

2012-02-20 13:11:56

不錯:) one（）在溢出的情況下返回false。因此，while（increment（...））{...}遍歷所有排列 – Ben 2012-02-20 13:24:02

像這樣的事情在我腦海

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); 


}

來源

2012-02-20 13:13:52 Pheonix

試圖開發一種排列算法

回答

相關問題