Given an array Arr[], Treat each element of the array as the digit and whole array as the number. Implement the next permutation, which rearranges numbers into the numerically next greater permutation of numbers

#1

How to solve this question without using STL

#2

See what actually next permutation do is change the order automatically. So if you will use it then half of your work will be reduced. But if you don’t want to use it. You can follow this source code


// Given a number as a char array number[], this function finds the 
// next greater number.  It modifies the same array to store the result 
void findNext(char number[], int n) 
{ 
    int i, j; 
  
    // I) Start from the right most digit and find the first digit that is 
    // smaller than the digit next to it. 
    for (i = n-1; i > 0; i--) 
        if (number[i] > number[i-1]) 
           break; 
  
    // If no such digit is found, then all digits are in descending order 
    // means there cannot be a greater number with same set of digits 
    if (i==0) 
    { 
        cout << "Next number is not possible"; 
        return; 
    } 
  
    // II) Find the smallest digit on right side of (i-1)'th digit that is 
    // greater than number[i-1] 
    int x = number[i-1], smallest = i; 
    for (j = i+1; j < n; j++) 
        if (number[j] > x && number[j] < number[smallest]) 
            smallest = j; 
  
    // III) Swap the above found smallest digit with number[i-1] 
    swap(&number[smallest], &number[i-1]); 
  
    // IV) Sort the digits after (i-1) in ascending order 
    sort(number + i, number + n); 
  
    cout << "Next number with same set of digits is " << number; 
  
    return; 
}

Have added comments for better understanding. Have any doubts left can ask here.

1 Like
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.