[leetcode]Permutations

新博文地址：[leetcode]Permutations

Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

 给你一个数组，求该数组的排列。

如果不了解排列的话，最好先去熟悉一下排列组合的相关概念，对于n个数来说，其排列数组一共有n！种情况，简单起见，我们假设 n-1个数的排列情况已经知道了，

例如[1,2]的排列情况一共有2种[1,2]，[2,1]，则添加3的时候，要注意对每个数组，3的位置都有三种情况，比如对于[1,2]来讲，□1□2□，3可能出现在三个方框显示的位置，因此就有三种情况，[3,1,2]、[1,3,2]、[1,2,3]同理[2,1]插入3之后也有三种情况，而且，这6种情况不会有交集，因为1，2的顺序已经限定了，前三种和后三种必定没有交集

既然这种思想要求我们知道n-1个数的排列情况，那么就可以用两种算法来实现：

1. 自底向上的递推

2. 自顶向下的递归

 

loop算法：

	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	public ArrayList<ArrayList<Integer>> permute(int[] num){
		if(num == null || num.length == 0){
			return result;
		}
		ArrayList<Integer> tem = new ArrayList<Integer>();
		tem.add(num[0]);
		result.add(tem);
		for(int i = 1; i < num.length; i++ ){//自底向上进行递推
			int n = num[i];
			int count = 0;
			for(; count < factorial(i);count++){
				ArrayList<Integer> list = result.get(count);
				generateNewLists(list,n);
			}
			for(count = 0 ; count < factorial(i); result.remove(0),count++);//删除旧节点
		}
		return result;
	}
	private int factorial(int n){//计算n的阶乘
		int result = 1;
		for(int i = 1; i <= n; result *= i,i++);
		return result;
	}
	private void generateNewLists(ArrayList<Integer> list ,int n){//由n-1的排列，插入n之后形成新的排列
		int size = list.size();
		for(int i = 0; i <= size; i++){
			ArrayList<Integer> newList = new ArrayList<Integer>();
			int num = 0;
			for(int j = 0; j < list.size(); j++){
				if(num == i){
					newList.add(n);
				}
				newList.add(list.get(j));
				num++;
			}
			if(i == size){
				newList.add(n);
			}
			result.add(newList);
		}
	}

 

递归版本（大致思想差不多，只是实现上的区别，递归代码稍微短一点，但是效率略低）

	public ArrayList<ArrayList<Integer>> permuteWithCursor(int[] num){
		if(num == null || num.length == 0){
			return new ArrayList<ArrayList<Integer>>();
		}
		return dfs(num,num.length - 1);
	}
	
	public ArrayList<ArrayList<Integer>> dfs(int[] num,int n ){
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if(n == 0){
			ArrayList<Integer> list = new ArrayList<Integer>();
			list.add(num[n]);
			result.add(list);
			return result;
		}
		ArrayList<ArrayList<Integer>> prePermutation = dfs(num,n - 1);
		for(ArrayList<Integer> list : prePermutation){
			int size = list.size();
			for(int i = 0; i <= size; i++){//具体实现与loop版本相同
				ArrayList<Integer> newList = new ArrayList<Integer>();
				int count = 0;
				for(int j = 0; j < list.size(); j++){
					if(count == i){
						newList.add(num[n]);
					}
					newList.add(list.get(j));
					count++;
				}
				if(i == size){
					newList.add(num[n]);
				}
				result.add(newList);
			}
		}
		return result;
	}