按字典顺序打印给定字符串的所有字母组合的算法 [英] Algorithm to print all combination of letters of the given string in lexicographical order
问题描述
我试图创建代码以按字典顺序生成给定字符串的所有可能组合:
I tried to create the code to generate all possible combination of the given string in the lexicographical order:
我写的代码是:
void get(char *n)
{
int l=strlen(n);
sort(n,n+l);
int k=0,m,i,j,z;
while(k<l)
{
m=k;
for(i=k;i<l;i++)
{
for(j=k;j<=i;j++)
cout<<n[j];
cout<<"\n";
}
for(z=m+2;z<l;z++)
cout<<n[m]<<n[z]<<"\n";
k++;
}
}
int main()
{
char n[100];
cin>>n;
get(n);
return 0;
}
假设字符串为:abcde
Suppose the string is : abcde
我的代码未生成如下组合:
My code is not generating combinations like:
abd
abe
我得到的字符串abcde的输出是:
The output I am getting for the string abcde are:
a
ab
abc
abcd
abcde
ac
ad
ae
b
bc
bcd
bcde
bd
be
c
cd
cde
ce
d
de
e
我的输出不包含类似abd abe
希望这可以使问题更清楚
Hope this makes the question clear
如何使用有效的算法生成所有这些组合
How to generate all these combinations using an efficient algorithm
推荐答案
这是一种简单的递归方法:
This is a simple recursive approach:
#include <string>
#include <iostream>
using namespace std;
void get( string str, string res ) {
cout << res << endl;
for( int i = 0; i < str.length(); i++ )
get( string(str).erase(i,1), res + str[i] );
}
int main( int argc, char **argv) {
string str = "abcde";
get( str, "" );
return 0;
}
也许不是最有效的方法,而是一种简短的方法.请记住,枚举所有组合的复杂度始终为 O(2 n ) .因此根本没有高效的算法.
Maybe not the most efficient way of doing it, but a short and simple one. Keep in mind, that enumerating all combinations has a complexity of O(2n) anyway. So there exists no efficient algorithm at all.
这篇关于按字典顺序打印给定字符串的所有字母组合的算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!