# Permutations
### Source
- leetcode: [Permutations | LeetCode OJ](https://leetcode.com/problems/permutations/)
- lintcode: [(15) Permutations](http://www.lintcode.com/en/problem/permutations/)
### Problem
Given a list of numbers, return all possible permutations.
#### Example
For nums = `[1,2,3]`, the permutations are:
~~~
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
~~~
#### Challenge
Do it without recursion.
### 题解1 - Recursion(using subsets template)
排列常见的有数字全排列，字符串排列等。
使用之前 [Subsets](http://algorithm.yuanbin.me/zh-cn/exhaustive_search/subsets.html) 的模板，但是在取结果时只能取`list.size() == nums.size()`的解，且在添加list元素的时候需要注意除重以满足全排列的要求。此题假设前提为输入数据中无重复元素。
### Python
~~~
class Solution:
"""
@param nums: A list of Integers.
@return: A list of permutations.
"""
def permute(self, nums):
alist = []
result = [];
if not nums:
return result
self.helper(nums, alist, result)
return result
def helper(self, nums, alist, ret):
if len(alist) == len(nums):
# new object
ret.append([] + alist)
return
for i, item in enumerate(nums):
if item not in alist:
alist.append(item)
self.helper(nums, alist, ret)
alist.pop()
~~~
### C++
~~~
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int> > permute(vector<int> nums) {
vector<vector<int> > result;
if (nums.empty()) {
return result;
}
vector<int> list;
backTrack(result, list, nums);
return result;
}
private:
void backTrack(vector<vector<int> > &result, vector<int> &list, \
vector<int> &nums) {
if (list.size() == nums.size()) {
result.push_back(list);
return;
}
for (int i = 0; i != nums.size(); ++i) {
// remove the element belongs to list
if (find(list.begin(), list.end(), nums[i]) != list.end()) {
continue;
}
list.push_back(nums[i]);
backTrack(result, list, nums);
list.pop_back();
}
}
};
~~~
### Java
~~~
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0) return result;
List<Integer> list = new ArrayList<Integer>();
dfs(nums, list, result);
return result;
}
private void dfs(int[] nums, List<Integer> list, List<List<Integer>> result) {
if (list.size() == nums.length) {
result.add(new ArrayList<Integer>(list));
return;
}
for (int i = 0; i < nums.length; i++) {
if (list.contains(nums[i])) continue;
list.add(nums[i]);
dfs(nums, list, result);
list.remove(list.size() - 1);
}
}
}
~~~
### 源码分析
在除重时使用了标准库`find`(不可使用时间复杂度更低的`binary_search`，因为`list`中元素不一定有序)，时间复杂度为 O(N)O(N)O(N), 也可使用`hashmap`记录`nums`中每个元素是否被添加到`list`中，这样一来空间复杂度为 O(N)O(N)O(N), 查找的时间复杂度为 O(1)O(1)O(1).
在`list.size() == nums.size()`时，已经找到需要的解，及时`return`避免后面不必要的`for`循环调用开销。
使用回溯法解题的**关键在于如何确定正确解及排除不符条件的解(剪枝)**。
### 复杂度分析
以状态数来分析，最终全排列个数应为 n!n!n!, 每个节点被遍历的次数为 (n−1)!(n-1)!(n−1)!, 故节点共被遍历的状态数为 O(n!)O(n!)O(n!), 此为时间复杂度的下界，因为这里只算了合法条件下的遍历状态数。若不对 list 中是否包含 nums[i] 进行检查，则总的状态数应为 nnn^nnn 种。
由于最终的排列结果中每个列表的长度都为 n, 各列表的相同元素并不共享，故时间复杂度的下界为 O(n⋅n!)O(n \cdot n!)O(n⋅n!), 上界为 n⋅nnn \cdot n^nn⋅nn. 实测`helper`中 for 循环的遍历次数在 O(2n⋅n!)O(2n \cdot n!)O(2n⋅n!) 以下，注意这里的时间复杂度并不考虑查找列表里是否包含重复元素。
### 题解2 - Recursion
与题解1基于 subsets 的模板不同，这里我们直接从全排列的数学定义本身出发，要求给定数组的全排列，可将其模拟为某个袋子里有编号为1到 n 的球，将其放入 n 个不同的盒子怎么放？基本思路就是从袋子里逐个拿球放入盒子，直到袋子里的球拿完为止，拿完时即为一种放法。
### Python
~~~
class Solution:
# @param {integer[]} nums
# @return {integer[][]}
def permute(self, nums):
if nums is None:
return [[]]
elif len(nums) <= 1:
return [nums]
result = []
for i, item in enumerate(nums):
for p in self.permute(nums[:i] + nums[i + 1:]):
result.append(p + [item])
return result
~~~
### C++
~~~
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int> > permute(vector<int>& nums) {
vector<vector<int> > result;
if (nums.size() == 1) {
result.push_back(nums);
return result;
}
for (int i = 0; i < nums.size(); ++i) {
vector<int> nums_new = nums;
nums_new.erase(nums_new.begin() + i);
vector<vector<int> > res_tmp = permute(nums_new);
for (int j = 0; j < res_tmp.size(); ++j) {
vector<int> temp = res_tmp[j];
temp.push_back(nums[i]);
result.push_back(temp);
}
}
return result;
}
};
~~~
### Java
~~~
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> numsList = new ArrayList<Integer>();
if (nums == null) {
return result;
} else {
// convert int[] to List<Integer>
for (int item : nums) numsList.add(item);
}
if (nums.length <= 1) {
result.add(numsList);
return result;
}
for (int i = 0; i < nums.length; i++) {
int[] numsNew = new int[nums.length - 1];
System.arraycopy(nums, 0, numsNew, 0, i);
System.arraycopy(nums, i + 1, numsNew, i, nums.length - i - 1);
List<List<Integer>> resTemp = permute(numsNew);
for (List<Integer> temp : resTemp) {
temp.add(nums[i]);
result.add(temp);
}
}
return result;
}
}
~~~
### 源码分析
Python 中使用`len()`时需要防止`None`, 递归终止条件为数组中仅剩一个元素或者为空，否则遍历`nums`数组，取出第`i`个元素并将其加入至最终结果。`nums[:i] + nums[i + 1:]`即为去掉第`i`个元素后的新列表。
Java 中 ArrayList 和 List 的类型转换需要特别注意。
### 复杂度分析
由于取的结果都是最终结果，无需去重判断，故时间复杂度为 O(n!)O(n!)O(n!), 但是由于`nums[:i] + nums[i + 1:]`会产生新的列表，实际运行会比第一种方法慢不少。
### 题解3 - Iteration
递归版的程序比较简单，咱们来个迭代的实现。非递归版的实现也有好几种，这里基于 C++ STL 中`next_permutation`的字典序实现方法。参考 Wikipedia 上的字典序算法，大致步骤如下：
1. 从后往前寻找索引满足 `a[k] < a[k + 1]`, 如果此条件不满足，则说明已遍历到最后一个。
1. 从后往前遍历，找到第一个比`a[k]`大的数`a[l]`, 即`a[k] < a[l]`.
1. 交换`a[k]`与`a[l]`.
1. 反转`k + 1 ~ n`之间的元素。
### Python
~~~
class Solution:
# @param {integer[]} nums
# @return {integer[][]}
def permute(self, nums):
if nums is None:
return [[]]
elif len(nums) <= 1:
return [nums]
# sort nums first
nums.sort()
result = []
while True:
result.append([] + nums)
# step1: find nums[i] < nums[i + 1], Loop backwards
i = 0
for i in xrange(len(nums) - 2, -1, -1):
if nums[i] < nums[i + 1]:
break
elif i == 0:
return result
# step2: find nums[i] < nums[j], Loop backwards
j = 0
for j in xrange(len(nums) - 1, i, -1):
if nums[i] < nums[j]:
break
# step3: swap betwenn nums[i] and nums[j]
nums[i], nums[j] = nums[j], nums[i]
# step4: reverse between [i + 1, n - 1]
nums[i + 1:len(nums)] = nums[len(nums) - 1:i:-1]
return result
~~~
### C++
~~~
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int> > permute(vector<int>& nums) {
vector<vector<int> > result;
if (nums.empty() || nums.size() <= 1) {
result.push_back(nums);
return result;
}
// sort nums first
sort(nums.begin(), nums.end());
for (;;) {
result.push_back(nums);
// step1: find nums[i] < nums[i + 1]
int i = 0;
for (i = nums.size() - 2; i >= 0; --i) {
if (nums[i] < nums[i + 1]) {
break;
} else if (0 == i) {
return result;
}
}
// step2: find nums[i] < nums[j]
int j = 0;
for (j = nums.size() - 1; j > i; --j) {
if (nums[i] < nums[j]) break;
}
// step3: swap betwenn nums[i] and nums[j]
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
// step4: reverse between [i + 1, n - 1]
reverse(nums, i + 1, nums.size() - 1);
}
return result;
}
private:
void reverse(vector<int>& nums, int start, int end) {
for (int i = start, j = end; i < j; ++i, --j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
};
~~~
### Java
~~~
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0) return result;
Arrays.sort(nums);
while (true) {
// step0: add nums into result
List<Integer> list = new ArrayList<Integer>();
for (int i : nums) {
list.add(i);
}
result.add(list);
// step2: find the first nums[k] < nums[k + 1] from the end to start
int k = -1;
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
k = i;
break;
}
}
if (k == -1) break;
// step3: find the first nums[l] > nums[k] from the end to start
int l = nums.length - 1;
while (nums[l] <= nums[k]) {
l--;
}
// step3: swap between l and k
int temp = nums[l];
nums[l] = nums[k];
nums[k] = temp;
// step4: reverse between k + 1, nums.length - 1
reverse(nums, k + 1, nums.length - 1);
}
return result;
}
private void reverse(int[] nums, int lb, int ub) {
while (lb < ub) {
int temp = nums[lb];
nums[lb] = nums[ub];
nums[ub] = temp;
lb++;
ub--;
}
}
}
~~~
### 源码分析
注意好步骤即可，其中对于数组的 reverse 操作不可在 while 循环中自增，极易出 bug! 对于 Java 来说其实可以首先将数组转化为 List, 相应的方法多一些。
### 复杂度分析
除了将 n!n!n! 个元素添加至最终结果外，首先对元素排序，时间复杂度近似为 O(nlogn)O(n \log n)O(nlogn), 反转操作近似为 O(n)O(n)O(n), 故总的时间复杂度为 O(n!)O(n!)O(n!). 除了保存结果的`result`外，其他空间可忽略不计，所以此题用生成器来实现较为高效，扩展题可见底下的 Python itertools 中的实现，从 n 个元素中选出 m 个进行全排列。
### Reference
- [Permutation Generation](#) - Robert Sedgewick 的大作，总结了诸多 Permutation 的产生方法。
- [Next lexicographical permutation algorithm](http://www.nayuki.io/page/next-lexicographical-permutation-algorithm) - 此题非递归方法更为详细的解释。
- [Permutation - Wikipedia, the free encyclopedia](https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order) - 字典序实现。
- [Programming Interview Questions 11: All Permutations of String | Arden DertatArden Dertat](http://www.ardendertat.com/2011/10/28/programming-interview-questions-11-all-permutations-of-string/)
- [algorithm - complexity of recursive string permutation function - Stack Overflow](http://stackoverflow.com/questions/5363619/complexity-of-recursive-string-permutation-function)
- [[leetcode]Permutations @ Python - 南郭子綦 - 博客园](http://www.cnblogs.com/zuoyuan/p/3758816.html)
- [[leetcode] permutations的讨论 - tuantuanls的专栏 - 博客频道 - CSDN.NET](http://blog.csdn.net/tuantuanls/article/details/8717262)
- [非递归排列算法（Permutation Generation）](http://arieshout.me/2012/04/non-recursive-permutation-generation.html)
- [闲谈permutations | HelloYou](http://helloyou2012.me/?p=133)
- [9.7. itertools — Functions creating iterators for efficient looping — Python 2.7.10 documentation](https://docs.python.org/2/library/itertools.html#itertools.permutations)
- Preface
- Part I - Basics
- Basics Data Structure
- String
- Linked List
- Binary Tree
- Huffman Compression
- Queue
- Heap
- Stack
- Set
- Map
- Graph
- Basics Sorting
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
- Bucket Sort
- Counting Sort
- Radix Sort
- Basics Algorithm
- Divide and Conquer
- Binary Search
- Math
- Greatest Common Divisor
- Prime
- Knapsack
- Probability
- Shuffle
- Basics Misc
- Bit Manipulation
- Part II - Coding
- String
- strStr
- Two Strings Are Anagrams
- Compare Strings
- Anagrams
- Longest Common Substring
- Rotate String
- Reverse Words in a String
- Valid Palindrome
- Longest Palindromic Substring
- Space Replacement
- Wildcard Matching
- Length of Last Word
- Count and Say
- Integer Array
- Remove Element
- Zero Sum Subarray
- Subarray Sum K
- Subarray Sum Closest
- Recover Rotated Sorted Array
- Product of Array Exclude Itself
- Partition Array
- First Missing Positive
- 2 Sum
- 3 Sum
- 3 Sum Closest
- Remove Duplicates from Sorted Array
- Remove Duplicates from Sorted Array II
- Merge Sorted Array
- Merge Sorted Array II
- Median
- Partition Array by Odd and Even
- Kth Largest Element
- Binary Search
- Binary Search
- Search Insert Position
- Search for a Range
- First Bad Version
- Search a 2D Matrix
- Search a 2D Matrix II
- Find Peak Element
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II
- Find Minimum in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array II
- Median of two Sorted Arrays
- Sqrt x
- Wood Cut
- Math and Bit Manipulation
- Single Number
- Single Number II
- Single Number III
- O1 Check Power of 2
- Convert Integer A to Integer B
- Factorial Trailing Zeroes
- Unique Binary Search Trees
- Update Bits
- Fast Power
- Hash Function
- Count 1 in Binary
- Fibonacci
- A plus B Problem
- Print Numbers by Recursion
- Majority Number
- Majority Number II
- Majority Number III
- Digit Counts
- Ugly Number
- Plus One
- Linked List
- Remove Duplicates from Sorted List
- Remove Duplicates from Sorted List II
- Remove Duplicates from Unsorted List
- Partition List
- Two Lists Sum
- Two Lists Sum Advanced
- Remove Nth Node From End of List
- Linked List Cycle
- Linked List Cycle II
- Reverse Linked List
- Reverse Linked List II
- Merge Two Sorted Lists
- Merge k Sorted Lists
- Reorder List
- Copy List with Random Pointer
- Sort List
- Insertion Sort List
- Check if a singly linked list is palindrome
- Delete Node in the Middle of Singly Linked List
- Rotate List
- Swap Nodes in Pairs
- Remove Linked List Elements
- Binary Tree
- Binary Tree Preorder Traversal
- Binary Tree Inorder Traversal
- Binary Tree Postorder Traversal
- Binary Tree Level Order Traversal
- Binary Tree Level Order Traversal II
- Maximum Depth of Binary Tree
- Balanced Binary Tree
- Binary Tree Maximum Path Sum
- Lowest Common Ancestor
- Invert Binary Tree
- Diameter of a Binary Tree
- Construct Binary Tree from Preorder and Inorder Traversal
- Construct Binary Tree from Inorder and Postorder Traversal
- Subtree
- Binary Tree Zigzag Level Order Traversal
- Binary Tree Serialization
- Binary Search Tree
- Insert Node in a Binary Search Tree
- Validate Binary Search Tree
- Search Range in Binary Search Tree
- Convert Sorted Array to Binary Search Tree
- Convert Sorted List to Binary Search Tree
- Binary Search Tree Iterator
- Exhaustive Search
- Subsets
- Unique Subsets
- Permutations
- Unique Permutations
- Next Permutation
- Previous Permuation
- Unique Binary Search Trees II
- Permutation Index
- Permutation Index II
- Permutation Sequence
- Palindrome Partitioning
- Combinations
- Combination Sum
- Combination Sum II
- Minimum Depth of Binary Tree
- Word Search
- Dynamic Programming
- Triangle
- Backpack
- Backpack II
- Minimum Path Sum
- Unique Paths
- Unique Paths II
- Climbing Stairs
- Jump Game
- Word Break
- Longest Increasing Subsequence
- Palindrome Partitioning II
- Longest Common Subsequence
- Edit Distance
- Jump Game II
- Best Time to Buy and Sell Stock
- Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock III
- Best Time to Buy and Sell Stock IV
- Distinct Subsequences
- Interleaving String
- Maximum Subarray
- Maximum Subarray II
- Longest Increasing Continuous subsequence
- Longest Increasing Continuous subsequence II
- Graph
- Find the Connected Component in the Undirected Graph
- Route Between Two Nodes in Graph
- Topological Sorting
- Word Ladder
- Bipartial Graph Part I
- Data Structure
- Implement Queue by Two Stacks
- Min Stack
- Sliding Window Maximum
- Longest Words
- Heapify
- Problem Misc
- Nuts and Bolts Problem
- String to Integer
- Insert Interval
- Merge Intervals
- Minimum Subarray
- Matrix Zigzag Traversal
- Valid Sudoku
- Add Binary
- Reverse Integer
- Gray Code
- Find the Missing Number
- Minimum Window Substring
- Continuous Subarray Sum
- Continuous Subarray Sum II
- Longest Consecutive Sequence
- Part III - Contest
- Google APAC
- APAC 2015 Round B
- Problem A. Password Attacker
- Microsoft
- Microsoft 2015 April
- Problem A. Magic Box
- Problem B. Professor Q's Software
- Problem C. Islands Travel
- Problem D. Recruitment
- Microsoft 2015 April 2
- Problem A. Lucky Substrings
- Problem B. Numeric Keypad
- Problem C. Spring Outing
- Microsoft 2015 September 2
- Problem A. Farthest Point
- Appendix I Interview and Resume
- Interview
- Resume