C语言怎么实现有重复元素的全排列

一、C语言怎么实现有重复元素的全排列

1、整体思路就是利用回溯的思想，也可认为是深度优先搜索

2、从字符串第一位idx=0开始，每次递归都从s[idx]之后选择一个字符与s[idx]交换

3、因为可能有重复字符，可使用哈希数组标记当前循环每个字符是否被选择

4、因为字符范围不超过ASCII码，所以使用128空间的数组足够用来标记了

5、选择好当前字符s[i]并与s[idx]交换之后，递归调用继续排列下一位s[idx+1]

6、注意这里要进行回溯，即不选s[i]而选择之后的某个字符交换到s[idx]

7、所以要将之前的s[i]与s[idx]交换过来，恢复原状，才能循环判断下一个选择

8、#define MAXN 1000000//排列总数可能很多

9、char*res[MAXN]={NULL};//指针数组保存排列结果

10、void swap(char*x, char*y){//交换两个字符变量的内容

11、void perm(char*s, int n, int idx){//回溯产生字符串全排列

12、 if(idx== n){//已排列到字符串结尾

13、 res[num]=(char*)malloc(sizeof(char)*(n+ 1));

14、//printf("%s\n", s);//输出当前排列

15、 strcpy(res[num], s);//保存当前排列

16、 int i, hash[128]={0};//哈希数组，标记每个字符是否被选择

17、 continue;//跳过已被标记过的重复字符

18、 hash[s[i]]= 1;//选过的话在数组中标记为1

19、 swap(&s[idx],&s[i]);//选择s[i]交换到s[idx]

20、 perm(s, n, idx+ 1);//递归，继续s[idx+1]的选择

21、 swap(&s[idx],&s[i]);//回溯，当前不选择s[i]，而选择其他字符

22、 char*s=(char*)malloc(sizeof(char)*(n+ 1));

23、 printf("一共有%d种排列:\n", num);//输出排列总数

24、 for(i= 0; i< num; i++){//输出所有排列

二、C语言如何实现有重复元素的全排列

1、在递归里面用交换的方式获取全排列，从第一个开始，不断与后面数交换，当然递归时不要忘记在后面写个换回来的语句。只要加个交换条件就可以了，在不相等时交换，相等时不交换。

2、当前阶段，在编程领域中，C语言的运用非常之多，它兼顾了高级语言和汇编语言的优点，相较于其它编程语言具有较大优势。计算机系统设计以及应用程序编写是C语言应用的两大领域。同时，C语言的普适较强，在许多计算机操作系统中都能够得到适用，且效率显著。

3、C语言拥有经过了漫长发展历史的完整的理论体系，在编程语言中具有举足轻重的地位。

4、C语言是普适性最强的一种计算机程序编辑语言，它不仅可以发挥出高级编程语言的功用，还具有汇编语言的优点，因此相对于其它编程语言，它具有自己独特的特点。具体体现为以下三个方面：

5、其一，广泛性。C语言的运算范围的大小直接决定了其优劣性。C语言中包含了34种运算符，因此运算范围要超出许多其它语言，此外其运算结果的表达形式也十分丰富。此外，C语言包含了字符型、指针型等多种数据结构形式，因此，更为庞大的数据结构运算它也可以应付。

6、其二，简洁性。9类控制语句和32个关键字是C语言所具有的基础特性，使得其在计算机应用程序编写中具有广泛的适用性，不仅可以适用广大编程人员的操作，提高其工作效率，同时还能够支持高级编程，避免了语言切换的繁琐。

7、其三，结构完善。C语言是一种结构化语言，它可以通过组建模块单位的形式实现模块化的应用程序，在系统描述方面具有显著优势，同时这一特性也使得它能够适应多种不同的编程要求，且执行效率高。

三、c语言排列组合c语言排列组合

1、只要C的上面是0，不管下面是什么都等于1。

2、分子是从5开始递减的两个数字相乘，即5*4；分母为从1开始递增的两个数字，即1*2；所以结果为5*4÷(1*2)=10;

3、从n个不同元素中，任取m(m≤n,m与n均为自然数,下同）个不同的元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数。

4、组合的定义：从n个不同元素中，任取m(m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m)表示。

5、其他排列与组合公式从n个元素中取出m个元素的循环排列数=A(n,m)/m=n!/m(n-m)!. n个元素被分成k类，每类的个数分别是n1,n2,...nk这n个元素的全排列数为 n!/(n1！×n2！×...×nk!). k类元素，每类的个数无限，从中取出m个元素的组合数为C(m+k-1,m）。

6、参考资料来源：百度百科-排列组合