算法设计与分析之全排列

全排列 1 首先看最后两个数4 5 它们的全排列为45和54 即以4开头的5的全排列和以5开头的4的全排列 由于一个数的全排列就是其本身 从而得到以上结果 2 再看后三个数3 4 5 它们的全排列为345 354 435 453 534 543六组数 即以3开头的和4 5的全排列的组合 以4开头的和3 5的全排列的组合和以5开头的和3 4的全排列的组合 从而可以推断 设一组数p r1 r2 r3 rn 全排列为perm p pn p rn 因此perm p r1perm p1 r2perm p2 r3perm p3 rnperm pn 当n 1时perm p r1 为了更容易理解 将整组数中的所有的数分别与第一个数交换 这样就总是在处理后n 1个数的全排列 两个例子 123的全排列 首先遍历元素 然后把遍历到的每一个元素都和第一个元素交换第一个和第一个交换就是1和1交换最后还是123那么就形成了123213321这样的3组 交换后再换回来还原成123因为后面的交换都是在123的基础上交换的所以swap要写2次 检查每一组除了第一个之外的剩余元素 如果这些元素个数是2 那么就对这剩下的2个元素全排列就是123132 213231 3213122个元素的全排列很简单就是把这2个元素交换位置就OK 两个例子 1234的全排列 首先遍历元素 然后把遍历到的每一个元素都和第一个元素交换那么就形成了1234213432144231这样的4组 检查每一组除了第一个之外的剩余元素 如1234剩余的是234 发现是3个元素那么问题就转换为求234的全排列了接下来也是一样问题转换为求134 214 231的全排列像这样总是对除了第一个之外的元素全排列 每次元素的个数都在减少一个 求N个元素全排列最终就变成求2的元素的全排列了 求n个元素的全排列 分析 n 1输出a1 n 2输出a1a2 a2a1 n 3输出a1a2a3 a1a3a2 a2a1a3 a2a3a1 a3a2a1 a3a1a2 归纳 n 3时排列的分类 1 a1类 a1之后跟a2 a3的全排列 2 a2类 a2之后跟a1 a3的全排列 3 a3类 a3之后跟a2 a1的全排列 将 1 中的a1 a2互换位置 得到 2 将 1 中的a1 a3互换位置 得到 3 可以用循环重复执行 交换位置 后跟剩余序列的所有排列 对剩余的序列再使用该方法 直至没有剩余序列 递归调用 由排列组合的知识可知 n个元素的全排列共有n 种 n 可分解为n n 1 种 而 n 1 又分解为 n 1 n 2 种 依次类推 若用一个数组a n 来保存1 n之间的n个自然数 对于i 1 n 每次使a 1 同a i 交换后 对a 2 a n 中的n 1个元素进行全排列 然后再交换a 1 与a i 的值 使它恢复为此次排列前的状态 同样 对于a 3 a n 区间内的n 2个元素进行全排列 然后再把交换的元素交换回来 依次类推 直到对a n 进行全排列时 输出整个数组的值 即得到一种排列结果 n 3123132213231321312 n 4123412431324134214321423213421432314234124312413 321432413124314234123421423142134321431241324123 procedurerange a k n ifk nthenprint a elsefori ktondo a k a i callrange a k 1 n a k a i endifendrange 对于n个元素a a1a2 ak an 设过程range a k n 是求a的第k到第n个元素的全排列 算法如下 procedurerange a k n 当k指向最后元素时 递归终止 输出相应的字符串a否则i从k到n重复执行 交换ak与ai range a k 1 n 交换ak与ai endrange VoidPerm Typelist intk intm 递归的产生前缀是list 0 k 1 后缀是list k m 的全排列的所有排列if k m 只剩下一个元素for inti 0 i m i cout list i cout endl else 还有多个元素待排列 递归产生排列for inti k i m i Swap list k list i Perm list k 1 m Swap list k list i 为什么需要交换两次 举个例子比如现在数组的数据是123算法是这样的1和3先交换变成了321然后递归