字符串的排列与组合问题
排列问题
问题描述:已知字符串的中字符是互不相同的,求所有可能的字符排列。例如输入序列ab,则得到的所有可能序列应当为aa、ab、ba、bb思路:此题目可以采用递归的思想,由于所有可能排列的位数均是n位,可以利用一个长度为n的数组array[]来存放最终要输出的结果,并以array_pos表示数组中存放的字符下标,当array_pos==len时,输出array的值。由于含有n个字符的字符串,满足条件的排列共有n^n个,因此在递归当中需要用到一个for循环。
设f(str,array,len,pos)为输出可能的排列序列的函数,则递归模型如下:
终止条件:f(str,array,len,pos) ≡ {输出符合条件的排列;
return}若len==array_pos
递归主体:f(str,array,len,pos) ≡ {将str中对应的字符暂存到array中;
f(str,array,len,pos+1)}若len ≠ array_pos
#include
using namespace std;
void Permutation(const char *str,char array[],int len, int array_pos) {
if (len == array_pos) {
for (int i = 0;
i < len;
i++)
cout << array[i];
cout << endl;
return;
}
for (int j = 0;
j < len;
j++) {
array[array_pos] = str[j];
Permutation(str, array, len, array_pos+1);
}
}
int main()
{
const char* str = "abc";
char* array = new char[3];
int length = strlen(str);
Permutation(str, array, length, 0);
return 0;
}
时间复杂度:O(n^n),空间复杂度:O(n)
组合问题
【字符串的排列与组合问题】问题描述:已知字符串中的字符是互不相同的,编写程序输出字符串的任意组合,例如给定abc,则任意组合为a、b、c、ab、ac、bc、abc解法一:此题目可以采用递归的方式进行处理,对于n个字符中,取m个字符的排列,可分为如下两种情况
情况①:将第1个元素保留,并在剩余的n-1个元素中选取m-1个元素进行组合
情况②:跳过第1个元素,在剩余的n-1个元素中选取m个元素进行组合
设f(str,buf,num)为输出任意组合的函数,则递归模型如下:
终止条件:f(str,buf,num) ≡ {输出buf;return}
若num==0【在n个元素中,能够找到符合条件的m个字符组成的组合】
f(str,buf,num) ≡ {不做任何事情,直接return}
若*str=='\0'【在n个元素中,找不到符合条件的m个字符组成的组合】
递归主体:f(str,buf,num) ≡ {将str中的字符暂存至buf中;
f(str+1,buf,num-1)}对应情形1
f(str,buf,num) ≡ {将buf中的字符删除;
f(str+1,buf,num)} 对应情形2
#include
#include
using namespace std;
void output(vector buffer) {
for (vector::iterator iter = buffer.begin();
iter != buffer.end();
iter++)
cout << *iter;
cout << endl;
}
void Combination(const char* str,vector &buffer,int num) {
if (num == 0) {
output(buffer);
return;
}
if (*str == '\0')
return;
buffer.push_back(*str);
Combination(str + 1, buffer, num - 1);
buffer.pop_back();
Combination(str + 1, buffer, num);
}
int main(){
vector buffer;
char str[] = "abc";
int length = sizeof(str) / sizeof(char);
for (int i = 1;
i < length;
i++)
Combination(str, buffer, i);
return 0;
}
解法二:利用位运算
对于n个字符的字符串,其可能的组合有2^n-1种,以abc为例,则利用二进制进行表示,用1表示字符输出,0表示字符不被输出,则所有可能的结果均可表示为a(100)、b(010)、c(001)、ab(110)、ac(101)、bc(011)、abc(111)
#include
using namespace std;
void Combination(const char* str,int len) {
for (int i = 1;
i < (1 << len);
i++) {//1<
参考资料:《编程之法—面试和算法心得》习题
推荐阅读
- 热闹中的孤独
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 放屁有这三个特征的,请注意啦!这说明你的身体毒素太多
- 一个人的旅行,三亚
- 布丽吉特,人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事,我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量