算法设计与分析 课件 3.3-递归 - 典型应用 -全排列.pptx

算法设计与分析

递归-典型应用-全排列;设R={r1,r2,…,rn}是要进行排列的n个元素，试设计一个算法，将这n个元素的全排列找出。;R的全排列可归纳定义如下：

n=1时，Perm(r)=(r),r是集合中唯一的元素。

n1时，Perm(R)由(r1)Perm(R1),(r2)Perm(R2),....,(rn)Perm(Rn)构成。;全排列输出算法描述

用一个形如Perm(inta[],intk,intm)的函数表示

输入：a数组，k,m

输出：a的第k到第m个元素的全排列

1、ifk=mthen输出a数组;

else

2、fori=ktomdobegin

3、a[k]和a[i]互换；

4、Perm(a,k+1,m);

5、a[k]和a[i]互换；

end;

6、return;a[3]={1,2,3}

Perm(a,0,2);选择题：

对于1，2，3，4构成的序列进行全排列，最后一种排列是（）

A:4321

B:4231

C:4123

D:4132