Permutations [source code]
public class Permutations {
static
/******************************************************************************/
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res_lsls = new ArrayList<>();
if (nums.length == 0)
return res_lsls;
int[] nums_copy = Arrays.copyOf (nums, nums.length);
helper (nums_copy, 0, res_lsls);
return res_lsls;
}
void helper (int[] nums, int pos, List<List<Integer>> lsls) {
if (pos == nums.length) {
List<Integer> res_ls = new ArrayList<>();
for (int j : nums)
res_ls.add (j);
lsls.add(res_ls);
return;
}
for (int i = pos; i < nums.length; i++) {
swap (nums, pos, i);
helper (nums, pos + 1, lsls);
swap (nums, pos, i);
}
}
void swap (int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
/******************************************************************************/
public static void main(String[] args) {
Permutations.Solution tester = new Permutations.Solution();
int[][] inputs = {
{1,2,3},
};
for (int i = 0; i < inputs.length; i++) {
int[] nums = inputs[i];
List<List<Integer>> res = tester.permute(nums);
System.out.println(Printer.separator());
String input_str = Printer.array (nums);
System.out.println (Printer.wrapColor (input_str, "magenta") + " -> \n" +
res
);
}
}
}
nextInt(i)返回的其实是一个[0,i)的值, 有时候比较难理解这个值到底怎么计算, 关键概念就是你要理解这个算出来的是一个offset的概念, 这个就是这个函数设计的初衷. 这样一个1-based的offset, 你怎么融入到你0-based的index的计算里面去, 就是你自己需要稍微调整一下就行了;
当然, 如果是实在是脑子宕机, 那么最简单的方法, 就是问一下自己, 你想要的这个随机范围, minimum inclusive是多少, 然后maximum inclusive是多少, 然后maximum exclusive是多少, 就行了; 这样最后算起来也不复杂;
比如你假如有一个长度是10的, 你现在在3, 那么你就想要在[4,9]的范围内进行一个选择一个index; 但是要记住, 你最后random出来的始终是一个offset, 所以最好切换到这个思考方式上面去: 更进一步, 这个offset的初始值就是0, 但是你站在3的位置上, 最小可接受的offset就是1, 这个就不一致; 所以最好, 你就站在4这个位置计算一个可接受的offset, 这个就很简单了, [0, 10 - 4)就行了, 这个就是在4的位置上可接受的offset, 那么在3位置上可接受的offset, 就是[0, 10 - 4) + 1就行了; 最后这个offset加到3上面, 就是你想要的index;
当然我后来意识到了, 这个根本不是这个题目的要求, 这个题目要求的是permutation所有的, 而不是随机值; 不过这个思考过程还是有意思的; 保存在这里:
int i = pos;
if (pos + 1 < nums.length) {
int ofs = (new Random ()).nextInt(nums.length - (pos + 1)) + 1;
i = pos + ofs;
} else {
i = pos;
}
有些Corner Case还是要考虑, 比如你认为offset应该在4的基础上计算, 但是假如你现在是在9怎么办? 所以这个+1操作要事先分情况处理一下, 考虑一下是否合法;
感觉还是手生了, 其实是很熟悉的一个题目, 但是实际上做的时候还是有很多东西没有处理好; 比如store和swap这两个操作, 是什么顺序?
➜ src git:(master) ✗ java Permutations
nums: (1 2 3 ), pos: (0), lsls: ([])
nums: (2 1 3 ), pos: (1), lsls: ([[2, 1, 3]])
nums: (2 3 1 ), pos: (2), lsls: ([[2, 1, 3], [2, 3, 1]])
nums: (3 2 1 ), pos: (1), lsls: ([[2, 1, 3], [2, 3, 1], [3, 2, 1]])
nums: (3 1 2 ), pos: (2), lsls: ([[2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]])
========================
1 2 3 ->
[[2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
➜ src git:(master) ✗ java Permutations
nums: (1 2 3 ), pos: (0), lsls: ([])
nums: (2 1 3 ), pos: (1), lsls: ([[1, 2, 3]])
nums: (2 3 1 ), pos: (2), lsls: ([[1, 2, 3], [2, 1, 3]])
nums: (3 2 1 ), pos: (1), lsls: ([[1, 2, 3], [2, 1, 3], [1, 2, 3]])
nums: (3 1 2 ), pos: (2), lsls: ([[1, 2, 3], [2, 1, 3], [1, 2, 3], [3, 2, 1]])
========================
1 2 3 ->
[[1, 2, 3], [2, 1, 3], [1, 2, 3], [3, 2, 1]]
上面那个就是我一开始在每一个iteration, 先swap, 然后再store, 这种逻辑就比较有问题, 最好的逻辑, 还是应该是store then change, 每当你进入一个call, 你都应该考虑一下你当前这个state是否已经保存(其实就是这个问题环境下的处理); 当然, 另外一种思路, 就是你在每一个parent位置完成对child的处理, 这样当进入child的call的时候, 就可以change then store/process了, 但是感觉这种逻辑好像比较容易写的比较复杂;
当然上面这个trace对应的算法本身还是有bug的:
void helper (int[] nums, int pos, List<List<Integer>> lsls) {
if (pos == nums.length)
return;
List<Integer> res_ls = new ArrayList<>();
for (int j : nums)
res_ls.add (j);
lsls.add(res_ls);
for (int i = pos + 1; i < nums.length; i++) {
swap (nums, pos, i);
helper (nums, pos + 1, lsls);
swap (nums, pos, i);
}
}
最后大概还是写出来了; 速度是7ms (42%), 可以接受, 不过花的时间还是有点多了;
另外, 上面那个bug其实还是自己没有想好; 上面那个bug看起来很合理, 每一个state上来过来了就store, 然后后面change; 但是这里有一个问题, 这个简单的逻辑并不是适合所有的问题. 首先, 上面的代码的第一个bug是, i的起点必须包括pos自己, 这个好像其实是我以前讨论过的一个subtlety了; 但是修改了完了之后, 得到的算法有一个问题, 就是有大量的duplicate; 我以前在其他的问题里面的时候其实也用过这个算法, 当时没有感觉有问题很大原因是因为那些算法需要完成的只是简单的遍历就行了, 但是这里最后你要返回这个结果, 所以一定要去重. 而避免duplicate的一个很重要的思路, 就是要注意add的时机. 就是因为随便的store, 也就是这里的process, 才导致最后很多重复, 这个好像之前NLP作业的时候也碰到过类似的情况. 所以这里需要思考的问题, 到底什么时候才是最合理的add的时间; 最后想出来, 应该是在leaf的位置才进行add; 然后基本就没有问题了;
虽然最后submission里面成绩不算太好, 不过前排的几个答案基本都是这个一样的写法, 不谋而合, 这个题目的难点就是这么几个看起来不起眼的小细节;
submission的另外一个做法:
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList();
if (nums == null || nums.length == 0)
return res;
helper(res, new ArrayList(), nums, new boolean[nums.length]);
return res;
}
private void helper(List<List<Integer>> res, List<Integer> list, int[] nums, boolean[] used) {
if (list.size() == nums.length) {
res.add(new ArrayList(list));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
list.add(nums[i]);
helper(res, list, nums, used);
used[i] = false;
list.remove(list.size() - 1);
}
}
}
这个思路其实还是类似的, 就是保存了一个bitmap用来辅助backtracking而已, 然后有一个path list来作为accum; 这个还是一个更加general的做法;
discussion里面有一个帖子对这种比较大众化的backtracking问题进行了一个总结: https://discuss.leetcode.com/topic/46162/a-general-approach-to-backtracking-questions-in-java-subsets-permutations-combination-sum-palindrome-partioning/65
我没有专门看了, 感觉对于这个技术本身我是没有障碍的, 主要还是对于具体问题的分析, 没有必要专门把答案看一遍, 这个人并没有给出什么很witty的干货总结;
不过总体感觉, 其实还是上面那种bitmap + accum的思路, 才是backtracking问题最常见的思路;
这个是一个考古帖子, 2014年的, 估计就是刚开始开发的一帮人的做法:
public List<List<Integer>> permute(int[] num) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if (num.length ==0) return ans;
List<Integer> l0 = new ArrayList<Integer>();
l0.add(num[0]);
ans.add(l0);
for (int i = 1; i< num.length; ++i){
List<List<Integer>> new_ans = new ArrayList<List<Integer>>();
for (int j = 0; j<=i; ++j){
for (List<Integer> l : ans){
List<Integer> new_l = new ArrayList<Integer>(l);
new_l.add(j,num[i]);
new_ans.add(new_l);
}
}
ans = new_ans;
}
return ans;
}
这个做法总体思路好像是一致的, 大概就是pick number incrementally ltr for each position. 不过他选择了用iteration的方法来做, 看起来不是特别的方便, 尤其是里面还有add at position这种操作, 是非常inefficient的;
不过总体思路应该还是类似的; 这里这个算法的整体实现思路就非常类似我之前NLP写EM算法的思路, empty NEXT in the beginning each iteration, and update the CUR to be NEXT at the end of each iteration.
事实上, 这个算法的思路其实不一样:
@cbmbbz said in My AC simple iterative java/python solution:
the basic idea is, to permute n numbers, we can add the nth number into the resulting
List<List<Integer>>from the n-1 numbers, in every possible position.For example, if the input num[] is {1,2,3}: First, add 1 into the initial
List<List<Integer>>(let's call it "answer").Then, 2 can be added in front or after 1. So we have to copy the List
in answer (it's just {1}), add 2 in position 0 of {1}, then copy the original {1} again, and add 2 in position 1. Now we have an answer of { {2,1},{1,2} }. There are 2 lists in the current answer. Then we have to add 3. first copy {2,1} and {1,2}, add 3 in position 0; then copy {2,1} and {1,2}, and add 3 into position 1, then do the same thing for position 3. Finally we have 2*3=6 lists in answer, which is what we want.
这个想法其实还是很有意思的, 有一点DP或者说recursion的感觉在里面, 用非常recursion(-1)的思路来思考, 但是实际上这个思路是完全正确的;
注意他这里代码的写法, i控制的其实是长度, 也就是input size, 用来控制recursion的; 而j控制的更像是insert position: 因为i是从小到大的增长, 所以对于每一个i, 你可以说, 有i + 1个插入位置;
事实上, 这个代码虽然没有我自己学习的这个代码这么slick, 但是却是非常接地气. 本质上的思路其实也是类似的; 按理说这样一个算法应该是可以被自己想到的;
同样的算法, 换成recursion来写:
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums.length == 0) return result;
backtrack(result, nums, new ArrayList<Integer>(), 0);
return result;
}
private void backtrack(List<List<Integer>> result, int[] nums, List<Integer> currentList, int index) {
if (currentList.size() == nums.length) {
result.add(currentList);
return;
}
int n = nums[index];
for (int i = 0; i <= currentList.size(); i++) {
List<Integer> copy = new ArrayList<Integer>(currentList);
copy.add(i, n);
backtrack(result, nums, copy, index + 1);
}
}
这个是另外一个人的一个优化, 好像是不需要重复的创建新的lsls:
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
if(nums.length == 0) return result;
List<Integer> cur = new LinkedList<Integer>();
cur.add(nums[0]);
result.add(cur);
for(int i = 1; i < nums.length; i++) {
int curSize = result.size();
for(int j = 0; j < curSize; j++) {
for(int x = 0; x < result.get(j).size(); x++) {
List<Integer> newList = new LinkedList<Integer>(result.get(j));
newList.add(x, nums[i]);
result.add(newList);
}
result.get(j).add(nums[i]);
}
}
return result;
}
}
这个好像是2014年第一个提出recursive做法的人, 当然他好像其实也是看来的而已:
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > result;
permuteRecursive(num, 0, result);
return result;
}
// permute num[begin..end]
// invariant: num[0..begin-1] have been fixed/permuted
void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result) {
if (begin >= num.size()) {
// one permutation instance
result.push_back(num);
return;
}
for (int i = begin; i < num.size(); i++) {
swap(num[begin], num[i]);
permuteRecursive(num, begin + 1, result);
// reset
swap(num[begin], num[i]);
}
}
};
总体思路是类似的, add on leaf, swap-recurse-swap这些操作, 都是完全类似的;
Problem Description
Given a collection of distinct 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],
[3,2,1]
]
Difficulty:Medium
Total Accepted:180.3K
Total Submissions:409.8K
Contributor: LeetCode
Companies
linkedin microsoft
Related Topics
backtracking
Similar Questions
Next Permutation Permutations II Permutation Sequence Combinations