代码之家 › 专栏 › 技术社区 › whacko__Cracko

哪种数据结构是迭代字符串排列的最佳数据结构?

data-structures stl c++

whacko__Cracko · 技术社区 · 15 年前

比如说,我们有字符串“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<<" ";
   }

输出:

阿苏哈萨索亚奥哈斯阿拉伯联合酋长国乌沙阿苏绍阿豪厄斯奥什

我知道太天真了,一个循环列表会是一个更好的选择,有人能更有效地使用STL实现相同的事情吗?

3 回复 | 直到 15 年前

Lars 15 年前

在伪代码中,我走这条路:

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

可能有一种方法可以使用函数重写remark(),但是我的stl-fu已经生锈了。

anon 15 年前

最好的解决方案不是数据结构,而是算法-参见 next_permutation

Peter Alexander 15 年前

我相信你要找的是 rotate 算法。对于反向的,您需要像在自己的代码中那样执行反向操作。

执行您的操作的未测试代码:

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"

推荐文章

AstralHex · 矩阵乘法代码工作不正常

4 月前

Baba Dan Constantin · SSE4.1在矩阵4x4乘法上比SSE3慢?

4 月前

Giogre · 为包含许多数值字段的简单“struct”重载比较运算符

4 月前

einpoklum · 定义一个并不真正提供now()函数的std::chrono Clock是“合法的”吗?

4 月前

Fishie · 作为类成员的智能指针是否仍然自动释放?[关闭]

4 月前

Die4Toast · 递归调用成员箭头运算符->

4 月前

Angle.Bracket · 如何用C++将UTF-8文件名写入MS Windows控制台?

4 月前

Anka HanÄ±m · 关于结构和动态数组地址的问题

4 月前

Adam Barnes · 我如何定义一个基于constexpr函数返回值进行限制的概念?

4 月前

user2138149 · 为什么我不能获取包含多个元素的结构体中某些元素的地址?[副本]

4 月前