这是我很早写的程序,算是灌水文章
全排列程序的一种思路
一个数的全排列，如2的全排列为12，21；共2个；3的全排列为123，132，213，231，312，321；共6个……。全排列在很多地方都有重要的应用，但是要产生但是一个数的全排列，却并不如我们想象的那么简单，(不信您可以先不看文章中的程序，自己编写一个的产生算法)，本文笔者利用一种棋盘思路，编写了一个全排列的程序。
我们知道一个数n的全排列，就是自然数从1到n的没有重复的全部排序，排成一个排列后，以后排的排列不能与之重复。我们可以用如下方法简单地化解。
设想有一种棋，棋盘为n×n格，棋子共n个，要求每行和每列不能有两个或两个以上的棋子，要求它的棋子的全部可能的布局。下图为4×4棋盘的一种布局。
●
●
●
●
其实用心思考以下，这就是一个数n全排列的等价命题。因为每行和每列不能有重复的棋子，而棋盘又是正方形，它的棋子的全部可能的布局，就相当于数n的一个排列。
可以用如下的思路下棋，首先在第1行第1列处放置一个棋子，然后开始放第2行，因为第1列已经放了棋子，故只能放置在第2列上，然后放第3列…..一直放到第n行。这样算是完成了一个排列，接下来排第2个排列，注意：此时的状态不要改变，将第n－1行上的棋子从左边第一个格子开始向右移动一格，看看是否与前n－2行的棋子冲突(不要管第n行的棋子)，如果冲突便将棋子再向右移动一格，再看是否有冲突，直到不发生冲突为止，如果找不到这样的一个位置，可不管第n行和第n－1行棋子，用第n－2棋子作同样的实验，直到找到一个位置为止，否则，将所用的棋子行号减1，作同样的实验，直到找到一个位置后。用同样的方法排下一行的棋子，当排到第n行时便又完成一个排列。当第1行的棋子中排到最右边的一个棋格时而再排将不能排时，便完成了棋盘的全部布局，此时全排列结束。
下面是其程序，用C＋＋语言编写。
#include <stdio.h>
#include <iostream.h>
int Row[15];///用于模拟棋盘，其中数组下标为行号，所赋的值为棋子所在的列号
int i;
int CanSet(int k) /////判断第k行上棋子能否放在当前列上
{
int j;
j=1;
while(j<k){
if(Row[j]==Row[k])return 0;///只要和前边的行上的棋子有冲突便不成功
j++;
}
return 1;
}
void QuanPaiLie(int n)//////全排列实现函数
{
int k;
Row[1]=0;////第1次，第1行上也没放置棋子
k=1;/////开始放置第1行
while(k>0){
Row[k]=Row[k]+1;////将棋子向右移动一格
while(Row[k]<=n&&(CanSet(k)<1)){
Row[k]=Row[k]+1;////不能放则重复向右移动棋子
};
if(Row[k]<=n){////我们找到了一个位置，那么可以放下棋子了
if(k==n){
for(i=1;i<=n;i++)printf("%d ",Row[i]);////已经放完了n行一个排列完成了，
////将它们打印出来
printf("\n");/////换一行
}else{
k=k+1;////如果还没有放完，继续放
Row[k]=0;////从最左边开始放
}
}else{
k=k-1;/////向上一行，看看是否有别的放法
}
}
}
void main()
{
int n;
printf("enter your num to pailie:");
cin>>n;
QuanPaiLie(n);
}
本程序在TC++3.0和VC5.0上均调试通过。
1997/6/10
于合肥电子工程学院
#####完##
