What is the best data structure to iterate through row layout?

Question

Let's say that we have the string "ABCAD", now we need to iterate all possible location of this string both clockwise and counterclockwise.

My ugly implementation is as follows:

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

Conclusion:

AHSAU HSAUA SAUAH AUAHS UAHSA UASHA ASHAU SHAUA HAUAS AUASH

I know that a too naive, AFAIK circular list would be a better choice, can someone more effectively implement the same with STL?

Answer 1

In pseudo code, I would go along 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 is probably a way to rewrite the reordering method () using functors, but my STL-fu is rusty.

Answer 2

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

Answer 3

I believe you are looking for a rotate algorithm. For reverse, you need to do the opposite, as it was in your own code.

Unverified code to complete your actions:

 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"