高效率的全排列算法——N进制方法实现

分类： 基本算法 (C++) 2010-06-22 21:15 1099人阅读 评论(2) 收藏 举报

算法iniinput2010c

算法描述：

 

全排列N进制算法——

从1到N，输出全排列，共N！条。
分析：用N进制的方法。设一个N个单元的数组a用来存放待全排列的数组的下标，对第一个单元做加一操作，满N进一。每加一次一就判断一下各位数组单元有无重复，有则再转回去做加一操作，没有（且数组a中没有值为N的元素）则说明得到了一个排列方案。

 

例如：求1-3的全排列，共3!条
设数组初始状态为0 0 0，以下为计算全排列的步骤：

0 0 0 +1
1 0 0 +1
2 0 0 +1
3 0 0 满3进1 ->
0 1 0 +1
1 1 0 +1
2 1 0 +1
3 1 0 满3进1 ->
0 2 0 +1
1 2 0 +1
2 2 0 +1
3 2 0 满3进1 ->
0 3 0 满3进1 ->
0 0 1 +1
1 0 1 +1
2 0 1 +1
3 0 1 满3进1 ->
0 1 1 +1
1 1 1 +1
2 1 1 +1
3 1 1 满3进1 ->
0 2 1 +1
1 2 1 +1
2 2 1 +1
3 2 1 满3进1 ->
0 3 1 满3进1 ->
0 0 2 +1
1 0 2 +1
2 0 2 +1
3 0 2 满3进1 ->
0 1 2 +1
1 1 2 +1
2 1 2 +1
3 1 2 满3进1 ->
0 2 2 +1
1 2 2 +1
2 2 2 +1
3 2 2 满3进1 ->
0 3 2 满3进1 ->
0 0 3 满3进1 ->   （最高位为进制n(这里是3)是循环退出条件）
0 0 0

 

其中用红色背景色表明的6个下标序列是合格的,每一个下标序列对应一种排列。

 

 

 

实现如下：

===============================

 

#include <iostream>
using namespace std;

 

//若下标序列中出现进制n或者序列有重复的数字，返回真
bool CheckSame(int *a,int n)
{
 for(int i=0;i<n-1;i++)
 {
  if(a[i] == n)
   return true;
  for(int j=i+1;j<n;j++)
   if(a[i] == a[j])
    return true;
 }
 return false;
}

int main()
{
 int n;
 char c = 'y';
 while(c == 'y')
 {
  cout<<"Input N:";
  cin>>n;
  int *a = new int[n]; //数组a用来存下标
  //数组b用来存实际待排列的数字，也可以手工任意定义
  int *b = new int[n];
  for(int i=0;i<n;i++)
  {
   a[i] = 0;
   b[i] = i+1;
  }
  int count = 0;    //存放总的排列数目
  while(a[n-1] != n)  //最高位为进制n是循环退出条件
  {
   //先打印当前的全排列
   if(!CheckSame(a,n))
   {
    for(int i=0;i<n;i++)
    {
     cout<<b[a[i]]<<" ";
     if(i == n-1)
      count++;
    }
    cout<<endl;
   }
   //完成进位
   bool increase = false;
   for(int i=0;i<n-1;i++)
   {
    //如果有那位是n，则完成进位
    if(a[i] == n)
    {
     a[i] = 0;
     a[i+1]++;
     increase = true; //进过位
     break;
    }
   }
   //如果没有进过位，则使最低位加1
   if(!increase)
    a[0]++;
  }
  cout<<"Total number is:"<<count<<endl;
  delete []a;
  delete []b;
  a = b = NULL;
  cout<<"Continue?(y/n):";
  cin>>c;
 }
 return 0;
}