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