随笔 - 30  文章 - 67  trackbacks - 0
<2011年8月>
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿(8)

随笔分类

随笔档案

文章档案

收藏夹

Oops

搜索

  •  

积分与排名

  • 积分 - 84536
  • 排名 - 275

最新评论

阅读排行榜

评论排行榜

 

今天主要是想回忆下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, 
0sizeof(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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理