forked from abbh07/DataStructure-Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
NextPermutation.cpp
81 lines (78 loc) · 1.33 KB
/
NextPermutation.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//https://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cstring>
#include <climits>
using namespace std;
int nextPermutation(int n)
{
vector<int> v;
while(n)
{
v.push_back(n%10);
n /= 10;
}
reverse(v.begin(),v.end());
int s = v.size();
int k = s-2;
bool flag = false;
while(k >= 0)
{
if(v[k] < v[k+1])
{
flag = true;
break;
}
k--;
}
if(!flag)
{
return -1;
}
int l = s-1;
while(k < l)
{
if(v[k] < v[l])
{
break;
}
l--;
}
swap(v[k],v[l]);
vector<int>::iterator it1 = v.begin() + k + 1;
vector<int>::iterator it2 = v.end();
reverse(it1,it2);
int next = 0;
int p = 1;
for(int i=s-1;i>=0;i--)
{
next = next + v[i]*p;
p *= 10;
}
return next;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int res = nextPermutation(n);
if(res != -1)
{
cout<<res<<"\n";
}
else
{
cout<<"not possible"<<"\n";
}
}
return 0;
}