列举所有的组合！
比如，有A、B、C三个字母。
那其组合就为：1 、A、B、C
2、AB、BA、AC、CA、BC、CB
3、ABC、ACB、BAC、BCA、CAB、CBA
[解决办法]
#include <vector>
#include <iostream>
#include <string>
using namespace std;
void generateStrings(vector <string> & result, string current, char c)
{
for(int i = 0; i <= current.length(); i++ ) {
string newString = current.substr(0,i) + c + current.substr(i, current.length()-i);
result.push_back(newString);
}
}
void addElement(vector <string> & result, char c)
{
int size = result.size();
for(int i = 0; i < size; i++) {
generateStrings(result, result[i], c);
}
}
int main()
{
string elements = "abc ";
vector <string> result;
result.push_back(elements.substr(0,1));
for(int i = 1; i < elements.size(); i++) {
addElement(result, elements[i]);
result.push_back(elements.substr(i,1));
}
for(int i = 0; i < result.size(); i++) {
cout < < result[i] < < " ";
}
cout < < endl;
}
[解决办法]
int a[20]={0};
char *p= "abcd ";
char c[20];
int n;
void fin(int k)
{
int i,j;
if(k> =n) return;
for(i=0;i <n;i++)
{
if(a[i]==0)
{ c[k]=*(p+i);
a[i]=1;
for(j=0;j <k+1;j++)
printf( "%c ",c[j]);
printf( " \n ");
fin(k+1);
a[i]=0;
}
}
return;
}
int main()
{
n=strlen(p);
n=3;
printf( "jkl\n ");
fin(0);
getch();
return 0;
}
[解决办法]
这实际上是一个组合+全排列的问题，列举所有可能时间复杂度很高
深搜可以解决，不过试了一下10个字符左右就要算好久了；要枚举所有可能，所以此深搜算法没有剪枝可能。
// 0002.cpp;
#include <stdio.h>
int idx[100], cn, max_depth;
void dfs(int depth, const char *pstr)
{
if (depth == max_depth){
for (int i = 0; i < cn; i ++){
printf( "%c ", pstr[idx[i]]);
}
printf( "\n ");
return;
}
for (int i = 0; *(pstr+i) != '\0 '; i ++){
for (int j = 0; j < cn && idx[j] != i; j ++);
if (j == cn){
idx[cn++] = i;
dfs(depth+1, pstr);
cn--;
}
}
}
int main(void)
{
char rgchar[100] = "ABC ";
for (int i = 1; *(rgchar+i-1) != '\0 '; i ++){
max_depth = i;
dfs(0, rgchar);
}
return 0;
}
