学步园

例5：有3个人排成一个队列，问有多少种排对的方法，输出每一种方案？

分析：如果我们将3个人进行编号，分别为1、2、3，显然我们列出所有的排列，123，132，213，231，312，321共六种。可用循环枚举各种情况，参考程序：

program exam5;

var

    i,j,k:integer;

begin

    for I:=1 to 3 do

for j:=1 to 3 do

        for k:=1 to 3 do

        if (i+j+k=6) and (i*j*k=6) then writeln(i,j,k);

end.

上述情况非常简单，因为只有3个人，但当有N个人时怎么办？显然用循环不能解决问题。下面我们介绍一种求全排列的方法。

设当前排列为P1 P2 ,…,Pn，则下一个排列可按如下算法完成：

1．求满足关系式Pj-1 < Pj的J的最大值，设为I，即

I=max{j | Pj-1 < Pj , j = 2..n}

2．求满足关系式Pi -1 < Pk的k的最大值，设为j，即

J=max{K | Pi-1 < Pk , k = 1..n}

3．Pi -1与Pj互换得 (P) = P1 P2 ,…,Pn

4．(P) = P1 P2 ,…, Pi-1 Pi,…, Pn部分的顺序逆转，得P1 P2 ,…, Pi-1 Pn Pn-1,…, Pi便是下一个排列。

例：设P1 P2 P3 P4 =3421

1．I= max{j | Pj-1 < Pj , j = 2..n} = 2

2．J=max{K | Pi-1 < Pk , k =1..n} = 2

3．P1与P2交换得到4321

4．4321的321部分逆转得到4123即是3421的下一个排列。

程序设计如下：

program exam5;

const

     maxn     = 100;

var   i,j,m,t : integer;

      p       : array[1..maxn] of integer;

      count   :integer;         {排列数目统计变量}

begin

    write('m:');readln(m);

    for i:=1 to m do begin p[i]:=i; write(i) end;

    writeln;

    count:=1;

    repeat

{求满足关系式Pj-1 < Pj的J的最大值，设为I}

      i:=m;

      while (i>1) and (p[i-1]>=p[i]) do dec(i);

      if i=1 then break;

   {求满足关系式Pi -1 < Pk的k的最大值，设为j}

      j:=m;

      while (j>0) and (p[i-1]>=p[j]) do dec(j);

      if j=0 then break;

    {Pi -1与Pj互换得 (P) = P1 P2 ,…,Pm}

      t:=p[i-1];p[i-1]:=p[j];p[j]:=t;

{Pi,…, Pm的顺序逆转}

      for j:=1 to (m-i+1) div 2 do begin

          t:=p[i+j-1];p[i+j-1]:=p[m-j+1];p[m-j+1]:=t

      end;

    {打印当前解}

    for i:=1 to m do write(p[i]);

    inc(count);

    writeln;

    until false;

    writeln(count)

End.

 #include<stdio.h>
#include<stdlib.h>
#include<string.h>
int *arg=0;//数组
int Num=0;//数组个数
void fun( int x );
int t=0;
int main()
{
  int i=0;
  scanf( "%d",&Num );
  arg=( int* )malloc( sizeof( int )*Num );

    memcpy( arg,p,aix*sizeof( int ) );
    free( p );
  }
}