[leetcode] Permutations | 一个array的所有permutation

Posted by: lexigrey on: August 7, 2013

• In: leetcode
• Leave a Comment

这个思路本来很简单，如果用recursion来enumeration的话，即用set，每次第i个位置用了set的第j个元素，然后set remove j, recurse on i + 1。非常straight forward的做法，但是用java这么做有好几个问题：

• 如果input有重复，如aabc，set没法处理同时存在2个a的情况。
• 在recurse on set的每个元素的时候，因为for循环是interate thru set itself，但里面还有set.add(), set.remove这些改变set本身的语句，所以会有modify iterator exception。还得弄个copy先。
• 代码巨长。越写越没信心。

所以还是CC150上的另一种思路：每次取一个元素，对于之前（上一层循环的list结果）的每个permutation, 在能插的地方就插这个新元素，然后生成新的permutation，放入这一层的结果。这样代码相对简单，而且不用recursion。有几个要点：

1. 最开始要传一个空的permutation进去，否则没处可insert第一个元素。
2. 这种做法不能防止duplication（1212可能有好几种insert成它的方法）。

public ArrayList<ArrayList<Integer>> permute(int[] num) {
  ArrayList<ArrayList<Integer>> lastLayer = new ArrayList<ArrayList<Integer>>();
  lastLayer.add(new ArrayList<Integer>());
  for (int i = 0; i < num.length; i++) {
    ArrayList<ArrayList<Integer>> newLayer = new ArrayList<ArrayList<Integer>>();
    for (int j = 0; j < lastLayer.size(); j++) {
      ArrayList<Integer> curr = lastLayer.get(j);
      insertEverywhere(curr, num[i], newLayer);
    }
    lastLayer = newLayer;
  }
  return lastLayer;
}
private void insertEverywhere(ArrayList<Integer> curr, int num, ArrayList<ArrayList<Integer>> newLayer) {
  for (int i = 0; i <= curr.size(); i++) {
    ArrayList<Integer> newList = new ArrayList<Integer>(curr);
    newList.add(i, num);
    newLayer.add(newList);
   }
}

Tags: subsets/permutation, 固定解法