C ++ recursive algorithm for permutation
The permute () function runs in an infinite loop and I can't find why? I tried to test the function by removing the recursive call and it seems to work fine. I also have a base case so I don't know where the problem is.
#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;
}
source to share
Your problem seems to be in the "smallString" function. In this function, OutOfRange is used in s [j]. I type like
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...
}
Now the output is output as
smallString :: s :: abc k :: 0
smallString :: s :: abc k :: 0
smallString :: s :: bc k :: 0
smallString :: s :: bc k :: 1
smallString :: s :: bc k :: 1
smallString :: s :: bk :: 0
smallString :: s :: bk :: 1
smallString :: s :: bk :: 1,.
So at some point in time it comes up as "s :: bk :: 1", so you select the character at position 1 from string "b".
The string is basically a char array that starts from 0 to (n-1). For string "b", only the 0th position has the character "b". but we are referring to a non-existent position.
So it throws an error and starts a continuous loop from here.
FIX FOR YOUR QUESTION:
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]);
}
}
source to share