Which is the best data-structure for iterating through arrangements of a string?

Question

Lets say, we have string "ABCAD", now we need to iterate through all possible arrangement of this string in both clockwise and counter-clockwise direction.

My ugly implementation looks like this:

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

Output:

AHSAU HSAUA SAUAH AUAHS UAHSA UASHA ASHAU SHAUA HAUAS AUASH

I know that too naive,AFAIK a circular list would be a better choice, could somebody implement the same thing more efficiently using STL ?

Answer 1

The best solution is not a data structure but an algorithm - see next_permutation

Answer 2

In pseudocode, I'd go this route:

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

There's probably a way to rewrite rearrange() using functors, but my STL-fu is rusty.

Answer 3

I believe what you are looking for is the rotate algorithm. For the reverse ones, you'll need to do the reverse as you did in your own code.

Untested code to do what yours does:

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"