Thursday, October 3, 2013

47. Permutations II ----M

Q:
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

A:
**********************第五遍*********************
不用排序,就是每次增加一个数的时候, 直接在后面插入,一直插入到发现这个数为止。

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        res.push_back(vector<int>{nums[0]});
        for(int i = 1; i<nums.size(); i++){
            int val = nums[i];
            vector<vector<int>> newRes;
            for(auto line : res){ // append at tail untill we see                 
                for(int j = line.size();j>=0;j--){
                    if(j == line.size() || line[j] != val){
                        vector<int> newLine(line);
                        newLine.insert(newLine.begin()+j,val);
                        newRes.push_back(newLine);
                    }else{
                        break;
                    }
                }
            }
            res = newRes;
        }
        return res;
    }
};
 Learned:
vector<int> a = b; // where b is declared as vector<int> b{2,3,5,6};  这样的是deep copy. 所以上面的代码还可以减少copy



*********************第一遍*****************

原本的思路是,先treat them as all distinct, 再删去重复的。
但是,这样,估计会太复杂,冗余太多。

后来想,每一重循环:  先extract unique items,找到其所有permutations,
再加入。 ---可是,这样, 还是需要处理重复的情况。

 经过分析, 当我们要加入m个value的值。   我们发现,有一样是i不变的,就是要加入的位置。(前面加入后,这个值也可以很容易地 update)。 因此,我们每次固定一个要加入的位置,确定要加入的value的个数。然后recursively 计算剩下的value 的position 的permutation。

这样的思路,最大的好处是,加入的时候,不用考虑已加入的permutation是否有重复的。

代码如下:
public class Solution {
   public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        // use DP rather than recursively calling to find them
        ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
        if (num.length == 0) {
            return all;
        }
        // add the first one
        Arrays.sort(num);
        int i =0;
        while(i<num.length) {
            int newNumber = num[i];
            // count how many newNumber exist in the input
            int nNum = 1;
            while (i + 1 < num.length && num[i + 1] == newNumber) {
                nNum++;
                i++;
            }
            all = addNewNumbers2Al(all, nNum, newNumber);
            i ++;;
        }
        return all;
    }

    private ArrayList<ArrayList<Integer>> addNewNumbers2Al(
            ArrayList<ArrayList<Integer>> all, int nNum, int newNumber) {
        // if all is still empty
        if (all.size() == 0) {
            ArrayList<Integer> al = new ArrayList<Integer>();
            for (int i = 0; i < nNum; i++) {
                al.add(newNumber);
            }
            all.add(al);
            return all;
        }
        int permuLength = all.get(0).size();// the length of the existing
                                            // permutations
        // also use ArrayList to save the positions, and its how many newNumber
        // is stored at that position
        ArrayList<ArrayList<Integer>> returnedAll = new ArrayList<ArrayList<Integer>>();
        ArrayList<ArrayList<Integer>> allPos = buildPermu(0, permuLength, nNum);
        // at position i, add allPos[i] number of newNumbers
        for(int i =0;i<allPos.size();i++){
            ArrayList<Integer> alPos = allPos.get(i); // for this inserting positions permutation
            ArrayList<ArrayList<Integer>>  newAll =   copyAndInsertList(all,alPos,newNumber);
            returnedAll.addAll(newAll);
        }        
        return returnedAll;
    }

    ArrayList<ArrayList<Integer>> buildPermu(int startPos, int endPos, int nNum) {
        // input : startPosisin and end Position of the inerted value,
        // GOAL: for positions of length nPos, we can add nNum of a specific
        // values,
        // we need return how many values we need
        ArrayList<ArrayList<Integer>> allPos = new ArrayList<ArrayList<Integer>>();
        if (nNum == 0) {
            ArrayList<Integer> al = new ArrayList<Integer>();
            for (int i = startPos; i <= endPos; i++)
                al.add(0); // all add 0 at tail
            allPos.add(al);
            return allPos;
        }
        if (startPos == endPos) {
            ArrayList<Integer> al = new ArrayList<Integer>();
            al.add(nNum);
            allPos.add(al);
            return allPos;
        }
        // now number of positions > 1 and number of        
            for (int k = 0; k <= nNum; k++) { // k is the number of values that
                                                // inserted at beginning
                // first return all list before
                ArrayList<ArrayList<Integer>> allAddKatStart = buildPermu(startPos+1,
                        endPos, nNum - k);
                // insert at the begining of the list
                for (int t = 0; t < allAddKatStart.size(); t++) {
                    allAddKatStart.get(t).add(0, k);// insert at beginning
                }
                // NOW,allAddKatStart contains   all the permuations with the first permuation is k at startPosition
                allPos.addAll(allAddKatStart);
            }
        return allPos;
    }

    private ArrayList<ArrayList<Integer>> copyAndInsertList(
            ArrayList<ArrayList<Integer>> all, ArrayList<Integer> alPos,int targetValue) {
        // create a new copy of all, and then add newNumber at position k
        ArrayList<ArrayList<Integer>> newAll = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < all.size(); i++) { // for each list, copy and
                                                // insert newNumber
            ArrayList<Integer> alOld = all.get(i);

            ArrayList<Integer> alNew = new ArrayList<Integer>();
            for (int j = 0; j < alOld.size(); j++) {
                alNew.add(alOld.get(j));
            }
            newAll.add(alNew);
        }
        // now we have the copied all,  named as newAll
        for(int i =0;i<newAll.size();i++){
            ArrayList<Integer> tmpAl = newAll.get(i );  // for each old permutation
            // now we have the new list, we need insert the targetValue at positions specified by alPos
            for(int insertPos =alPos.size()-1;insertPos>=0;insertPos-- ){ // we are working on position j
                // add  alPos[j] time of targetValue
                for(int k = 0;k<alPos.get(insertPos);k++) 
                    tmpAl.add(insertPos , targetValue);
            }            
        }
        return newAll;
    }
}



Mistakes:
哎,太多了。一开始是思路不对。
后来,后来,从周四下午,在家里电脑上想了想,找到路子了。黑色星期五的下午,才突然想起来,可以把position也做permutation。
然后,晚上,来了,干了快2个小时,才弄完。

语法错误啊什么的,倒是不多。 没怎么用debug。  思路啊,思路。

-------------------第二遍 --------------很简单嘛,用 recursively calling ---------------------------
思想是: 对每一个不同的值,插入到 (删去它之后的permute的list)的第一个位置。
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        return helper(nums,0);
    }
private:
    vector<vector<int>> helper(vector<int> & nums, int start){
        int n = nums.size();
        vector<vector<int>> res;
        if(start >=n)
            return res;
        if(start == n-1){
            res.push_back(vector<int>{nums[start]});
        }else{
            for(auto & line : helper(nums,start+1)){
                for(int i =line.size(); i>=0;i--){
                    auto newLine = line;
                    newLine.push_back(nums[start]);
                    if(i != line.size() && newLine[i] == newLine.back() ){
                        break;
                    }else{
                        newLine[line.size()] = newLine[i];//swap potion i and the last 
                        newLine[i] = nums[start];
                        res.push_back(newLine);
                    }
                }
            }
        }
        return res;
    }
};

       -------------------------   3 rd pass-----------------------------
每次删掉最前面所有的相同的值,假设是k 个value ==3的值。  那么我们把剩下的permute好之后,再把这k个3 插入到结果里去。

public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        Arrays.sort(num);
        return permute(num, 0);
    }
    private ArrayList<ArrayList<Integer>> permute(int[] num,int start){
        // find how many values at start
        ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
        if(start >= num.length)
            return all;
        
        int count = 0;
        int val = num[start];
        while( start<num.length && num[start] == val ){
            start++;
            count++;
        }
        // get result without this value (and count)
        ArrayList<ArrayList<Integer>> oneLess = permute(num, start);
        // input # of val into the oneLess list
        all.addAll(insert2permute( oneLess, val,count ,0));
        return all;
    }
    private ArrayList<ArrayList<Integer>> insert2permute( ArrayList<ArrayList<Integer>> all, int val, int count,int startIndex ){
        // insert the total amount (count) of values (val ) into the arrayList (all)
        if(count<=0){
            return all;
        }
        if(all.size() ==0){
            ArrayList<Integer> al = new ArrayList<Integer>();
            for(int i =0;i<count;i++)
                al.add(val);
            all.add(al);
            return all;
        }
        // now all is not empty, and count >= 1
        // begining insert position
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        for(int i=startIndex;i<=all.get(0).size();i++){
            // add val at each startIndex position
            ArrayList<ArrayList<Integer>> newAll = copyList(all);
            for(ArrayList<Integer> al : newAll){
                al.add(i,val);
            }
            result.addAll(insert2permute( newAll, val, count-1, i+1));
        }
        return result;        
        
    }
    private ArrayList<ArrayList<Integer>> copyList(ArrayList<ArrayList<Integer>> all){
        ArrayList<ArrayList<Integer>> newAll = new ArrayList<ArrayList<Integer>>();
        if(all.size()==0)
            return newAll;
        
        for(ArrayList<Integer> al:all){
            ArrayList<Integer> newAl = new ArrayList<Integer>();
            for(int val : al){
                newAl.add(val);
            }
            newAll.add(newAl);
        }
        return newAll;
    }
}




Learned:








No comments:

Post a Comment