哪种数据结构最适合遍历字符串的排列?

Question

假设我们有字符串“ABCAD”，现在我们需要遍历这个字符串的所有可能排列，包括顺时针和逆时针方向。

我的丑陋实现如下：

string s = "ABCAD";
string t ="";
 for(int i = 0; i < sz(s); i++){
    t = s[i];
  for(int j = i+1; ; j++){
      if((j) == sz(s)){
         j = 0;
        }
       if(j == i){
          break;
        }
       t+= s[j];
     }
     cout<<t<<" ";
   }
reverse(all(s));
 for(int i = 0; i < sz(s); i++){
    t = s[i];
  for(int j = i+1; ; j++){
      if((j) == sz(s)){
         j = 0;
        }
       if(j == i){
          break;
        }
       t+= s[j];
     }
     cout<<t<<" ";
   }

输出：

AHSAU HSAUA SAUAH AUAHS UAHSA UASHA ASHAU SHAUA HAUAS AUASH

我知道这太幼稚了，我认为循环列表会是一个更好的选择，有人能否使用STL更有效地实现同样的事情？

- whacko__Cracko

---

如果你想要一个循环列表：https://dev59.com/_XNA5IYBdhLWcg3wdtv5 - kennytm

Answer 1

伪代码实现，我会这样做：

function rearrange (string s) {
  string t = s + s;
  for (int i = 0; i < length(s); ++i)
    print t.substring(i, length(s));
}

input = "ABCAD"

rearrange(input);
rearrange(reverse(input));

可能有一种使用函数对象重写rearrange()的方法，但我的STL技能有些生疏。

- Lars

---

是的，太好了 :) 你知道吗，我刚刚得到它，然后看到了你的回答 :) - whacko__Cracko

你可以通过一次对 rearrange 的调用来完成这个操作，代码如下：function rearrange (string s) { string t = s + s; string q = reverse(s) + reverse(s); for (int i = 0; i < length(s); ++i){ print t.substring(i, length(s)); print q.substring(i, length(s)); } } - whacko__Cracko

Answer 2

我相信你需要的是旋转算法。对于反转，你需要像在自己的代码中一样进行反转。

以下是未经测试的代码，可以实现与你的代码相同的功能：

std::string s = "ABCAD"

for (int i = 0; i < s.size(); ++i)
{
  std::cout << s << std::endl;
  std::rotate(s.begin(), s.begin() + 1, s.end());
}

reverse(s.begin(), s.end());

// same loop as above for reverse "arrangements"

- Peter Alexander

---

将for循环放入自己的函数中，我就买单了。 - Mark Ruzon

Answer 3

最佳解决方案不是数据结构而是算法 - 参见 next_permutation。

- anon

---

"ABCAD" 的全排列总数为 5!/2! = 60，但我只需要其中的 10 个。 - whacko__Cracko

@nthrgeek 您是指唯一的排列组合吗？如果是这种情况，请在生成时将每个排列组合保存在std::set中。 - anon

这只是所有顺时针和逆时针旋转 :) - whacko__Cracko

@nthrgeek，“方向”如何影响结果？如果我有“AB”，那么唯一可能的排列是“AB”和“BA”。 - anon

请使用下一个排列来解决这个问题，给我指点一下。 :) - whacko__Cracko