Какая структура данных лучше всего подходит для итераций расположения строк?

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

Я знаю, что слишком наивный, AFAIK круговой список был бы лучшим выбором, может кто-нибудь реализовать то же самое более эффективно с помощью STL?

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

Возможно, есть способ переписать перестановку () с помощью функторов, но мой STL-фу ржавый.

Answer 2

Я считаю, что вы ищете алгоритм 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"

Answer 3

Лучшим решением является не структура данных, а алгоритм - см. next_permutation