用于排列的 C++ 递归算法 [英] C++ recursive algorithm for permutation
问题描述
permute() 函数陷入无限循环,我似乎找不到原因?我尝试通过删除递归调用来检查函数,它似乎工作正常.我也有基本情况,所以不知道问题出在哪里.
The permute() function runs into an infinite loop and I can't seem to find why? i tried checking the function by removing the recursive call and it seems to be working fine. I also have the base case, so don't know where is the problem.
#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;
}
推荐答案
您的问题似乎出在smallString"函数上.在该函数中,OutOfRange 用于 s[j].我把打印像
Your problem seems to be in the "smallString" function. In that function, OutOfRange is used in s[j]. I put print 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...
}
现在输出打印就像
smallString:: s ::abc k::0
smallString:: s ::abc k::0
smallString:: s ::abc k::0
smallString:: s ::abc k::0
smallString:: s ::bc k::0
smallString:: s ::bc k::0
smallString:: s ::bc k::1
smallString:: s ::bc k::1
smallString:: s ::bc k::1
smallString:: s ::bc k::1
smallString::s ::b k::0
smallString:: s ::b k::0
smallString:: s ::b k::1
smallString:: s ::b k::1
smallString:: s ::b k::1..
smallString:: s ::b k::1 . .
因此,在某个时间点它是s ::b k::1",因此您要从字符串b"中选择位置 1 处的字符.
So, At one point of time it comes as "s ::b k::1" so you are selecting the character at the position 1 from the string "b".
String 基本上是一个从 0 到 (n-1) 的字符数组.对于字符串b",只有第 0 个位置具有字符b".但我们正在访问一个不存在的职位.
String is basically an char array which start from 0 to (n-1). For string "b" only 0th position is having character 'b'. but we are accessing an non-existing position.
所以它抛出错误并从这里开始连续循环.
So it throws error and start looping continuously from here.
解决您的问题:
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]);
}
}
这篇关于用于排列的 C++ 递归算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!