几种求排列数的方法

前面的热心网友回答的那种穷举法可以,但比较耗时且不易扩展.
全排列问题其实就是一个深度搜索的问题,一般采取回溯法来解决.
当然就具体问题还要考虑剪枝等细节问题,不过你这里只是全排列就不用考虑那么多了.
比较有名的题目是八皇后问题.
 
下面给一个全排列问题的递归解法,改变N的值可以对不同数进行全排列.
如果要求输入n来全排列的话把数组a改成动态分配,并作为参数送入各个函数就行了.
 
#include <iostream>
using namespace std;
#define N 3
int a[N];
void printSeq()
{
 for(int i=0; i<N; i++) cout << a[i] << " ";
 cout << endl;
}
bool isok(int i, int k)
{
 for(int j=0; j<i; j++)
 {
  if(a[j] == k) return false;
 }
 return true;
}
void calcSeq(int i)
{
 if(i==N) printSeq();
 else
 {
  for(int k=1; k<=N; k++)
  {
   if(isok(i, k))
   {
    a[i] = k;
    calcSeq(i+1);
   }
  }
 }
}
int main()
{
 calcSeq(0);
 return 0;
}
 
另外也有非递归解法,模拟一个栈来做