最新全排列算法设计和分析课件PPT.ppt 13页

'全排列算法设计和分析 两个例子123的全排列--首先遍历元素,然后把遍历到的每一个元素都和第一个元素交换第一个和第一个交换就是1和1交换最后还是123那么就形成了123 213 321这样的3组(交换后再换回来还原成123因为后面的交换都是在123的基础上交换的所以swap要写2次)-检查每一组除了第一个之外的剩余元素，如果这些元素个数是2，那么就对这剩下的2个元素全排列就是123132, 213231,3213122个元素的全排列很简单就是把这2个元素交换位置就OK） 两个例子1234的全排列--首先遍历元素,然后把遍历到的每一个元素都和第一个元素交换那么就形成了1234 2134 32144231这样的4组-检查每一组除了第一个之外的剩余元素，如1234剩余的是234，发现是3个元素那么问题就转换为求234的全排列了接下来也是一样问题转换为求134，214，231的全排列像这样总是对除了第一个之外的元素全排列，每次元素的个数都在减少一个，求N个元素全排列最终就变成求2的元素的全排列了 VoidPerm(Typelist[],intk,intm){//递归的产生前缀是list[0:k-1]后缀是list[k:m]的全排列的所有排列if(k==m){//只剩下一个元素for(inti=0;i<=m;i++)cout<