数字全排列

问题描述

给一个不重复的数字数组，写一个程序，输出全排列。

比如给定数组：

[1, 2, 3]

输出：

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

解决思路

这个问题很经典，接下来尝试使用数学归纳法的思想来解决这个问题。

在中学的时候，我们就知道一个长度为n的数列有n!个排列。因为第一个数字有n种情况，第二个数字有n-1种情况，第三个数字有n-2种情况……第n个数字只有一种情况了，用公式表示就是n*(n-1)*(n-2)….*1 = n!

我们换一个思维来考虑，以数组[1,2,3]为例，它的全排列为：

第一个数字为1的其他两个数字的全排列 + 第一个数字为2的其他两个数字的全排列 + 第一个数字为3的其他两个数字的全排列。

那么两个数字的全排列怎么算呢，以[1,2]为例，就是：

第一个数字为1的剩下的数的全排列 + 第一个数字为2的剩下的数的全排列。

因为剩下的只有一个数，就不用继续了，到这就可以输出了。

依次类推到n个数字的全排列：

设数组 p = {r1, r2, r3, r4, r5…., rn}，设p的全排列为perm(p)，设pn = p - {rn}。那么perm(p) = { r1, perm(p1) } + { r2, perm(p2) } + {r3, perm(p3) } + …… + {rn, perm(pn) }。同样思路，也可以算出perm(p1), perm(p2), perm(p3)……perm(pn)。继续，就可以使用递归求解了，递归的出口就是perm求的全排列数组里面只有一个值。

代码实现

下面是java的实现代码：

import java.util.Arrays; public class Test { public static void main(String[] args) { int[] arr = {1,2,3}; Test t = new Test(); t.perm(arr, 0, arr.length); } //求数组全排列 public void perm(int[] nums, int start, int len) { //判断递归出口，当start == len - 1时，也就是要做的全排列只有一个值 ，那么就可以输出了 if(start == len - 1) { System.out.println(Arrays.toString(nums)); }else { /* * 没有到递归出口时，这一段代码是关键 * for循环模拟的是： * { r1, perm(p1) } + { r2, perm(p2) } + {r3, perm(p3) } + …… + {rn, perm(pn) } * 从r1, r2, r3 一直到 rn 作为第一位，求剩下的全排列 */ for(int i = start; i < len; i++) { swap(nums, start, i);//通过交换，依次将每个数放在第一位 perm(nums, start + 1, len);//递归调用 swap(nums, start, i);//交换回来，保证原数组不会变，以进行下一轮全排列 } } } //交换数组中的两个值 public void swap(int[] nums, int i, int j) { int tem = nums[i]; nums[i] = nums[j]; nums[j] = tem; } }

输出结果：

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2]

参考：

http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1191914.html

https://blog.csdn.net/randyjiawenjie/article/details/6313729

转载于:https://www.cnblogs.com/scuwangjun/p/9005914.html

相关资源：数据结构—成绩单生成器