全排列

mahonglin123456

　　交换两个数：



template<class T>
void exchange(T & f, T & s)
{
T t = f;
f = s;
s = t;
};
　　递归方式——递归节：



void fullPermutation(int * fullArray, int start, int number, int & count)
{
if(start >= number)
{
cout << count + 1 << "\t:" ;
for(int i = 0;i < number; ++ i)
cout << fullArray << " ";
cout << endl;
count ++;
}
else
for(int i = start; i < number; ++ i)
{
exchange(fullArray[start], fullArray);
fullPermutation(fullArray, start+1, number, count);
exchange(fullArray[start], fullArray);
}
}
　　递归方式——精简：



int fullPermutation(int number)
{
int * fullArray = new int[number];
for (int i = 0;i < number;i ++)
fullArray = i + 1;
int icount = 0;
fullPermutation(fullArray, 0, number, icount);
delete[] fullArray;
return icount;
}
　　逆转数组：



void reverseArray(int * fullArray, int number)
{
int i(0), j(number - 1);
while (i < j)
exchange(fullArray[i ++], fullArray[j --]);
}
　　找到传说中XY的索引坐标：
　　找到最后一个这样的xindex，使的fullArray[xindex] < fullArray[xindex + 1]；
　　xindex之后找到最后一个这样的yindex，使的fullArray[xindex] < fullArray[yindex]；



int findXY(int * fullArray, int number, int &xindex, int &yindex)
{
xindex = -1;
for (int i = 0; i < number - 1; ++ i)
{
if (fullArray < fullArray[i + 1])
{
xindex = i;
yindex = i + 1;
}
else if (xindex != -1 && fullArray[xindex] < fullArray[i + 1])
yindex = i + 1;
}
return xindex;
}
　　非递归方式产生全排列：



void fullPermutation2(int * fullArray, int number, int & count){
int xindex(-1);
int yindex(-1);
count = 1;
cout << count << "\t:" ;
for(int i = 0;i < number; i ++)
cout << fullArray << " ";
cout << endl;
while (-1 != findXY(fullArray,number, xindex, yindex))
{
exchange(fullArray[xindex], fullArray[yindex]);
reverseArray(fullArray + xindex + 1, number - xindex -1);
cout << ++ count << "\t:" ;
for(int i = 0;i < number; i ++)
cout << fullArray << " ";
cout << endl;
}
}
　　非递归方式精简：



int fullPermutation2(int number)
{
int * fullArray = new int[number];
for (int i = 0;i < number;i ++)
fullArray = i + 1;
int icount = 0;
fullPermutation2(fullArray, number, icount);
delete[] fullArray;
return icount;
}
　　测试



#include <iostream>
using namespace std;

int main()
{
int number;
cout << "Number:" << endl;
cin >> number;
int firstmethod = fullPermutation(number);
int secondmethod = fullPermutation2(number);
cout << "the size of results int first method is \t" << firstmethod << endl;
cout << "the size of results int second method is \t" << secondmethod << endl;
system("pause");
return 0;
}