C|字符串排列组合算法
第二个算法是我笔试题遇到的，当时没有做出来，在网上看到别人写的算法，感觉太精妙了，就在这里分享出来。
全排列 所谓全排列，就是打印出字符串中所有字符的所有排列。例如输入字符串abc，则打印出 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba 。
#include
#includestatic int number=0;
void Swap(char *a ,char *b)
{
char temp = *a;
*a = *b;
*b = temp;
}void AllRange(char* str,int start,int length)
{
if(start == length-1)
{
printf("%s\n",str);
number++;
}
else
{
for(int i=start;
i<=length-1;
i++)
{
Swap(&str[start],&str[i]);
AllRange(str,start+1,length);
Swap(&str[start],&str[i]);
}
}
}void Permutation(char* str)
{
if(str == NULL)
return;
AllRange(str,0,strlen(str));
}void main()
{
char str[] = "abcde";
Permutation(str);
printf("number=%d\n",number);
}
全组合
如果不是求字符的所有排列，而是求字符的所有组合应该怎么办呢？还是输入三个字符 a、b、c，则它们的组合有
a b c ab ac bc abc。当然我们还是可以借鉴全排列的思路，利用问题分解的思路，最终用递归解决。不过这里介绍一种比较巧妙的思路 —— 基于位图。假设原有元素 n 个，则最终组合结果是 2n?1 个。我们可以用位操作方法：假设元素原本有：a,b,c 三个，则 1 表示取该元素，0 表示不取。故取
a则是001，取ab则是011。所以一共三位，每个位上有两个选择 0 和 1。而000没有意义，所以是2n?1个结果。这些结果的位图值都是 1,2…2^n-1。所以从值 1 到值 2n?1 依次输出结果：
001,010,011,100,101,110,111 。对应输出组合结果为：a,b,ab,c,ac,bc,abc。因此可以循环 1~2^n-1，然后输出对应代表的组合即可。有代码如下：
#include
#includestatic int number=0;
void Combination(char *str)
{
if(str == NULL)
return ;
int len = strlen(str);
int n = 1<反转字符串 main.c
【C|字符串排列组合算法】
#include
#includevoid print(char *str)
{
if(*str!='\0')print(str+1);
if(*str!='\0')
printf("%c",*str);
}int main(int argc,char **argv)
{
char *buff="hello world";
print(buff);
printf("\n");
return 0;
}
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一起来学习C语言的字符串转换函数
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- 字符串拼接成段落，换行符（\n）如何只执行n-1次
- C语言的版本比较
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解