全排列
带重复元素的排列
下一个排列
上一个排列
第 k 个排列
排列序号
排列序号II
全排列
给定一个数字列表，返回其所有可能的排列。

注意事项

你可以假设没有重复数字。
样例
给出一个列表[1,2,3]，其全排列为：

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

分析

可以用递归和非递归解决

首先递归法，也是利用了回溯法和深度优先搜索。

我们考虑一个一个将数组元素加入到排列中，递归求解，就好像下面的解答树：

添加的时候排除掉相同的元素即可，回溯法我们经常会设置一个已访问标识数组，来表示数组被访问过，但这里不用这样，因为如果list里面已经包含就说明已经访问过了，所以只要判断，跳过已有的元素即可。
再考虑递归的结束条件，当元素都添加足够就结束了，添加足够的意思就是，元素个数等于数组的长度。

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    public List<List<Integer>> permute(int[] nums) {
		List<List<Integer>> res = new ArrayList<>();
		if(nums == null)
			return res;
		if(nums.length == 0)
		{	
			res.add(new ArrayList<Integer>());
			return res;
		}
			
		ArrayList<Integer> list = new ArrayList<>();
		dfs(res, list, nums);
		return res;
   }

	private void dfs(List<List<Integer>> res, ArrayList<Integer> list, int[] nums) {
		
		int n = nums.length;
		if(list.size() == n)
		{	
			res.add(new ArrayList<Integer>(list));
			return;
		}
		
		for(int i = 0;i < n;i++) {
			if(list.contains(nums[i]))
				continue;
			list.add(nums[i]);
			dfs(res, list, nums);
			list.remove(list.size() - 1);
		}
	}
}

非递归实现
思路是这样的，就是高中的排列组合知识，运用插入法即可，假设有i个元素的排列组合，那么对于i+1个元素，可以考虑就是将i+1的元素插入到上述的排列的每一个位置即可。

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    public List<List<Integer>> permute(int[] nums) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();  
        if ( nums == null)  
            return res;
        if( nums.length == 0)
        {    
            res.add(new ArrayList<Integer>());
            return res;
        }
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        res.add(new ArrayList<Integer>(list));
        
        for(int i=1;i<nums.length;i++) {
        	int size1 = res.size();
        	for(int j=0;j<size1;j++) {
        		int size2 = res.get(0).size();
        		for(int k=0;k<=size2;k++) {
        			ArrayList<Integer> temp = new ArrayList<>(res.get(0));
        			temp.add(k,nums[i]);
        			res.add(temp);
        		}
        		res.remove(0);
        	}
        }
        return res;
   }
}

带重复元素的全排列

给出一个具有重复数字的列表，找出列表所有不同的排列。

样例
给出列表 [1,2,2]，不同的排列有：

代码

class Solution {
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
	    
        ArrayList<List<Integer>> res = new ArrayList<>();
        
        if(nums == null)
        	return null;
        
        if(nums.length == 0)
        {	
        	res.add(new ArrayList<Integer>());
        	return res;
        }
        
        ArrayList<Integer> list = new ArrayList<>();
        
        //先将数组排序，这样相同元素将会出现在一起
        Arrays.sort(nums);
        
        int n = nums.length;
        int[] visited = new int[n];
        for(int i=0;i<n;i++)
        	visited[i] = 0;//0标识未访问
        
        helper(res, list, visited, nums);
        return res;
    }

	private void helper(ArrayList<List<Integer>> res, ArrayList<Integer> list, int[] visited, int[] nums) {
		
		if(nums.length == list.size()) {
			res.add( new ArrayList<Integer>(list));
		}
		
		for(int i=0;i<nums.length;i++) {
			
			if(visited[i] == 1 || i!= 0 && (visited[i-1] == 0 && nums[i] == nums[i-1]))
				continue;
			/*
            上面的判断主要是为了去除重复元素影响。
            比如，给出一个排好序的数组，[1,2,2]，那么第一个2和第二2如果在结果中互换位置，
            我们也认为是同一种方案，所以我们强制要求相同的数字，原来排在前面的，在结果
            当中也应该排在前面，这样就保证了唯一性。所以当前面的2还没有使用的时候，就
            不应该让后面的2使用。
            */
			list.add(nums[i]);
			visited[i] = 1;
			helper(res, list, visited, nums);
			list.remove(list.size()-1);
			visited[i] = 0;
			
		}
			
		
	}
}

下一个排列

给定一个若干整数的排列，给出按正数大小进行字典序从小到大排序后的下一个排列。

如果没有下一个排列，则输出字典序最小的序列。

样例
左边是原始排列，右边是对应的下一个排列。

1,2,3 → 1,3,2

3,2,1 → 1,2,3

1,1,5 → 1,5,1

分析

这道题让我们求下一个排列顺序，有题目中给的例子可以看出来，如果给定数组是降序，则说明是全排列的最后一种情况，则下一个排列就是最初始情况，可以参见之前的博客 Permutations 全排列。我们再来看下面一个例子，有如下的一个数组
1　　2　　7　　4　　3　　1
下一个排列为：
1　　3　　1　　2　　4　　7
那么是如何得到的呢，我们通过观察原数组可以发现，如果从末尾往前看，数字逐渐变大，到了2时才减小的，然后我们再从后往前找第一个比2大的数字，是3，那么我们交换2和3，再把此时3后面的所有数字转置一下即可，步骤如下：
1　　2　　7　　4　　3　　1
1　　2　　7　　4　　3　　1
1　　3　　7　　4　　2　　1
1　　3　　1　　2　　4　　7

所以我们要做的就是找到第一个比peak元素大的数字，交换，然后反转

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: return nothing (void), do not return anything, modify nums in-place instead
     */
    public int[] nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
        return nums;
    }

    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

上一个排列

给定一个整数数组来表示排列，找出其上一个排列。

注意事项

排列中可能包含重复的整数

样例
给出排列[1,3,2,3]，其上一个排列是[1,2,3,3]

给出排列[1,2,3,4]，其上一个排列是[4,3,2,1]

分析

与求下一个排列是一样的方法，只是相应的操作变反即可

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A list of integers that's previous permuation
     */
    public void swapItem(ArrayList<Integer> nums, int i, int j) {
		Integer tmp = nums.get(i);
		nums.set(i, nums.get(j));
		nums.set(j, tmp);
	}
	public void swapList(ArrayList<Integer> nums, int i, int j) {
		while ( i < j) {
			swapItem(nums, i, j);
			i ++; j --;
		}
	}
    public ArrayList<Integer> previousPermuation(ArrayList<Integer> nums) {
		int len = nums.size();
		if ( len <= 1)
			return nums;
		int i = len - 1;
		while ( i > 0 && nums.get(i) >= nums.get(i-1) )
			i --;
		swapList(nums, i, len - 1);     
		if ( i != 0) {
			int j = i;
			while ( nums.get(j) >= nums.get(i-1) ) j++;
			swapItem(nums, j, i-1);
		}
		
		return nums;
    }
}

第k个排列

给定 n 和 k，求123..n组成的排列中的第 k 个排列。

注意事项

1 ≤ n ≤ 9

样例
对于 n = 3, 所有的排列如下：

123
132
213
231
312
321
如果 k = 4, 第4个排列为，231.

分析

康托展开的公式：（不用记，看形势就行，下面会有例子）

X=an(n-1)!+an-1(n-2)!+…+ai(i-1)!+…+a21!+a1*0!

ai为整数，并且0<=ai<i(1<=i<=n)

适用范围：没有重复元素的全排列

N个数的第k个排序，例子，1，2，3，4共有4！种排列，1234,1243,1324等等。按顺序应该是

1234

1243

1324

1342

1423

1432等等

可以通过STL中next_permutation（begin, end）;来算下一个全排列，理论上你要算n个数的第k个排列只要调用k-1次next_permutation()就行，但是一般来说肯定会超时的，因为next_permutation的时间复杂度是O(n)（如果自己写出来next_permutation时间复杂度比n大就要注意了，其中一个容易疏忽的地方是最后排序可以用reverse而不是sort）。所以如果用这个的话时间复杂度是O(N^2)。

而用康托展开只要O(n)就行，下面来说说具体怎么做:

题目：找出第16个n = 5的序列（12345）

首先第十六个也就是要前面有15个数，要调用15次next_permutation函数。

根据第一行的那个全排列公式，15 / 4! = 0 …15 =》有0个数比他小的数是1，所以第一位是1

拿走刚才的余数15，用15 / 3! = 2 …3 => 剩下的数里有两个数比他小的是4（1已经没了），所以第二位是4

拿走余数3，用 3 / 2! = 1 …1 =》剩下的数里有一个数比他小的是3，所以第三位是3

拿走余数1，用 1/ 1! = 1 …0 => 剩下的数里有一个数比他小的是 5（只剩2和5了），所以第四位是5

所以排列是 1,4,3,5,2

class Solution {
    /**
      * @param n: n
      * @param k: the kth permutation
      * @return: return the k-th permutation
      */
    public String getPermutation(int n, int k) {
        
        StringBuilder sb = new StringBuilder();
        boolean[] used = new boolean[n];

        k = k - 1;
        int factor = 1;
        for (int i = 1; i < n; i++) {
            factor *= i;
        }

        for (int i = 0; i < n; i++) {
            int index = k / factor;
            k = k % factor;
            for (int j = 0; j < n; j++) {
                if (used[j] == false) {
                    if (index == 0) {
                        used[j] = true;
                        sb.append((char) ('0' + j + 1));
                        break;
                    } else {
                        index--;
                    }
                }
            }
            if (i < n - 1) {
                factor = factor / (n - 1 - i);
            }
        }

        return sb.toString();
        
    }
}

排列序号

给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始。

样例
例如，排列 [1,2,4] 是第 1 个排列。

分析

这道题是求第k个排列的反向思维

已知是n = 5，求14352是它的第几个序列？（同一道题）

用刚才的那道题的反向思维：

第一位是1，有0个数小于1，即0* 4！

第二位是4，有2个数小于4，即2* 3！

第三位是3，有1个数小于3，即1* 2！

第四位是5，有1个数小于5，即1* 1！

第五位是2，不过不用算，因为肯定是0

所以14352是 n = 5的第 0 + 12 + 2 + 1 + 0 = 15 + 1（求的是第几个，所以要加一） = 16

第16个，跟刚才那道题一样，证明对了

public class Solution {
    /**
     * @param A an integer array
     * @return a long integer
     */
    public long permutationIndex(int[] A) {
        // Write your code here
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
		
		for (int i = 0; i < A.length; i++) {
			if (hash.containsKey(A[i]))
				hash.put(A[i], hash.get(A[i]) + 1);
			else {
				hash.put(A[i], 1);
			}
		}
		long ans = 0;
		for (int i = 0; i < A.length; i++) {
			for (int j = i + 1; j < A.length; j++) {
				if (A[j] < A[i]) {
					hash.put(A[j], hash.get(A[j])-1);
					ans += generateNum(hash);
					hash.put(A[j], hash.get(A[j])+1);
					
				}
			
			}
				hash.put(A[i], hash.get(A[i])-1);
		}
		
		return ans+1;
    }
    
    long fac(int numerator) {
			
		long now = 1;
		for (int i = 1; i <= numerator; i++) {
			now *= (long) i;
		}
		return now;
	}

	long generateNum(HashMap<Integer, Integer> hash) {
		long denominator = 1;
		int sum = 0;
		for (int val : hash.values()) {
			if(val == 0 )	
				continue;
			denominator *= fac(val);
			sum += val;
		}
		if(sum==0) {
			return sum;
		}
		return fac(sum) / denominator;
	}
}

排列序号II

给出一个可能包含重复数字的排列，求这些数字的所有排列按字典序排序后该排列在其中的编号。编号从1开始。

样例
给出排列[1, 4, 2, 2]，其编号为3。

分析

这道题基于查找不存在重复元素中排列序号的基础之上，

即P(n) = P(n-1)+C(n-1)

C(n-1) = (首元素为小于当前元素，之后的全排列值)
P(1) = 1;

而不存在重复元素的全排列值C(n-1) = (n-1)!*k(k为首元素之后小于当前元素的个数)

在存在重复元素的排列中首先全排列的值的求法变为：

C(n-1) = (n-1)!/(A1!A2!···Aj!)k(其中Ai 为重复元素的个数，k为小于首元素前不重复的个数)

/**
     * @param A an integer array
     * @return a long integer
     */
    long fac(int numerator) {
        long now = 1;
        for (int i = 1; i <= numerator; i++) {
            now *= (long) i;
        }
        return now;
    }   
    long generateNum(HashMap<Integer, Integer> hash) {
        long denominator = 1;
        int sum = 0;
        for (int val : hash.values()) {
            if(val == 0 )    
                continue;       
            denominator *= fac(val);
            sum += val; 
        }       
        if(sum==0) {
            return sum; 
        }       
        return fac(sum) / denominator;
    }   

    public long permutationIndexII(int[] A) {
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();

        for (int i = 0; i < A.length; i++) {
            if (hash.containsKey(A[i]))
                hash.put(A[i], hash.get(A[i]) + 1);
            else {      
                hash.put(A[i], 1);
            }           
        }       
        long ans = 0;
        for (int i = 0; i < A.length; i++) {
            HashMap<Integer, Integer> flag = new HashMap<Integer, Integer>(); 

            for (int j = i + 1; j < A.length; j++) {
                if (A[j] < A[i] && !flag.containsKey(A[j])) {
                    flag.put(A[j], 1);
                    hash.put(A[j], hash.get(A[j])-1);
                    ans += generateNum(hash);
                    hash.put(A[j], hash.get(A[j])+1);
                }

            }
            hash.put(A[i], hash.get(A[i])-1);
        }
        return ans + 1;
    }