数字全排列问题 - 一霎微雨洒庭轩

2007-08-22

数字全排列问题 - [Algorithms]

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
 http://conoon.blogbus.com/logs/7858162.html

数字全排列问题：
任意给出从1到N的N个连续的自然数，求出这N个自然数的各种全排列。如N=3时，共有以下6种排列方式：
123，132，213，231，312，321。
注意：数字不能重复，N由键盘输入（N<=9）。

解题思路：
应用回溯法，每个数的取法都有N个方向（1——N），当取够N个数时，输出一个排列，然后退后一步，取前一个数的下一个方向（即前一个数+1），并且要保证所有数字不能重复。当前数字的所有方向都取完时，继续退一步，一直重复到第一个数为止。

程序代码：

program quanpailie; {数字全排列问题}
var
a:array[1..9] of integer;
k,x,n:integer;

function panduan(j,h:integer):boolean; {判断当前数字是否能赋值给当前数组元素}
var
    m:integer;
begin
    panduan:=true;
    for m:=1 to h-1 do
      if a[m]=j then panduan:=false {如果当前数字与前面的数组元素相同则不能赋值}
end;

procedure try(h:integer);
var
    i,j,m:integer;
begin
       for j:=1 to n do
         if panduan(j,h) then
              begin
                a[h]:=j; {能够赋值，且长度k加一}
                k:=k+1;
                if k=n then {如果长度达到N则表示一种组合已经完成，输出结果}
                  begin
                    for m:=1 to n do
                      write(a[m]);
                      write('':4);
                      x:=x+1; {每输出一种排列方式加一}
                      if x mod 5=0 then writeln; {每行输出5种排列方案}
                  end
                else
                  try(h+1); {对下一个数组元素进行赋值}
                k:=k-1    {回溯的时候一定要把长度减一}
              end
   end;