作者：未知 来源：月光软件站 加入时间：2005-2-28　月光软件站

以下是一个全排列的泛型算法的简单实现；
我用它生成测试序列可以用于一些代码的测试；
顺便研究一下泛型算法；
下面的实现还是较初级， 还有待改进；

#pragma warning(disable: 4530)
#pragma warning(disable: 4786)
#include <cassert>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <exception>
using namespace std;

//阶乘, 不检测溢出
unsigned __int64 _tFactorial(unsigned __int64 N)
{
     unsigned __int64 r = 1;
     for(unsigned __int64 i = 2; i <= N; i ++)
          r *= i;
     return r;
}

//全排列, 不检测重复
template<typename T, typename Array>
void arrange(T * first, T *last, Array matrix, int row = 0, int col = 0)
{
 if(first >= last)
  return;

 int N = last - first;

 if(N == 1) //递归终止
 {
  matrix[row][col] = *first;
  return;
 }
 
 int line_N = _tFactorial(N - 1);
 T *temp = new T[N - 1], *cp;

 for(int i = 0, j; i < N; i ++)
 {
  for(j = 0; j < line_N; j ++)
   matrix[i * line_N + j + row][col] = *(first + i);

  for(cp = temp, j = 0; j < N; j ++)
   if(j != i)
    *cp ++ = *(first + j);

  arrange<T>(temp, temp + N - 1, matrix, row + i * line_N, col + 1); 
 } 

 delete[] temp;
} 

int main(int argc, char *argv[])
{
 try
 {
  int i, j;

  char c[5] = "1234"; //待排列数据
  char rc[24][4]; //保存结果

  string str[3] = {"the", "if", "else"};
  string rstr[6][3]; 

  arrange<char>(c, c + 4, rc);
  for(i = 0; i < 24; i ++)
  {
   for(j = 0; j < 4; j ++ )
    cout <<  rc[i][j] << ',';
   cout << endl;
  }

  arrange<string>(str, str + 3, rstr);
  for(i = 0; i < 6; i ++)
  {
   for(j = 0; j < 3; j ++ )
    cout <<  rstr[i][j] << ',';
   cout << endl;
  }
  
  //STL容器
  char vc[] = "ABCD";
  vector<char> vec(vc, vc + 4);
  vector<vector<char> > rvec; //不能使用容器作返回参数

  arrange<char>(vec.begin(), vec.end(), rc);
  for(i = 0; i < 24; i ++)
  {
   for(j = 0; j < 4; j ++ )
    cout <<  rc[i][j] << ',';
   cout << endl;
  }
 }
 catch(exception &e)
 {
  cout << e.what() << endl;
 }
 return 0;
}

---------- 结果----------

1,2,3,4,
1,2,4,3,
1,3,2,4,
1,3,4,2,
1,4,2,3,
1,4,3,2,
2,1,3,4,
2,1,4,3,
2,3,1,4,
2,3,4,1,
2,4,1,3,
2,4,3,1,
3,1,2,4,
3,1,4,2,
3,2,1,4,
3,2,4,1,
3,4,1,2,
3,4,2,1,
4,1,2,3,
4,1,3,2,
4,2,1,3,
4,2,3,1,
4,3,1,2,
4,3,2,1,
the,if,else,
the,else,if,
if,the,else,
if,else,the,
else,the,if,
else,if,the,
A,B,C,D,
A,B,D,C,
A,C,B,D,
A,C,D,B,
A,D,B,C,
A,D,C,B,
B,A,C,D,
B,A,D,C,
B,C,A,D,
B,C,D,A,
B,D,A,C,
B,D,C,A,
C,A,B,D,
C,A,D,B,
C,B,A,D,
C,B,D,A,
C,D,A,B,
C,D,B,A,
D,A,B,C,
D,A,C,B,
D,B,A,C,
D,B,C,A,
D,C,A,B,
D,C,B,A,

相关软件：