将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;
}