有重复元素的排列问题

1、有重复元素的排列问题一 问题描述 ：设 R=r1,r2, r n 是要进行排列的 n 个元素，其中 r1,r2 rn 元素可能相同，请设计出一个算法，列出 R 中元素的所有不同排列。 在给定的 n 以及待排列的 n 个元素，计算出这 n 个元素的所有不同排列。要求输入输出：输入：第一行是元素个数 n，1=n=15，接下来的 1行是待排列的 n 个元素，元素中间不要加空格。 输出：程序运行结束时，将计算出 n个元素的所有不用排列，最后 1 行中的数是排列总数。例如：Inputaaccoutputaacc acac acca caac caca ccaa三 设计概要：1）数据类型定义：int j=

2、0int n char list int k ； int m int flag定义 j 初始为 0，用来计数总共排列数 输入排列元素的个数 定义数组 list 存放排列元素 数组中元素第 k 位到第 m 位的排列 标识符2）程序流程图：void Perm(int k,int m)k=mY3）模块间的调用：四 详细算法设计：if ( 是否一个元素 )for( 寻找到该排列元素 ) printf( 输出该元素 ); 排列数加一else / 还有多个元素待排列，递归产生排列 for(从第 k 个直到第 m 个元素 ) flag=0;for(p=k;p<i;p+)if(listp=listi)f

3、lag=1;if(flag=1) continue; Swap(listk,listi); Perm(list,k+1,m); Swap(listk,listi);void Swap(char &a,char &b) 交换元素五 调试分析：1）在调试过程中主要遇到了一些简单的符号错误，其次就是在实现排列perm（）时，对元素是否重复的判断出现了问题；对符号方面的错误就只能是细心的去发现然后再修改，在排列元素重复上初时是对算法的实现 在这判断上考虑欠缺，导致再运行通过后进行测试时出现了和预期结果不同的情况，经思考后修改最终实现了 该算法。2）由于该程序的算法实现起来比较简单，对算

4、法的时间和空间要求也比较低，所以也无需再想去改进算法 的时空分析复杂度。3）在选用测试用例时，运用白盒测试法的覆盖来测试，选用了从1 个元素到多个元素，从全不相同元素到有重复元素等来进行测试，所以测试用例应该得当。4）在进行调试时，遇到最多的首先就是小小的符号问题出错误，比如漏了分号，中英符号混了，从而出现 了编译错误，这告诉我平时编写代码时要养成良好的习惯，例如在符号问题，大括号问题等；其次就是程序上 出现了问题，包括了对算法考虑得不周全，例如边界问题等等；有时会出现修改了某处错误，但新的错误又出 现了，所以在调试过程中，应首先避免了符号上的错，然后再从全局上先去考虑下出错原因，再根据出错点

5、进 行修改。六 测试结果：4七 源程序：#include"stdio.h"int j=0;void main() /main 函数，调用 swap 和 perm int n;void Swap(char &a,char &b);void Perm(char list,int k,int m); scanf("%d",&n);char list16;scanf("%s",list);Perm ( list, 0, n-1);printf("%dn",j);void Swap(char &

6、;a,char &b) / 交换元素char temp =a;a=b;b=temp;m 的所有排列void Perm(char list,int k,int m)/产生 listk ： int i,p;int flag;void Swap(char &a,char &b);if(k=m) / 只剩下一个元素 for( i = 0;i <= m;i+) printf("%c",listi); j+; printf("n");else / 还有多个元素待排列，递归产生排列for(i=k;i<=m;i+) flag=0;for(p=k;p<i;p+)if(li