c++ - 编写置换函数

Question

我被要求编写一个使用递归的置换函数。该函数的唯一参数应该是我应该找到所有排列的字符串。该函数应返回具有所有可能排列的向量。我知道我可以next_permutation在 STL 算法中使用，但有人要求我不要这样做。

我已经设置了基本案例，并且我知道我需要一个 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 长度排列；)

这是整个解决方案：

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
  • 将元素添加x到每个排列的开头

Answer 4

实施 Ken Bloom 刚刚写的：

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

Answer 5

尝试这样的事情：

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;