| 全排列问题（基于元素交换的算法的C++实现） | 您所在的位置：网站首页 › 全排列的算法 › 全排列问题（基于元素交换的算法的C++实现） |
|
一、题目
生成1~n的全排列 二、解题思路我们尝试用递归的思想解决： 1与1交换，继续求子问题(2,3,...,n)的子问题。2与1交换，继续求子问题(1,3,...,n)的子问题。3与1交换，继续求子问题(2,1,...,n)的子问题。................................ n与1交换，继续求子问题(2,3,...,1)的子问题。这样每个数开头一次，递归求解剩下序列的排序，即可得到n个数的全排列。假如 我们有1,2,3,4，下面我们用上述思想生成1,2,3,4的全排列。 首先，1与1交换，在继续求子问题（2,3,4），该子问题又分为三种子问题，一种是2和2交换，继续求子问题（3,4）接下来继续求子问题（3,4），一种是3和3交换，剩下子问题{4}，单独元素，直接返回排列为（1,2,3,4），另一种是4和3交换，剩下子问题{3}， 单独元素，直接返回（1,2,4,3）；另一个是3和2交换，继续求（2,4）的子问题，接下来继续求子问题（2,4），一种是2和2交换，剩下子问题{4}，单独元素，直接返回排列为（1,3,2,4），另一种是4和2交换，剩下子问题{2}， 单独元素，直接返回（1,3,4,2）；最后一种是4和2交换，继续求（3,2）的子问题，接下来继续求子问题（3,2），一种是3和3交换，剩下子问题{2}，单独元素，直接返回排列为（1,4,3,2），另一种是3和2交换，剩下子问题{2}， 单独元素，直接返回（1,4,2,3）。2与1交换，继续求子问题(1,3,4)的子问题。略3与1交换，继续求子问题(2,1,4)的子问题。略4与1交换，继续求子问题(2,3,1)的子问题。略 三、代码编写 #include #define N 100 using namespace std; //保存待排列数组 int a[N] = {0}; //记录需要排列元素个数 int length = 0; //交换数组的两个数，参数为数组索引 void swap(int s,int t){ int temp = a[t]; a[t] = a[s]; a[s] = temp; } //index表示从第index开始，计算index到n的的全排列， //即dfs(1)代表从第一数算起，生成1-n的全排列 void dfs(int index){ if(index > length){ for(int i = 1;i |
| CopyRight 2018-2019 实验室设备网 版权所有 |