If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
Examples:
Input -> output
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
Problem explanation:
Given a number, find the next highest number, using the same digits given in the array.
For example:
1234 -> 1243
Here 1235 is invalid, because digit “5” is not in the input array. Hence the next highest number will be “1243”.
Another example:
4132 -> 4213
One more, ok last one:
4321 -> none.
Because the number is already sorted in descending order, cannot find next higher element.
This problem can be solved in 3 ways.
1. Brute force approach
2. Direct Solution
3. Using inbuilt function. [Not really a solution, good to know]
We shall look into all the 3 solution below.
1. Brute force approach.
The solution is simple.
We increment the number by one, and check if all the number are present in the given array.
If all the numbers are accounted for we take that number, else we search again.
Obviously this will take lot of time. First you can give this solution, if interviewer is not satisfied, go to the 2nd solution.
2. Direct Solution
In this approach we take 2 pointers.
Step 1: In the given array, from the right side, find a number that is not in ascending order. Mark that number as num_1.
Step 2: Then we find another digit from the right of num_1, such that it is the smallest number but greater than num_1, and mark it as num_2.
Step 3: Swap num_1, num_2.
Step 4: Sort the numbers from the right of original position of num_1.
We shall analyze the above steps with the help of an example:
Given array:
3 2 8 4 1
From step 1, searching from right, “2” is breaking the ascending order of “1 4 8”. Mark it as num_1.
From step 2: “4” is the smallest number greater than num_1. Mark it as num_2.
From step 3: Swap num_1 and num_2
From step 4: Sort the array in ascending order from the original position of num_1.
We shall get our desired result.
Solution 3: Use library function:
Use “next_permutation()” function found in STL in C++.
Solution in C++
/*
* File : Next_Permutation.cpp
* Author : prodevelopertutorial.com
* Purpose : To find next premutaion of a number using 2 solutions
* Copyright: @ prodevelopertutorial.com
*/
#include<iostream>
#include<vector>
using namespace std;
void next_permutation_using_direct_approach(vector<int>& nums)
{
int len = nums.size();
int num_1_index;
int num_2_index;
//step 1: find the index of num 1 so that it is not in ascending order
for (num_1_index = len - 2; num_1_index >= 0; num_1_index--)
{
if (nums[num_1_index] < nums[num_1_index + 1])
{
break;
}
}
//if we did not find, we just reverse the numbers.
// example: if the number is 123, then 321 will be the next heighest permutation
if (num_1_index < 0)
{
reverse(nums.begin(), nums.end());
}
else
{
//step 2, we find second number index, such that it is greater than num 1
for (num_2_index = len - 1; num_2_index > num_1_index; num_2_index--)
{
//if we find, break the loop
if (nums[num_2_index] > nums[num_1_index])
{
break;
}
}
// step 3: swap the numbers
swap(nums[num_1_index], nums[num_2_index]);
//step 4: reverse the numbers
reverse(nums.begin() + num_1_index + 1, nums.end());
}
}
void nextPermutation_using_library_function(vector<int>& nums)
{
next_permutation(begin(nums), end(nums));
}
int main()
{
vector<int> number;
number.push_back(3);
number.push_back(2);
number.push_back(8);
number.push_back(4);
number.push_back(1);
for (int i = 0; i < number.size(); i++)
{
cout <<number[i] << " ";
}
cout<<endl;
//nextPermutation_using_library_function (number);
next_permutation_using_direct_approach (number);
for (int i = 0; i < number.size(); i++)
{
cout <<number[i] << " ";
}
cout<<endl;
}