next_permutation.cpp

vector<vector<int> > Solution::permute(vector<int> &A) {
    vector<vector<int> > listOfPermutations;
    vector<int> B;
    // get the first permutation
    sort(A.begin(), A.end());
    
    // add the first permutation in the list
    listOfPermutations.push_back(A);
    
    int n = A.size();
   
    int maximumElement = *(A.rbegin());
    
    
    while(1) {
        B.clear();
        // find the longest decreasing consecutive elements at the end of the array
        int beginDecreasing = n-1;
        while (beginDecreasing>0 && A[beginDecreasing-1]>=A[beginDecreasing]) {
            beginDecreasing--;
        }
      
        if (beginDecreasing == 0) break;
        
        int theSmallestButLargerPosition = -1;
        int theSmallestButLarger = maximumElement;
        
        for (int i=beginDecreasing; i<n; i++) {
            if (A[i]<=theSmallestButLarger && A[i]>A[beginDecreasing-1]) {
                theSmallestButLargerPosition = i;
                theSmallestButLarger = A[i];
            }
        }
        
        if (theSmallestButLargerPosition == -1) break;
        
        // swap the smallest but larger than A[beginDecreasing-1] with A[beginDecreasing-1]
        iter_swap(A.begin()+(beginDecreasing-1), A.begin()+theSmallestButLargerPosition);
        
        // sort the last decreasing array we found
        for (int i=beginDecreasing; i<n; i++) {
            B.push_back(A.back());
            A.pop_back();
        }
        
        for (vector<int>::iterator it = B.begin(); it!=B.end(); it++) {
            A.push_back(*it);
        }
        
        // add to list of permutation
        listOfPermutations.push_back(A);
    }
    
    return listOfPermutations;
}