有重复元素,i=0 链表used=∧ a[i]=a,不在表used中，将该元素添加到used中，并调用调用 a[k+1:m]的全排列 k=0,i=1 链表used=a∧ a[i]=a, 在表used中找到，说明以a[i]为前缀的排列已经输出。
有重复元素的排列问题
k=0,i=2 链表used=a∧ a[i]=b,不在表used中，将该元素添加到used中，并调用调用 a[k+1:m]的全排列 k=0,i=3 链表used=ab∧ a[i]=c, 不在表used中，将该元素添加到used中，并调用调用 a[k+1:m]的全排列 k=0,i=4 链表used=abc∧ a[i]=c, 在表used中找到，说明以a[i]为前缀的排列已经输出。
算法实现
#include <list> void perm(char list[],int k,int m) { if(k==m) //当只剩下一个元素时则输出 { count++; for(int i=0;i<=m;i++) printf("%c",list[i]); putchar('\n'); } for(int i=k;i<=m;i++) //还有多个元素待排列，递归产生排列 { if(finish(list,k,i)) { swap(list[k],list[i]); perm(list,k+1,m); swap(list[k],list[i]); }}}
R全排列递归算法：
定义过程：void perm(char a[],int k,int m)。在过程中将 a[k:m]中的每个元素分别与a[k]中的元素交换，然后递归调 用a[k+1:m]的全排列，并将计算结果做a[0:k]为的后缀。
有重复元素的排列问题
重复元素的解决方法：
由于a[k:m]中各元素可能相同，因此在与a[k]中的元 素交换之前要先判断该元素是否已经使用过。本算法 采用链表来存储各位元素的使用情况。
有重复元素的排列问题
有重复元素的排列问题
问题描述：
设R={r1,r2,…,rn}是要进行排列的n个元素，其中 r1,r2,…,rn可能相同。试设计一个算法，列出R的所有不 同排列。
编程任务：
给定以及待排列的个元素。计算出这个元素的所 有不同排列。
有重复元素的排列问题
R全排列归纳定义：
当n=1时，Perm(R)=(r)，其中r是集合R中唯一的元素； 当n>1是，Perm(R)由(r1)Perm(R1)，(r2)Perm(R2) ，…， (rn)Perm(Rn)构成。其中Ri=R-{ri}，(ri) Perm(Ri) 表示在 全排列Ri的每一个排列前加上前缀ri得到的排列。
结果截图