美文网首页
7.23 permutation & nextpermu

7.23 permutation & nextpermu

作者: 陈十十 | 来源:发表于2016-07-24 22:03 被阅读32次

    to do

    8.3.2 Next Permutation

    reference to sth can not "repoint" like pointer does
    实在写太久了哭。。mark

        void nextPermutation(vector<int>& nums) {
            int pivoti = -1;
            // from R->L, find first occurence of out of order.(descending) if 1220, 1
            for (int i=nums.size()-1; i>0; --i) {
                if (nums[i-1] < nums[i]) {
                    pivoti=i-1;
                    break;
                }
            }
            if (pivoti==-1) {
                reverse(nums.begin(), nums.end());
                return;
            }
            
            // from R->L. find first occurence of greater than [pivoti]
            for (int j=nums.size()-1; j>=0; --j) {
                if (nums[j] > nums[pivoti]) {
                    swap(nums[j], nums[pivoti]);
                    // int tmp = nums[pivoti];
                    // nums[pivoti] = nums[j];
                    // nums[j] = tmp;
                    reverse(nums.begin()+pivoti+1, nums.end());
                    return;
                }
            }
        }
    

    std::for_each

    template <class InputIterator, class Function> 
    Function for_each (InputIterator first, InputIterator last, Function fn);
    **Apply function to range**
    template <class InputIterator,class Function> 
    Function for_each(InputIterator first, InputIterator last, Function fn) { 
      while (first!=last) { fn (*first); ++first; }
      return fn;// or, since C++11: return move(fn);
    }
    

    8.4.3] permutation II rec, 也可以用next permutation

    或者看了答案的..感觉自己想的话,这个方法并不trivial。希望下次做的时候再明白透彻些。

    有compiler问题,error required from here,ubuntu下次跑!
    lambda func: [&reference_to_captured_var](params) {};

    class Solution {
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            n = nums.size();
            // record occurences of each elem in map
            unordered_map<int, int> map;
            for (auto i: nums) ++map[i];
            // convert map to vector of pair for tmp recording
            vector<pair<int, int>> record;
            // fn appy to each unordered_map<Key,T> entry, WHICH IS PAIR<INT, INT>
            for_each(map.begin(), map.end(), [&record](pair<int, int>& entry){ 
                record.push_back(entry);
            });        
            
            vector<int> path;
            vector<vector<int>> ret;
            permuteR(record.begin(), record.end(), path, ret);
            return ret;
        }
    
    private: 
        size_t n;
        void permuteR(vector<pair<int, int>>::iterator begin, vector<pair<int, int>>::iterator end, vector<int>& path, vector<vector<int>>& ret) {
            if (path.size()==n) {
                ret.push_back(path);
                return;
            }
            // iterate through nums, if hasn't used up all occurrences of some elem, add and backtrack
            for (auto it=begin; it<end; ++it) {
                // count occurrence of *it .first in path
                int ct = 0;
                for (auto p=path.begin(); p<path.end(); ++p) {
                    if (*p==(*it).first) ++ct;
                }
                // if still (*it).first left to use, append
                if ((*it).second > ct) {
                    path.push_back((*it).first);
                    permuteR(begin, end, path, ret);
                    path.pop_back();
                }
            }
            
        }    
    };
    

    相关文章

      网友评论

          本文标题:7.23 permutation & nextpermu

          本文链接:https://www.haomeiwen.com/subject/pclgjttx.html