Рекурсивный алгоритм C++ для перестановки

Question

Функция permute() работает в бесконечном цикле, и я не могу найти почему? Я попытался проверить функцию, удалив рекурсивный вызов и, похоже, работает нормально. У меня также есть базовый случай, поэтому не знаю, где проблема.

#include <iostream> 
#include <string> 
#include <vector> 

using namespace std; 

string smallString(string s, int k){ // computes a string removing the character at index k 
    int i,j; 
    string res; 
    for(i=0,j=0;j<s.length();i++,j++){ 
     if(i==k){j++;} 
     res.push_back(s[j]); 
    } 
return res; 
} 
void permute(string s1, string s2, size_t len){ 
    if(len==1) 
     {cout<<"length is equal to 1"<<(s1+s2)<<'\n'; return;} //base case 
    else{ 
     for(int i =0;i<len;i++){ 
      string temp= s2.substr(i,1); 
      s1.append(temp); 
      string fin = smallString(s2,i); 
      //cout<<temp<<'\t'<<s1<<'\t'<<fin<<'\t'<<fin.length()<<'\n'; 
      permute(s1,fin,fin.length()); 
      s1.erase((s1.length()-1)); 
      //cout<<"printing s1 : "<<s1<<'\n'; 
     } 
    } 
} 

int main(){ 
    string s2="abc"; 
    string s1=""; 
    permute(s1,s2,s2.length()); 
    return 0; 
} 

Answer 1

Ваша проблема, кажется, в функции «smallString». В этой функции OutOfRange используется в s [j]. Я поставил печать как

for(i=0,j=0;j<s.length();i++,j++) 
{ 
    if(i==k){j++;} 
     cout<<"smallString:: s ::"<<s<<'\t'<<"k::"<<k<<'\n'; 
    res.push_back(s[j]); //Problem is here... 
} 

Теперь выход печать как

smallString :: s :: а к :: 0

smallString :: s :: а к :: 0

smallString :: s :: Ьс к :: 0

smallString :: s :: Ьс к :: 1

smallString :: s :: Ьс к :: 1

smallString :: с :: б к :: 0

smallString :: с :: б к :: 1

smallString :: с :: б к :: 1 . .

Итак, в какой-то момент это происходит как «s :: b k :: 1», поэтому вы выбираете символ в позиции 1 из строки «b».

Строка - это в основном массив символов, начинающийся от 0 до (n-1). Для строки «b» только 0-я позиция имеет символ «b». но мы обращаемся к несуществующей позиции.

Таким образом, он выдает ошибку и начинает непрерывный цикл отсюда.

FIX ДЛЯ ВЫПУСКА:

for(i=0,j=0;j<s.length();i++,j++) 
{ 
    if(i==k) 
    { 
     j++; 
    } 
    else 
    { 
     cout<<"smallString:: s ::"<<s<<'\t'<<"k::"<<k<<'\n'; 
     res.push_back(s[j]); 
    } 
}