首页 / 算法 / 算法学习——求有重复元素的全排列(递归)
算法学习——求有重复元素的全排列(递归)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法学习——求有重复元素的全排列(递归),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2818字,纯文字阅读大概需要5分钟。
内容图文
算法学习——求有重复元素的全排列(递归)
思路:看到这个题目首先能想到的一点就是:①我们要求元素的所有全排列②我们要对求出的全排列去重
第一步:求全排列,这里先讨论对不含重复元素的数组元素进行全排列,用递归方法怎么实现叻
思考这样一种方法:假如我们要求1,2,3,4的全排列,我们可以把1放到前面来,求2,3,4的全排列,之后把2放到前面,求1,3,4的全排列,之后把3放到前面,求1,2,4的全排列,然后把4放到前面来求1,2,3的全排列;这是外层循环,就是遍历每个数,将该数与第一个位置的数交换然后求得余下所有数的全排列,而余下的数的全排列也可以用该种方法求得,当递归到只剩一个数,无法再求其全排列时,递归就有了出口,此时就可以输出了。注意:当我们把1放到前面来,求得剩下所有数的全排列后输出结束,我们需要将1还放回原位置,然后继续将2放到前面来......
void perm(char list[],int k,int m)
{
if(k==m) //当只剩下一个元素时则输出
{
count++;
for(int i=0;i<=m;i++)
cout<<list[i];
cout<<endl;
}
for(int i=k;i<=m;i++) //还有多个元素待排列,递归产生排列
{
swap(list[k],list[i]);
perm(list,k+1,m);
swap(list[k],list[i]);
}
}
第一步完成后,思考第二步,如何给得到的结果去重呢?
我们求全排列时,是往前提一个数,求余下的数的全排列,假如我们有这样一组数:1,2,3,1,4,如何求全排列呢?实际上只要稍加思考就可以看出,依照上面的方法,两个1分别移到前面求剩下的数的全排列的效果一样,这就产生了重复,所以当1已经在之前求过全排列的话,后面那个1就不用再求了,这样就达到了去重的目的。
我们添加一个条件判断该数是否在之前使用过。
int finish(char list[],int k,int i)
{//第i个元素是否在前面元素[k...i-1]中出现过
if(i>k)
{
for(int j=k;j<i;j++)
if(list[j]==list[i])
return 0;
}
return 1;
}
void perm(char list[],int k,int m)
{
if(k==m) //当只剩下一个元素时则输出
{
count++;
for(int i=0;i<=m;i++)
cout<<list[i];
cout<<endl;
}
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]);
}
}
}
这样就可以实现带有重复元素的数组求全排列了!
完整代码如下
#include <iostream>
using namespace std;
int count=0;
void swap(char &a,char &b)
{
char temp;
temp=a;
a=b;
b=temp;
}
int finish(char list[],int k,int i)
{//第i个元素是否在前面元素[k...i-1]中出现过
if(i>k)
{
for(int j=k;j<i;j++)
if(list[j]==list[i])
return 0;
}
return 1;
}
void perm(char list[],int k,int m)
{
if(k==m) //当只剩下一个元素时则输出
{
count++;
for(int i=0;i<=m;i++)
cout<<list[i];
cout<<endl;
}
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]);
}
}
}
int main()
{
int i,n;
cout<<"请输入元素个数: "<<endl;
cin>>n;
cout<<"请输入待排列的元素: "<<endl;
//getchar();
char *a=new char[n];
for(i=0;i<n;i++)
cin>>a[i];
cout<<"所有不同排列为: "<<endl;
perm(a,0,n-1);
cout<<"排列总数为: "<<count<<endl;
return 0;
}
最后,加一个容易理解的小视频(这个up讲的太好了,我一个笨蛋都听懂了,供大家学习交流):https://www.bilibili.com/video/BV1dx411S7WR
wish you have a good day!
内容总结
以上是互联网集市为您收集整理的算法学习——求有重复元素的全排列(递归)全部内容,希望文章能够帮你解决算法学习——求有重复元素的全排列(递归)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。