一组数据的全排列

问题描述

int[] nums数组，数组中没有重复的数字，求这些数字能够组成的所有排列。

例如：

输入：[2,5,3]

输出：[[2,5,3],[2,3,5],[5,2,3],[5,3,2],[3,2,5],[3,5,2]]

问题分析

全排列，经典的数学问题。像问题描述中的这个例子，我们自己也能心算出来，甚至就算输入的是4个数，我们也能拿笔纸算出来。但是，如果输入的数组中的整数个数，达到5个、6个，甚至是100个的时候，你还能用笔算出来吗，就算能算出来，也得耗费大量的时间，还担心出错。而计算机程序解决此类问题，有得天独厚的优势，它计算速度快、结果精确，擅长做递归调用。好，面对这个问题，首先我们就要将它分解，分解得足够小，小到只是初始条件不同，而执行的动作完全是一样的地步，便于计算机执行。

对于一个排列来说，它的最小单元，就是它的一个位置上的取值，例如[2,5,3]，它有3个位置用来放置3个数据，所以它有3个单元，每个单元有什么不同呢，假如第一个位置上放了5，那么第2个位置，就只能放2和3了，很显然，每个单元放置数据时面对的可选数据不同，但执行的动作是一样，就是把符合条件的数据放到对应的位置。java程序中，循环结构，恰好就能够作为当前问题的一个最小单元，循环条件就是该位置所能放置的所有取值，循环体内部，我们用一个列表将当前的临时排列存储起来，并将当前的数值标记为已使用，接着进入下一个位置的放置操作，对应程序就是递归调用，调用完毕后，再将当前数值标记为未使用，为当前位置取下一个有效值作准备，s当临时列表的长度，等于初始输入数组的长度时，我们就得到了其中的一个排列，将其放置到结果列表中，当程序运行完，结果列表就是我们需要的全排列。

代码实现

@Test

public voidtestPermute() {

int[] nums={1,,3};

newSolution().permute(nums);

}

classSolution {

privateList

>result

=newLinkedList();

private intlength;

private int[]arr;

private boolean[]visit;

publicList

> permute(int[] nums) {

if(nums ==null|| nums.length==) {

returnCollections.emptyList();

}

length= nums.length;

arr= nums;

//用来记录数组中某个值是否已被使用

visit=new boolean[length];

generate(newLinkedList());

System.out.println("result: "+result);

returnresult;

}

private voidgenerate(List temp) {

//得到了其中一个排列

if(temp.size() ==length) {

result.add(newLinkedList(temp));

return;

}

//每个位置，都有权利取遍所有值

for(inti =; i

//前提是这个值没有被别的位置使用

if(!visit[i]) {

temp.add(arr[i]);

visit[i] =true;

//递归，进入下一个位置

generate(temp);

//回溯，重新安排当前位置取值

temp.remove(temp.size() -1);

visit[i] =false;

}

}

}

}