排列组合生成算法C++实现之字典序法

#include
#include
using namespace std;
/*
*字典序法
*1:求 i=max{j| pj-1*2:j=max{k| pi-1*3:互换pi-1与pj
*4:反排pj后面的数得到(q)
*5:重复步骤1
*/
int total = 0;

//找最后一个正序
int FindTheLastActiveSeq(int array[],int length)
{
for(int i = length - 1; i >= 1;i--)
{
if(array[i] > array[i-1])
return i-1;
}
return -1;
}
//最后大于array[index]者
int FindTheLastBigger(int array[],int length,int index)
{
for(int i = length - 1;i > index; i--)
{
if(array[i] > array[index])
return i;
}
return -1;
}
//换pi-1与pj
void swap(int& num1 ,int &num2)
{
int temp = num1;
num1 = num2;
num2 = temp;
}
//反排pj后面的数得到(q)
void Reverse(int array[],int length,int index)
{
vector vec;
int vecindex = 0;
for(int i = length - 1; i > index ; i--)
{
vec.push_back(array[i]);
}
for(int j = index+1; j <= length -1;j++)
{
array[j] = vec[vecindex++];
}
}
//打印排列
void PrintArray(int array[],int length)
{
cout <<"number: " << ++total << endl;
for(int i = 0 ; i < length ; i++)
cout << array[i] << " ";
cout << endl;

}
/*生成array中数列的所有排列 ，array必须为递增序列，
*考虑到通常array为非递增序列，我们对其进行了快速排序，
*以保证程序的健壮性
*/
void swapA(int A[],int i, int j);
int partition(int A[],int p,int r);
void quicksort(int A[],int p,int r);

bool Permutation(int array[],int length)
{

int index1 = FindTheLastActiveSeq(array,length);

if(index1 == -1)
return false;
int index2 = FindTheLastBigger(array,length,index1);

if(index2 == -1)
return false;
swap(array[index1],array[index2]);
Reverse(array,length,index1);
PrintArray(array,length);

return true;

}
int main()
{
int array[] = { 4,3,5,1,2};
int length = sizeof(array)/sizeof(int);
quicksort(array,0,length);
PrintArray(array,length);
while(Permutation(array,length));
system("pause");
return 0;
}


void swapA(int A[],int i, int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
int partition(int A[],int p,int r)
{
int x = A[r-1];
int i = p - 1;

for(int j = p ; j < r-1; j++)
if(A[j]<=x){
i++;
swapA(A,i,j);
}
swapA(A,i+1,r-1);
return i+1;
}
void quicksort(int A[],int p,int r)
{
if(p{
int q = partition(A,p,r);
quicksort(A,p,q-1);
quicksort(A,q+1,r);
}
}