Question

已知数N，求1,2，...,N的全排列? 非递归方法 C/C++

Answer 1

#include <iostream>
using namespace std;

#define N 3

// 交换元素
void swap(int *a,int *b){ 
	int temp=*a;
	*a = *b;
	*b = temp;
}

// 字典序全排列算法(非递归版本)
int FullArray(int iArr[], int n,bool *bPoint) 
{
	int i,j,k=-1,l;

	if(*bPoint){
		for(i=0;i<n;i++) cout<<iArr[i];
		cout<<endl;
		*bPoint=false;
	}

	for(i=0;i<n-1;i++){  // 找最后的升序的位置
		if(iArr[i]<iArr[i+1]) k=i;  
	}

	if (k>=0){ 
		l=-1;

		for(i=0;i<n;i++){  // 找到最后一个升序且是最大的数的下标
			if(iArr[k]<iArr[i]) l=i;
		} 

		swap(&iArr[k],&iArr[l]); 

		for(i=k+1;i<n;i++)// 将k+1的元素与末尾对调
		{
			j = n - i + k;
			if (i >= j) break; 
			swap(&iArr[i], &iArr[j]);
		}
	}

	if (k==-1) return 0;  
	for(i=0;i<n;i++) cout<<iArr[i];
	cout<<"\n";

	return 1; 
}

int main()
{
	
	int iArr[N]={1,2,3};    
	bool bFirst=true;
	
	// 开始循环调用字典序算法,直至全排列排列完毕
	// 返回0代表排列完毕，返回1代表仍有未排列完的数
	while (FullArray(iArr,N,&bFirst)==1);

	system("pause");
	return 0; 
}