算法设计与分析课件 37 全排列

算法设计与分析本节要点CONTENTS全排列全排列按照字典序输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。如何得到n个数的全排列呢？一种是交换法，另一种是标记法。需要特别注意，交换法得到的全排列不是按字典序，适用于对排列没有顺序要求的题目，或利用排列树辅助求解问题。如果题目要求按字典序输出全排列，则使用标记法求解。求解[1,2,3]的全排列。1与1交换，然后求解[2,3]的排列。[2,3]的排列是[2,3]和[3,2]，得到1开头的排列：[1,2,3]，[1,3,2]。2与1交换，然后求解[1,3]的排列。[1,3]的排列是[1,3]和[3,1]，得到2开头的排列：[2,1,3]，[2,3,1]。3与1交换，然后求解[2,1]的排列。[2,1]的排列是[2,1]和[1,2]，得到3开头的排列：[3,2,1]，[3,1,2]。注意，最后一个分支得到的排列中，[3,2,1]在[3,1,2]之前，不是按照字典序。全排列全排列根据求解过程画出排列树，如图所示。（1）递归函数的参数用一维数组ans[]存储从1到n的数。因为交换直接在数组上进行，无需辅助数组。横向枚举时，枚举的开始下标为层次t，结束下标为n-1。通过层次t判断是否到达叶子，设计一个参数：t，表示当前枚举的层次。树根的层次为0。（2）递归函数的结束条件到达叶子时，t=n，将得到的一个排列ans[]，输出该排列。全排列（3）横向枚举横向枚举用for语句实现，从开始下标t到结束下标n-1，逐个枚举即可。（4）纵向扩展纵向扩展，进入下一层时，需要确定参数变化，层次参数变为t+1，t为上一层的层次。在进入下一层之前，当前数ans[i]和序列的开始数ans[t]交换，swap(ans[i],ans[t])。在递归结束回溯时，需要还原现场，再交换回去，swap(ans[i],ans[t])。全排列算法实现全排列第二种解法（标记法）用一维数组ans[]存储一个排列，因为全排列中的数不可以重复使用，也可以通过vis[]标记该数是否已用过，如果已用过，则跳过。全排列（1）递归函数的参数用一维数组ans[]存储一个排列。横向枚举时，枚举的开始和结束数字分别为1和n。通过层次t判断是否到达叶子，设计一个参数：t，表示当前枚举的层次。树根的层次为0。（2）递归函数的结束条件到达叶子时，t=n，将得到的一个排列ans[]，输出该排列。全排列（3）横向枚举横向枚举用for语句实现，从1到n逐个枚举即可。（4）纵向扩展纵向扩展，进入下一层时，需要确定参数变化，参数变为t+1，t为上一层的层次。在进入下一层之前，首先判断如果该数已用过，直接跳过。否则用ans[]收集当前数i，并标记当前数已用过，vis[i]=true。在递归结束回溯时，需要还原现场，从ans[]中弹出当前数，并恢复标记当前数未用过，vis[i]=false。全排列算法实现全排列算法分析时间复杂度：包含n个元素的数组，其排列个数为n!，对应搜索树的每一个叶子节点。从树根到叶子经过的节点数为n，因此总时间复杂度为