全排列是指n个数(或其他字符)所有可能的排列顺序，例如1 2 3三个数字的全排列是

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

那么问题来了，任意输入一个大于1的数字n，列出1-n这n个数字的全排列。

如果尝试手动列举一下1 2 3的全排列，会发现通常我们会在头脑中制定好规则，并按照既定规则进行枚举，从而得到所有排列。

在这里我们制定的规则是：

（想象我们手里拿了3个数字，地上有A、B、C三个空位）

1)在每一个空位前，都按照1->2->3的顺序尝试放下一个数字，如果该数字已经放下则尝试下一个

2)每放下一个数字后向后移动一格，然后重复1->2->3的尝试

3)如果当前位置没有新的可能性，取回当前位置的数字并左移一格从新尝试

按上面规则很容易推算出第一种排列是1 2 3

取回3，返回B位置，取回2，然后按1->2->3尝试，发现可以放下3，右移到C，尝试后放下2，得到1 3 2

接下来必须返回到A的位置才有新的可能性，此时已经取回所有数字，按规则放下2，移到B，放下1，移到C，放下3，得到2 1 3

。。。

下面来看实现的代码：

  1. public class Permutation {
  2. private int max;
  3. private int[] array;
  4. private int[] hold;
  5. public Permutation(int max) {
  6. this.max = max;
  7. array = new int[max + 1];
  8. hold = new int[max + 1];
  9. }
  10. public void permute(int step) {
  11. if(step == max + 1) {
  12. for(int i = 1; i <= max; i++) {
  13. System.out.print(array[i] + " ");
  14. }
  15. System.out.println();
  16. return;  //返回上一步, 即最近一次调用permute方法的后一行
  17. }
  18. //按照1->2->3->...->n的顺序尝试
  19. for(int num = 1; num <= max; num++) {
  20. //判断是否还持有该数字
  21. if(hold[num] == 0) {
  22. array[step] = num;
  23. hold[num] = 1;
  24. //递归: 右移一格重复遍历数字的尝试
  25. permute(step + 1);
  26. //回到当前位置时取回当前位置数字
  27. hold[num] = 0;
  28. }
  29. }
  30. }
  31. public static void main(String[] args) {
  32. Permutation fa = new Permutation(3);
  33. fa.permute(1);
  34. }
  35. }

运行输出

  1. 1 2 3
  2. 1 3 2
  3. 2 1 3
  4. 2 3 1
  5. 3 1 2
  6. 3 2 1

我们用一个伪时序图来帮助理解递归调用的执行过程

顺便说一句，全排列问题还有多种算法，本文中使用的是深度优先算法的模型。

最新文章

  1. OpenCASCADE6.8.0 Reference Manual Serach Problem
  2. ACL
  3. Java编程思想学习(十一) 泛型
  4. latex输入希腊字母
  5. Android系统SVC命令教程
  6. AC题目简解-线段树
  7. spoj SORTBIT - Sorted bit squence
  8. jquery如何判断滚动条滚到页面底部并执行事件
  9. UVa 825 - Walking on the Safe Side
  10. jQuery EasyUI的使用入门
  11. java.io.IOException: Invalid header signature; read 0xE011BDBFEFBDBFEF, expected 0xE11AB1A1E011CFD0
  12. JS通过decodeURIComponent函数解码
  13. BitmapToASCii
  14. a,b,c为3个整型变量,在不引入第四个变量的前提下写一个算法实现 a=b b=c c=a?(异或解决值互换问题)
  15. 使用ROME解析rss，如何获取icon图标
  16. Windows PowerShell 入門（4）－変数と演算子
  17. html学习笔记之2——多媒体
  18. 四、UI开发之核心基础——约束（实用）
  19. XCode - App installation failed (A valid provisioning profile for this executable was not found)
  20. 应用程序发生异常 unknown software exception (0xc00000fd)... - 栈溢出(Stack overflow)

热门文章

  1. SQL Server-聚焦ROW_NUMBER VS TOP N性能
  2. java8 新特性入门 stream/lambda
  3. iOS转场动画封装
  4. PredictionIO+Universal Recommender快速开发部署推荐引擎的问题总结(1)
  5. 利用VSTS跟Kubernetes进行CI/CD
  6. rtmp流媒体搭建的所需安装包
  7. 简单记录一下原生ajax
  8. 设计模式之 - 模板模式（Template Pattern）
  9. PHP 购物车 php闭包 array_walk
  10. Mobiscroll的介绍【一款兼容PC和移动设备的滑动插件】