生成排列算法

浏览数：19 / 时间：2015年06月08日

1、递归方法

例如，如果集合是{1,2,3},那么这个集合中元素的所有排列是{(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)}，显然，给定n个元素共有n!种不同的排列，如果给定集合是{1,2,3,4}，可以用下面给出的简单算法产生其所有排列，即集合(1,2,3,4)的所有排列有下面的排列组成：

（1）以1开头后面跟着(2,3,4)的排列

（2）以2开头后面跟着(1,3,4)的排列

（3）以3开头后面跟着1,2,4)的排列

（4）以4开头后面跟着(1,2,3)的排列，这显然是一种递归的思路，于是我们得到了以下的实现：

void swap(int &a,int &b)
{
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}
void permutation(int* a,int k,int m) 
{
     int i,j;
     if(k == m)
     {
         for(i=0;i<m;++i)
             cout << a[i];
         cout<<endl;
     }
     else 
     {
         for(j=k;j<m;++j)
        {
             swap(&a[k],&a[j]);
             permutation(a,k+1,m);
             swap(&a[k],&a[j]);
        }
     }
}

去掉重复符号的全排列：在交换之前可以先判断两个符号是否相同，不相同才交换，这个时候需要一个判断符号是否相同的函数。

void swap(int &a,int &b)
{
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

bool isSwap(int *a ,int begin,int end)
{
    for(int i=begin;i<end;++i)
    {
          if(a[i] == a[end]) 
              return false;
    }
    return true;
}

void permutation(int* a,int k,int m) 
{
     int i,j;
     if(k == m)
     {
         for(i=0;i<m;++i)
             cout << a[i];
         cout<<endl;
     }
     else 
     {
         for(j=k;j<m;++j)
        {
             if(isSwap(a,k,j))     // 去掉重复元素
            {
                 swap(&a[k],&a[j]);
                 permutation(a,k+1,m);
                 swap(&a[k],&a[j]);
            }
        }
     }
}

2、非递归实现

基本思想是:
    1.对初始队列进行排序，找到所有排列中最小的一个排列Pmin。
    2.找到刚刚好比Pmin大比其它都小的排列P(min+1)。
    3.循环执行第二步,直到找到一个最大的排列,算法结束。
如排列ABCDE，这是所有排列中最小的一个排列，刚好比ABCDE大的排列是：ABCED。
算法如下：
给定已知序列P = A1A2A3.....An
对P按字典排序，得到P的一个最小排列Pmin = A1A2A3....An ，满足Ai > A(i-1) (1 < i <= n)
从Pmin开始,找到刚好比Pmin大的一个排列P(min+1)，再找到刚好比P(min+1)大的一个排列，如此重复。
1.从后向前（即从An->A1）,找到第一对为升序的相邻元素，即Ai < A(i+1)。
若找不到这样的Ai，说明已经找到最后一个全排列，可以返回了。
2.从后向前,找到第一个比Ai大的数Aj，交换Ai和Aj。
3.将排列中A(i+1)A(i+2)....An这个序列的数逆序倒置，即An.....A(i+2)A(i+1)。因为由前面第1、2可以得知，A(i+1)>=A(i+2)>=.....>=An,这为一个升序序列，应将该序列逆序倒置，所得到的新排列才刚刚好比上个排列大。
4.重复步骤1-3,直到返回。

void swap(int *a,int i,int j)  
{  
    a[i]^=a[j];  
    a[j]^=a[i];  
    a[i]^=a[j];  
}  
  
//将数组a中的下标i到下标j之间的所有元素逆序倒置  
void reverse(int a[],int i,int j)  
{  
    for(; i<j; ++i,--j) {  
        swap(a,i,j);  
    }  
}  
  
void print(int a[],int length)  
{  
    for(int i=0; i<length; ++i)  
        cout<<a[i]<<ends;  
    cout<<endl;  
}  
  
//求取全排列,打印结果  
void combination(int a[],int length)  
{  
    if(length<2) return;  
  
    bool end=false;  
    while(true) {  
        print(a,length);  
  
        int i,j;  
        //找到不符合趋势的元素的下标i  
        for(i=length-2; i>=0; --i) {  
            if(a[i]<a[i+1]) break;  
            else if(i==0) return;  
        }  
  
        for(j=length-1; j>i; --j) {  
            if(a[j]>a[i]) break;  
        }  
  
        swap(a,i,j);  
        reverse(a,i+1,length-1);  
    }  
}