Trick to find next permutation of a number
Ashish Kumar Gupta
43

Logic for generating the next permutation
for the next permutation following is the key rule :
1 -> start from end and check is any ar[i] < ar[i+1] for i fom size-1 to i>=0
<> if so then take that val = ar[i] and now again check from end if there is any
val < ar[j] where j starts from size -1 to 0
<> if so then swap(ar[ i ] ,ar[ j ]) and sort rest of array from i+1 to size
return .

2 -> if no such thing then next permutation will again be the initial one
so sort the whole array and return**
Below is the code for it

class Solution {
public:
    void nextPermutation(vector<int>& ar) {
        int size = ar.size();
        int flag=1;
        for(int i=size-1;i>0;i--){
            if(ar[i-1] >= ar[i]){
                continue;
            }else{
                int val  = ar[i-1];
                for(int j=size-1;j>0;j--){
                    if(val < ar[j]){
                        //cout<<ar[i-1]<< " "<<ar[j]<<endl;
                        swap(ar[i-1],ar[j]);
                        flag=0;
                        break;
                    }
                }
                if(flag==0){
                    sort(ar.begin()+i,ar.end());
                    return;
                }
            }
            
        }
        if(flag==1){
            sort(ar.begin(),ar.end());
        }
        
    }
};
Comments (0)