Dain

全排列

首先，给出算法的思路
设R={r₁,r₂,...,r_n}是要进行排列的n个元素，R_i=R-{r_i}。
集合X中元素的全排列记为permutation(X)，(ri)permutation(X)表示在全排列permutation(X)的每一个排列前加上前缀r_i得到的排列。
R的全排列可归纳定义如下：
当n=1时，permutation(R)={r},r是集合R中唯一的元素；
当n>1时，permutation(R)由(r₁)permutation(R₁)，(r₂)permutation(R₂)，……，(r_n)permutation(R_n)构成。

此算法要求待排列的数据是互异的，因为该算法不能检测同种排列是否已经输出，如：
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 @ 2006-12-25 10:17 Dain 阅读(1121) | 评论 (2) | 编辑收藏