c++使用递归生成全排列

  通常我们希望检查n个不同元素的所有排列方式来确定一个最佳的排序。比如a,b,c的排列方式有abc,acb,bac,bca,cab,cba六种。
  由于采用非递归的c++函数来输出排列方式很困难，所以采用递归是一种比较不错的方法。
  其核心是：将每个元素放到n个元素组成的队列最前方，然后对剩余元素进行全排列，依次递归下去。
  比如：
  a b c
  首先将a放到最前方（跟第一个元素交换），然后排列b c，然后将a放回本来位置
   结果 a b c； a c b
  其次将b放到最前方（跟第一个元素交换），然后排列a c，然后将b放回
   结果 b a c； b c a
   。。。
 
  如果是4个元素，就将元素依次放到第一个元素的位置，后面的排序类似前面的3元素排序。

  c＋＋代码如下：（在g＋＋上通过测试）
/*
* 本程序对一个数组进行全排列，并输出
* 文件名perm.cpp
*/
#include <iostream>
using namespace std;

/*
* 函数模板，递归调用对一个数组进行全排列
*/
template <class T>
void Perm(T list[],int k,int m)
{
  int i;
  if(k == m)//输出一个全排列
    {
      for(i=0;i <= m;i++)
        cout<<list[i];
      cout<<endl;
    }
  else //list[k:m]有多个排列方式
    //递归的产生这些排列方式
    for(i = k;i <= m;i++)
    {
      Swap(list[k],list[i]);//交换位置，逐步前提
      Perm(list,k+1,m);
      Swap(list[k],list[i]);//将位置还回去，对下一次排列负责
    }
}

template<class T>
inline void Swap(T& a,T& b)
{//exchange a and b
  T temp = a;a = b;b = temp;
}

//一个测试程序
int main()
{
  char list[]="abc";
  Perm(list,0,2);
  return 0;
}

本算法来源于数据结构、算法与应用此书，希望我的理解能帮助大家