7.23 permutation & nextpermu

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();
            }
        }
        
    }    
};