今天主要是想回忆下DFS,所以就那全排列开刀了,自己写了一个发现网上的解法真不错就想总结下:
一、利用DFS实现(自己写的)
废话就不说了 上代码:
#include <iostream>
#include <cstdio>
using namespace std;
const int size = 20;
bool visited[20];
int arr[20];
int n;
void dfs(int cnt)
{
if( cnt == n)
{
for(int i = 0; i < n; ++i)
{
cout << arr[i] << " " ;
}
cout << endl;
}
else
{
for(int i = 1; i <= n; ++i )
{
if(!visited[i])
{
arr[cnt] = i;
visited[i] = 1;
dfs(cnt+1);
visited[i] = 0;
}
}
}
}
int main()
{
while(cin>>n)
{
memset(visited, 0, sizeof(visited));
dfs(0);
}
return 0;
}
这种方法,我没有想好怎么实现含有相同元素的全全排列
二、利用递归实现,其实还是DFS,只是实现的方法不一样,但是它能够实现含有相同元素的全排列
下面给一段网上找的解释,其实王晓东的那本《算法与设计》有这个:
令E={e1,e2...en}表示n个元素的集合,我们的目标是生成该集合的所有排列方式。令Ei为E中移去元素i以后所获得的集合,perm(X)表示集合X中元素的排列方式,ei.perm(X)表示在perm(X)中的每个排列方式的前面均加上ei以后所得到的排列方式。例如,如果E={a,b,c},那么E1 = {b,c},perm(E1) = (bc,cb),e1.perm(E1) = (abc,acb)。
对于递归的基本部分,采用n=1。当只有一个元素时,只可能产生一种排列方式,所以perm(E) = (e),其中e是E中的唯一元素。当n>1时,perm(E) = e1.perm(E1) + e2.perm(E2)+ e3.perm(E3)+.......+en.perm(En)。这种递归定义形式是采用n个perm(X)来定义perm(E),其中每个X包含n-1个元素。至此,一个完整的递归定义所需要的基本部分和递归部分都已完成。
下面给出我自己写的代码:
#include <iostream>
#include <cstdio>
using namespace std;
template<class T>
void sswap(T &a, T &b)
{
if( a != b )
{
int tmp = a;
a = b;
b = tmp;
}
}
template<class T>
void Perm(T list[], int k, int m)
{
if(k == m)
{
for(int i = 0; i <= m; ++i)
{
cout << list[i] << "";
}
cout << endl;
}
else
{
for(int i = k; i <= m; ++i)
{
// if( (list[k] != list[i]) || (k == i) ) //为了实现相同元素的全排
// {
sswap(list[k], list[i]);
Perm(list, k+1, m);
sswap(list[k], list[i]);
//}
}
}
}
int main()
{
int n;
int arr[10];
while(cin>>n)
{
for(int i = 0; i < n; ++ i)
{
cin>>arr[i];
}
Perm(arr, 0, n - 1);
}
return 0;
}
三、压轴:STL next_permutation
下面是网上的一段分析
C++/STL中定义的next_permutation和prev_permutation函数则是非常灵活且高效的一种方法,它被广泛的应用于为指定序列生成不同的排列。本文将详细的介绍prev_permutation函数的内部算法。
按照STL文档的描述,next_permutation函数将按字母表顺序生成给定序列的下一个较大的排列,直到整个序列为降序为止。prev_permutation函数与之相反,是生成给定序列的上一个较小的排列。二者原理相同,仅遍例顺序相反,这里仅以next_permutation为例介绍算法。
先对序列大小的比较做出定义:两个长度相同的序列,从两者的第一个元素开始向后寻找,直到出现一个不同元素(也可能就是第它们的第一个元素),该元素较大的序列为大,反之序列为小;若一直到最后一个元素都相同,那么两个序列相等。
设当前序列为pn,下一个较大的序列为pn+1,这里蕴藏的含义是再也找不到另外的序列pm,使得pn < pm < pn+1。
问题
给定任意非空序列,生成下一个较大或较小的排列。
过程
根据上述概念易知,对于一个任意序列,最小的排列是增序,最大的为减序。那么给定一个pn要如何才能生成pn+1呢?先来看下面的例子:
设3 6 4 2为pn,下一个序列pn+1应该是4 2 3 6。观察第一个序列可以发现pn中的6 4 2已经为减序,在这个子集中再也无法排出更大的序列了,因此必须移动3的位置且要找一个数来取代3的位置。在6 4 2中6和4都比3大,但6比3大的太多了,只能选4。将4和3的位置对调后形成排列4 6 3 2。注意,由于4和3大小的相邻关系,对调后产生的子集6 3 2仍保持逆序,即该子集最大的一种排列。而4是第一次移动到头一位的,需要后面的子集为最小的排列,因此直接将6 3 2倒转为2 3 6便得到了正确的一个序列pn+1。
下面归纳分析该过程。假设一个有m个元素的序列pn,其下一组较大排列为pn+1:
若pn的最后的2个元素构成一个最小的增序子集,那么直接反转这2个元素使该子集成为减序即可得到pn+1。理由是pn和pn+1的前面m-2个元素都相等(没有对前面的元素进行操作),仅能靠最后2个元素来分出大小。而这2个元素只能出现2种排列,其中较大的一种是减序。
若pn的最后最多有s个元素构成一个减序子集,令i = m - s,则有pn(i) < pn(i+1),因此若将pn(i)和pn(i+1)调换必能得到一个较大的排列(不一定是下一个),因此必须保持pn(i)之前的元素不动,并在子集{pn(i+1), pn(i+2), ..., pn(m)}中找到一个仅比pn(i)大的元素pn(j),将二者调换位置。此时只要得到新子集{pn(i+1), pn(i+2), ..., pn(i), ...,pn(m)}的最小排列即可。注意到新子集仍保持减序,那么直接将其反转即可得到最小的增序子集。
按以上步骤便可从pn得到pn+1了。
复杂度
最好的情况为pn的最后的2个元素构成一个最小的增序子集,交换次数为1,复杂度为O(1),最差的情况为1个元素最小,而后面的所有元素构成减序子集,这样需要先将第1个元素换到最后,然后反转后面的所有元素。交换次数为1+(n-1)/2,复杂度为O(n)。这样平均复杂度即为O(n/2)。
//STL的生成方法
bool my_next_permutation(int * const begin, int * const end)
{
int *p1 , *p2;
for(p1 = end - 1; p1!= begin; p1--)//找到序列中从后往前第一个元素1小于元素2的一对
{
if(*(p1-1)< *(p1))
break;
}
if(p1==begin)//这种情况下序列已经完全逆序
return false;
p1--;//使p1指向小的那个数
for(p2 = p1 + 1; p2 != end; p2++)//寻找p1后面比p1小但是最大的那个数
//,这里利用了后面序列降序的性质
{
if(*p2 < *p1)
break;
}
p2--;//p2指向后面比p1大但是最小的那个
iter_swap(p1,p2);//交换p1,p2指向的元素
reverse(p1+1,end);//注意是到end 反向而非p2
return true;
}
请这样调用
view plaincopy to clipboardprint?
do
{
for(int i = 0; i < MAX; i++)
{
cout << d[i] << " ";
}
cout << endl;
}while(my_next_permutation(d,d+MAX));
do
{
for(int i = 0; i < MAX; i++)
{
cout << d[i] << " ";
}
cout << endl;
}while(my_next_permutation(d,d+MAX));
部分内容引用:
http://blog.csdn.net/heartnheart/archive/2010/10/20/5953150.aspx
posted on 2011-03-08 11:29
Cunch 阅读(596)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm