首页 > 代码库 > 全排列的递归实现
全排列的递归实现
对于全排列问题，假设我们有n个不同的数字，需要对其进行全排列，那么全排列的总数为f(n)，f(n) = n * f(n - 1)。我们可以看做是将第一个数字固定，然后对后边n-1个数字进行全排，这样第一个数字就有n种选择。同理，在求f(n - 1)时，可以看做第二个数字固定，后边n-2个数字进行全排，这样第二个数字就有n-2种选择。具体算法如下：
1 int swap(int &a, int &b) 2 { 3 int tmp = a; 4 a = b; 5 b = tmp; 6 } 7 8 void Print(int *a, int len) 9 {10 for(int i = 0; i != len; ++i)11 cout << a[i] << " ";12 cout << endl;13 }14 15 void Permutation(int *a, int start, int len)16 {17 if(start == len) //当到达末尾时输出整个数组18 {19 Print(a, len);20 return;21 }22 23 for(int i = start; i != len; ++i) //第i个数有n-i+1中选择24 {25 swap(a[i], a[start]); //为了保证每一次第一个数不同，让其与后边的数字依次调换26 Permutation(a, start + 1, len);27 swap(a[i], a[start]); //进行全排后再次调换回去，防止多次调换同一个数28 }29 }
全排列的递归实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。