編寫一個置換函數

Question

我被要求寫一個使用遞歸的置換函數。該函數的唯一參數應該是我應該找到所有排列的字符串。該函數應該返回一個具有所有可能排列的向量。我知道我可以在STL算法中使用next_permutation，但我被要求不要。

我有基礎案例設置，我知道我需要一個for循環，但我不太確定從那裏去哪裏。有人能指引我朝着正確的方向嗎？

vector <string> getPerm(string str) 
{ 
    vector<string> v; 
    if(w.length() <= 1) 
    { 
     v.push_back(str); 
     return v; 
    } 
    else 
    { 
     for(int i = 0; i < str.size(); i++) 
     { 
      //Some code 
     } 
    } 
} 

任何幫助，將不勝感激。

Answer 1

想象一下，您已經獲得了前一次函數迭代的結果，並返回字符串中前n-1個元素的所有排列。

vector<string>& v_prev = getPerm(str.substr(0, str.length()-1)); 

使用這個在你的代碼的

//Some code 

一部分。

另一個提示：使用0長度的字符串作爲遞歸的停止條件。可以遞歸地構建1- lenght置換;）

這裏是整個解決方案：

vector<string> getPerm(string str) 
{ 
    vector<string> v; 
    if (str.empty()) 
    { 
    v.push_back(string()); 
    return v; 
    } 
    else 
    { 
    vector<string>& v_prev = getPerm(str.substr(0, str.length()-1)); 
    for(int i = 0; i < v_prev.size(); i++) 
    { 
     for (int j = 0; j < v_prev[i].length() + 1; j++) 
     { 
     string p = v_prev[i]; 
     p.insert(j, str.substr(str.length() - 1, 1)); 
     v.push_back(p); 
     } 
    } 
    return v; 
    } 
} 

Answer 2

想想字符串的這些排列「123」

123 
132 

213 
231 

312 
321 

想想看「12」的這些排列

12 
21 

你能看到你將如何構建一個n字母的排列字符串，如果你知道所有n-1字母子串的排列組合。這種解決方案將是遞歸的。

Answer 3

• 對於每一個元素x在yourArray
  • 使yourArray副本而未元素x。致電此新陣列newArray。
  • 找到所有newArray
  • add元素x的排列到每臺排列

Answer 4

的開始嘗試是這樣的：

permut(s) : 
    if s.length=0 : exit; 
    else : 
    for i=0 to s.length : 
     front:=s[i]; 
     remove(s,i); 
     s2 := front + permut(s); 
     print s2, NEWLINE; 

Answer 5

實現什麼只是肯·布魯姆寫道：

vector <string> getPerm(string str) 
{ 
    vector<string> v; 
    if(str.length() <= 1) 
    { 
    v.push_back(str); 
    return v; 
    } 
    else 
    { 
    for(int i = 0; i < str.size(); i++){ 
     vector<string> perms = getPerm(str.substr(0,i)+str.substr(i+1)); 

     for(int j = 0; j < perms.size(); j++){ 
     v.push_back(str[i] + perms[j]); 
     } 
    } 
    } 
}