全排列递归方法（permutation原理

https://blog.csdn.net/axiqia/article/details/50967863 原博客

（一）递归的全排列算法

（A、B、C、D）的全排列为

1、A后面跟（B、C、D）的全排列

2、B后面跟（A、C、D）的全排列（A与B交换，其他次序保持不变）

3、C后面跟（B、A、D）的全排列（A与C交换，其他次序保持不变）

4、D后面跟（B、C、A）的全排列（A与D交换，其他次序保持不变）

用数字举例方便点：

1234
1243
1324
1342
1432
1423
2134
....
3214
3214
3241
3124
3142
3412
3421
4231

为观察规律，仅仅标红1234全排列中最高位首次1,2,3,4的排列。

解释：

以1234为基础（代码中第二次交换的意义），同为第一层递归的4种状态分别为：

第一位和第一位交换（234==》1234）；

第一位和第二位交换（34==》2134）；

第一位和第三位交换（24==》3214）；

第一位和第四位交换（23==》4123）。

为保证普遍性，选第三种状态继续递归：

以3214为基础，同为第二层递归的三种状态分别为：

第二位和第二位交换（314==》3214）；

第二位和第三位交换（34==》3124）；

第二位和第四位交换（31==》3412）。

继续递归即可。

 #include <iostream>

 #include <cstdio>

 using namespace std;

 void permutation(int k, int n, int a[])

 {

     //递归到底层

     if(k == n-)

     {

         for(int i = ; i < n; i ++)

             printf("%d", a[i]);

         printf("\n");

     }

     else

     {

         for(int i = k; i < n; i ++)

         {

             int temp = a[k];

             a[k] = a[i];

             a[i] = temp;

             //交换后递归下一层

             permutation(k+, n, a);

             //保证每一层递归后保持上一层的顺序

             temp = a[k];

             a[k] = a[i];

             a[i] = temp;

         }

     }

 }

 int main()

 {

     int a[];

     int n;

     scanf("%d", &n);

     for(int i = ; i < n; i ++)

         a[i] = i+;

     permutation(, n, a);

     return ;

 }

不过输出的格式有点偏差

巴特西

全排列递归方法（permutation原理

最新文章

热门文章

巴特西

全排列 递归方法（permutation原理

最新文章

热门文章

全排列递归方法（permutation原理