LeetCode – Permutations (Java)
Given a collection of numbers, return all possible permutations.
http://gongxuns.blogspot.com/2012/12/leetcode-permutations.html
X. We can also recursively solve this problem. Swap each element with each element after it.
A more systematic for solving permutation problems
http://blog.csdn.net/tuantuanls/article/details/8717262
X.
http://www.cnblogs.com/springfor/p/3888044.html
Related: LeetCode - Permutations II
Read full article from LeetCode – Permutations (Java)
Given a collection of numbers, return all possible permutations.
We can get all permutations by the following steps:
[1]
[2, 1]
[1, 2]
[3, 2, 1]
[2, 3, 1]
[2, 1, 3]
[3, 1, 2]
[1, 3, 2]
[1, 2, 3]
Loop through the array, in each iteration, a new number is added to different locations of results of previous iteration. Start from an empty List.http://gongxuns.blogspot.com/2012/12/leetcode-permutations.html
public ArrayList<ArrayList<Integer>> permute(int[] num) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); //start from an empty list result.add(new ArrayList<Integer>()); for (int i = 0; i < num.length; i++) { //list of list in current iteration of the array num ArrayList<ArrayList<Integer>> current = new ArrayList<ArrayList<Integer>>(); for (ArrayList<Integer> l : result) { // # of locations to insert is largest index + 1 for (int j = 0; j < l.size()+1; j++) { // + add num[i] to different locations l.add(j, num[i]); ArrayList<Integer> temp = new ArrayList<Integer>(l); current.add(temp); //System.out.println(temp); // - remove num[i] add l.remove(j); } } result = new ArrayList<ArrayList<Integer>>(current); } return result; } |
A more systematic for solving permutation problems
http://blog.csdn.net/tuantuanls/article/details/8717262
建立一棵树，比如说
对于第k层节点来说，就是交换固定了前面 k-1 位，然后分别 swap(k,k), swap(k, k+1) , swap(k, k+2) ...
例如上图中的第三层，固定了第一位（即2），然后分别交换第1，1位，1，2位，1，3位
public ArrayList<ArrayList<Integer>> permute(int[] num)
{
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
permute(num, 0, result);
return result;
}
void permute(int[] num, int start, ArrayList<ArrayList<Integer>> result)
{
if (start >= num.length) //终止条件，递归到末尾节点是，将数组转化为链表
{
ArrayList<Integer> item = convertArrayToList(num);
result.add(item);
}
for (int j = start; j <= num.length - 1; j++)
{
swap(num, start, j);//交换
permute(num, start + 1, result);//交换后子代递归
swap(num, start, j);//恢复到交换前的初始状态，以便于得出下一次的交换结果
}
}
对于排列可以通过交换元素得到。例如，输入为[1,2,3]可以由以下思路得到：
- [1,2,3]本身为一个排列
- 交换后两个元素得到新排列：[1,3,2]
- 对于原组合交换第一个和第三个元素得到[3,2,1]
- 对上一个组合交换后两个元素[3,1,2]
- 对原组合交换第一个和第二个元素[2,1,3]
- 交换后两个元素得到[2,3,1]
也就是说可以通过从后往前交换元素得到新的排列，但是在对交换后的排列进行交换的时候会打乱原来的顺序，因此可能得到重复的排列方式。所以可以再交换后恢复到原始组合，再对原始组合进行交换，避免重复的发生。从下面这张图上可以参考排列的思路：
void Perm(vector<int>& num, int i, vector<vector<int> > &r)
{
if (i == num.size())
{
r.push_back(num);
}
for (int k = i; k != num.size(); ++k)
{
swap(num[k], num[i]);
Perm(num, i + 1, r);
swap(num[k], num[i]);
}
}
vector<vector<int> > permute(vector<int> &num) {
if (!num.size())
{
vector<vector<int> > r;
return r;
}
vector<vector<int> > r;
Perm(num, 0, r);
return r;
}
public ArrayList<ArrayList<Integer>> permute(int[] num) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); permute(num, 0, result); return result; } void permute(int[] num, int start, ArrayList<ArrayList<Integer>> result) { if (start >= num.length) { ArrayList<Integer> item = convertArrayToList(num); result.add(item); } for (int j = start; j <= num.length - 1; j++) { swap(num, start, j); permute(num, start + 1, result); swap(num, start, j); } } private ArrayList<Integer> convertArrayToList(int[] num) { ArrayList<Integer> item = new ArrayList<Integer>(); for (int h = 0; h < num.length; h++) { item.add(num[h]); } return item; } private void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } |
X.
http://www.cnblogs.com/springfor/p/3888044.html
这道题就用循环递归解决子问题。
因为求所有组合，这就意味着不能重复使用元素，要用visited数组。
有因为是所有可能的组合，所以循环length次，就是这里面每位都有可能有length个可能性。
正因为如此，每一层递归就不需要传递一个start点，告诉他从哪开始（因为都是从头开始循环）。
Therefore, we need a for loop to process all the possibilities in each element of the array. For example, array[0] can be 1, 2, 3, 4. While in the case of array[0] = 1, array[1] can be 2, 3, 4. Recursively doing this we can get all the possible permutations.
1. Create a new array "visited[num.size()]" to keep the which element of the original array has been visited, so as to ensure only the remaining elements will be processed. For example, in case of array[0] = 1, only 2,3,4 can be process for array[1].
2. Remove the last element from the array, and resume the visit flag in order to process next possible permutation. For example, after having [1, 2, 3, 4], remove 4 from array (array will be fallen back to [1, 2, 3]), and reset visit flag of the 3rd element to un-visited. Then go into the next iteration: put 4 into the array. New array this time would be [1, 2, 4].
- public ArrayList<ArrayList<Integer>> permute(int[] num) {
- ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
- ArrayList<Integer> element = new ArrayList<Integer>();
- boolean[] visited = new boolean[num.length];
- helper(num, result, element, visited);
- return result;
- }
- public void helper(int[] num, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> element, boolean[] visited){
- if (element.size() == num.length){
- // duplicate element and add it to result (element would be changed from time to time. If directly use element
- // only result would be changed when element changed)
- result.add(new ArrayList<Integer>(element));
- return;
- }
- for(int i=0; i<num.length; i++){
- if(!visited[i]){
- visited[i] = true;
- element.add(num[i]);
- helper(num, result, element, visited);
- // After providing a complete permutation, pull out the last number,
- element.remove(element.size()-1);
- visited[i] = false;
- }
- }
- }
若输入数组为[3,2,1,4]
- 对给定的数组进行排序，这里排序后即[1,2,3,4]；
- 从后往前找第一个顺序对，所谓顺序对即第一个数小于第二个数，如(3,4)；
- 顺序对中较小的数字对应的位置即为交换点，如上面例子中3的位置。交换交换点上的数字与从后往前第一个比交换点上数值大的数字。因为交换点数字位于一个顺序对中，因此肯定是可以找到这样的数字的（上面例子中为4）；
- 将交换后的交换数字后面的所有数字顺序颠倒。（上面例子中交换后3为最后一个数字，因此不需要交换）
- 重复上面的步骤，直到数组中不存在顺序对为止（此时的数组变为[4,3,2,1]）
该算法不仅对非重复数组有用，对重复的是一样的，因为两个元素相等是为非顺序对，所以不会交换，也就不会出现重复的情况了。
http://tech-wonderland.net/blog/leetcode-permutations-i-and-ii.htmlRelated: LeetCode - Permutations II
Read full article from LeetCode – Permutations (Java)
