排列组合生成算法C++实现之邻位互换法

#include
#include

using namespace std;
/*
* 邻位互换法
* 1:找出处于活动状态的元素
* 2:找出处于活动状态的最大值
* 3:用数组初始化出Element类型
* 4:重复以上过程直到没有处于活动状态的元素
*/
int total = 0;
struct Element{
int data; // 整数数值
int direction; //箭头方向 ，0表示向左，1表示向右
};
//找出处于活动状态的元素
//vec存储处于活动状态的元素
bool FindActive(Element array[],int length,vector& vec)
{
vec.clear();
for(int i = 0;i < length;i++)
{
if(array[i].direction == 0 && (i-1 >= 0)&& array[i].data > array[i-1].data )
{
vec.push_back(i);
}
else if (array[i].direction == 1 && (i+1 < length)&& array[i].data > array[i+1].data)
{
vec.push_back(i);
}
}
if (vec.size() != 0)
{
return true;
}
return false;
}
//找出处于活动状态的最大值
int FindBiggestActive(Element array[],int length,vector& vec,int &biggestNum)
{
if (vec.size()==0)
{
return -1;
}
int biggest = vec[0];
for (int i = 0; i < vec.size();i++)
{
if(array[vec[i]].data > array[biggest].data )
{
biggest = vec[i];
}
}
biggestNum = array[biggest].data ;
return biggest;
}
void SwapE( Element array[],int i ,int j)
{
Element temp = {0,0};
temp = array[i];
array[i] = array[j];
array[j] = temp;
}

//交换最大活动状态值与其相邻的元素(箭头方向）
void Swap(Element array[],int length,int biggest)
{
int near;
if(array[biggest].direction == 0)
{
near = biggest - 1;
}
else{
near = biggest + 1;
}
if (near < 0 || near > length)
{
return ;
}

SwapE(array,near,biggest);
}

//改变比活动状态最大值还要打的元素的箭头方向
void ChangeDirection(Element array[],int length,int biggestNum)
{
for (int i = 0 ; i < length ; i++)
{
if(array[i].data > biggestNum)
{
array[i].direction = !array[i].direction;
}
}
}

//用数组初始化出Element类型
void InitElement(int data[],Element* elem,int length)
{
for (int i = 0; i < length ; i++)
{
elem->data = data[i];
elem->direction = 0;
elem++;
}
}
//打印出元素值
void printElement(Element array[],int length)
{
for (int i = 0 ; i < length ; i++)
{
cout << array[i].data << " ";

}
cout << "number : " << ++total << endl;
cout << endl;
}
//以下这3个函数都是为了实现快速排序
void swapA(int A[],int i, int j);
int partition(int A[],int p,int r);
void quicksort(int A[],int p,int r);


//生成Element array的全排列
bool permutation(Element array[],int length,vector& vec)
{
if (!FindActive(array,length,vec))
{
return false;
}
int biggestNUM;
int biggest = FindBiggestActive(array,length,vec,biggestNUM);
Swap(array,length,biggest);
ChangeDirection(array,len

gth,biggestNUM);
printElement(array,length);
return true;
}
int main()
{
int data[] = {1,2,3,4,5};
vector vec;
int length = sizeof(data)/sizeof(int);
quicksort(data,0,length);

Element* array = new Element[length];
InitElement(data,array,length);
printElement(array,length);

while(true)
{
if(!permutation(array,length,vec))
break;
}
delete [] array;
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);
}
}