生成1-n的全排列组合

将1-n之间的自然数进行全排列，代码如下所示：

#define N 6
#define FULL -1//完成

void test_row()
{
	int num[N];//待排列数组
	bool use[N];//记录已经排列的数
	for(int k=0;k<N;k++)
	{
		num[k]=0;
		use[k]=false;
	}
	row(num,0,N,use);
}
int row(int*num,int k,int n,bool*use)//对num中从第k个数开始的排列
{
	if(k<0)
		return FULL;
	if(k==n)
	{
		for(int j=0;j<n;j++)
			printf("%d ",num[j]+1);
		printf("\n");
	}
	else
	{
		int t=0;
		for(;t<n;t++)
		{
			if(!use[t])
			{
				push(t,use);
				num[k]=t;
				row(num,k+1,n,use);
				pop(use,num[k]);
			}
		}
	}
}


void push(int k,bool*use)//将k压入记录
{
	use[k]=true;
}
void pop(bool*use,int k)//将k清除记录
{
	use[k]=false;

 上面的程序有个问题：只能从最开始的1……n这样的状态开始排列组合，现在经过改进，可以从任一个状态开始排列，如果状态不对，还可以纠正，代码如下所示：

#define N 6
#define FULL -1//完成

void test_row()
{
	int num[N]={5,4,0,1,2,3};//待排列数组
	bool use[N];//记录已经排列的数
	for(int k=0;k<N;k++)
	{
		use[k]=false;
	}
	row(num,0,N,use);
}
int row(int*num,int k,int n,bool*use)//对num中从第k个数开始的排列
{
	if(k<0)
		return FULL;
	if(k==n)
	{
		bool full=true;
		for(int j=0;j<n;j++)
		{
			printf("%d ",num[j]+1);
			if(j<n-1&&num[j]<num[j+1])full=false;
		}
		printf("\n");
	}
	else
	{
		int t=num[k];
		if(t<0)t=0;
		for(;t<n;t++)
		{
			if(!use[t])
			{
				push(t,use);
				num[k]=t;
				row(num,k+1,n,use);
				pop(use,num[k]);
			}
		}
		num[k]=0;
	}
}


void push(int k,bool*use)//将k压入记录
{
	use[k]=true;
}
void pop(bool*use,int k)//将k清除记录
{
	use[k]=false;
}

 上面的程序会把所有的结果都显示出来，再改改，可以使之显示顺序排列的下一个组合，这里主要是添加了一个参数flag，由于上面程序中在返回的过程中会有清零的过程，这个flag可以指示是否清零。这样就可以是递归程序有决定的是否清零，从而保留已经排序的数，代码如下所示：

#define N 6
#define FULL -1//完成
#define END 0
#define FLAG_C 0//需要清零
#define FLAG_N 1//不需要清零

void test_row()
{
	int num[N]={5,4,0,1,2,3};//待排列数组
	bool use[N];//记录已经排列的数
	for(int k=0;k<N;k++)
	{
		use[k]=false;
	}
	row(num,0,N,use,FLAG_C);
}
int row(int*num,int k,int n,bool*use,int flag)//对num中从第k个数开始的排列
{
	if(k<0)
		return FULL;
	if(k==n)
	{
		for(int j=0;j<n;j++)
			printf("%d ",num[j]+1);
		printf("\n");
		return FULL;
	}
	else
	{
		int t=num[k];
		if(t<0)t=0;
		int sec=0;
		for(;t<n;t++)
		{
			if(!use[t])
			{
				sec++;
				push(t,use);
				num[k]=t;
				int f;
				if(sec==2)f=FLAG_N;
				else f=FLAG_C;
				if(row(num,k+1,n,use,f)==END)
					return END;
				if(sec==2)return END;
				pop(use,num[k]);
			}
		}
		if(flag==FLAG_C)
			num[k]=0;
	}
}


void push(int k,bool*use)//将k压入记录
{
	use[k]=true;
}
void pop(bool*use,int k)//将k清除记录
{
	use[k]=false;
}

 上面这个程序有问题，读者可以自己去运行一下，看看有什么问题，下面是暂时自认为正确的代码，稍稍有点不同：

#define N 6
#define FULL -1//完成
#define END 0
#define FLAG_C 0//需要清零
#define FLAG_N 1//不需要清零

void show(int*r,int length)
{
		for(int j=0;j<length;j++)
			printf("%d ",r[j]+1);
		printf("\n");
}
void test_row()
{
	int num[N]={5,1,2,4,3,0};//待排列数组
	bool use[N];//记录已经排列的数
	for(int k=0;k<N;k++)
	{
		use[k]=false;
	}
	row(num,0,N,use,FLAG_C);
}
int row(int*num,int k,int n,bool*use,int flag)//对num中从第k个数开始的排列
{
	if(k<0)
		return FULL;
	if(k==n)
	{
		show(num,n);
		return FULL;
	}
	else
	{
		int t=num[k];
		if(t<0)t=0;
		int sec=0;
		for(;t<n;t++)
		{
			if(!use[t])
			{
				sec++;
				push(t,use);
				num[k]=t;
				int f;
				if(sec==2||flag==FLAG_N)f=FLAG_N;
				else f=FLAG_C;
				if(row(num,k+1,n,use,f)==END)
					return END;
				if(sec==2||flag==FLAG_N)return END;
				pop(use,num[k]);
			}
		}
		if(flag==FLAG_C)
			num[k]=0;
	}
}


void push(int k,bool*use)//将k压入记录
{
	use[k]=true;
}
void pop(bool*use,int k)//将k清除记录
{
	use[k]=false;
}