Dain

写出一个可以工作的程序并不够

统计

留言簿(3)

积分与排名

良师益友

阅读排行榜

评论排行榜

全排列

首先,给出算法的思路
设R={r1,r2,...,rn}是要进行排列的n个元素,Ri=R-{ri}。
集合X中元素的全排列记为permutation(X),(ri)permutation(X)表示在全排列permutation(X)的每一个排列前加上前缀ri得到的排列。
R的全排列可归纳定义如下:
当n=1时,permutation(R)={r},r是集合R中唯一的元素;
当n>1时,permutation(R)由(r1)permutation(R1),(r2)permutation(R2),……,(rn)permutation(Rn)构成。

此算法要求待排列的数据是互异的,因为该算法不能检测同种排列是否已经输出,如:
1, 1, 2
那么,全排列期望输出是:
1, 1, 2
1, 2, 1
2, 1, 1
但是该算法的输出:
1, 1, 2
1, 2, 1
2, 1, 1
1, 1, 2
1, 2, 1
2, 1, 1

这是该算法的缺点,也限制了它的适用范围。

程序描述如下:

#include  < iostream >
#include 
< algorithm >  

using   namespace  std; 

//  递归产生R[k:n]的所有的排列,元素是互异的
template  < class  Type >
void  permutation(Type  * R, int  k, int  n)
{
    
if (k == n)
    {
        
for ( int  i = 0 ;i < n; ++ i)
            cout 
<<  R[i]  <<   " \t " ;
        cout 
<<  endl;
    }
    
else
        
for ( int  i = k;i < n; ++ i)
        {
            swap(R[k],R[i]);
            permutation(R,k
+ 1 ,n);
            swap(R[k],R[i]);
        }
}

还有一种很简单的方法,使用GP中的方法

该算法是STL中的范型算法,当然效果是很好的,不会出现上面的算法的情况。

程序描述如下:

//  使用泛型算法next_permutation()
#include  < iostream >
#include 
< vector >
#include 
< algorithm >  

using   namespace  std; 

//  产生R[k:n]的所有的排列
template  < class  Type >  

void  pernutation(Type  * R, int  k, int  n)
{
 vector
< Type >  myVec;
 
int  i,size  =  n  -  k;
 
for (i  =  k;i  <  n;i ++ )
  myVec.push_back(R[i]);
 
//  使用next_permutation()函数必须是有序的数据
 sort(myVec.begin(),myVec.end());
  
 
do
 {
  
for (i  =   0 ;i  <  size;i ++ )
   cout 
<<  myVec[i]  <<   " \t " ;
  cout 
<<  endl;
 }
 
while (next_permutation(myVec.begin(),myVec.end()));
}

注:这里的待全排的数据是存在数组或者向量中的。

posted on 2006-12-25 10:17 Dain 阅读(1080) 评论(2)  编辑 收藏 引用 所属分类: 算法

评论

# re: 全排序 2006-12-25 10:35 Dain

有兴趣,可以将递归改成非递归  回复  更多评论   

# re: 全排列 2007-06-22 00:00 ryan

很清楚,谢谢!  回复  更多评论   


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