算法笔记03--归纳法之生成排列

本文主要是介绍算法笔记03--归纳法之生成排列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

生成排列

生成排列即对n个数的全排列，显然时间复杂度是n指数级的O(n^k)

假定可以生成n-1个数的所有排列，那么就可以扩展生成1,2,.....,n的排列。

例如1的生成排列即1

1,2的生成排列即1,2和2,1

1,2,3的生成排列在1,2的生成排列基础上可以这样得到：

1在第1位，2,3的生成排列

2在第1位，1,3的生成排列

3在第1位，2,3的生成排列

那么推广到1,2,...,n的生成排列即：

1在第1位，2,...,n的生成排列

2在第2位，1,3,...n的生成排列

....

n在第1位，2,...,n的生成排列

先考虑数字1在第一位，那么对2,,...,n生成排列，

思路：

1.对0到n-1位置上的数字生成排列，具体做法从1,,..,n中按序拿出数字i(i从1开始到n)与位置j(j从0开始到n-1)上的数字交换，再对位置j+1到n-1位置上的数字生成排列。

2.对j(j从1开始)到n-1位置上的数字生成排列，具体做法从2,,..,n中按序拿出数字i(从2开始)与位置j上的数字交换，再对位置j+1到n-1位置上的数字生成排列。

3.......当j = n时，生成一个排列并打印

4. 回溯上一步，拿出数字i+1与j上的数字交换，并对j+1后面的序列生成排序

5. 直到i>n，结束

#include <iostream>  
using namespace std; void permutation(int* array, int iLength, int iCurStep)
{if(iLength == iCurStep) //若固定位置指针指到最后一个数字打印数组{	for(int i=0;i<iLength;i++){cout<<array[i]<<" ";}cout<<"\n";return ;}else{for(int i = iCurStep ; i<iLength ; i++)  //i为从固定指针位置到最后一个数字位置的扫描指针{swap(array[iCurStep],array[i]); //固定从iCurStep起每个位置上的数字到iCurStep上permutation(array,iLength,iCurStep+1);swap(array[i],array[iCurStep]); //复原array}}
}int main(){ int array[] = {1,2,3,4}; permutation(array, 4, 0); 
}