-
Notifications
You must be signed in to change notification settings - Fork 36
/
next_Permutation.cpp
61 lines (56 loc) · 969 Bytes
/
next_Permutation.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
#include <iostream>
using namespace std;
void swap(char* a, char* b)
{
if (*a == *b)
return;
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
void rev(string& s, int l, int r)
{
while (l < r)
swap(&s[l++], &s[r--]);
}
int bsearch(string& s, int l, int r, int key)
{
int index = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (s[mid] <= key)
r = mid - 1;
else {
l = mid + 1;
if (index == -1 || s[index] >= s[mid])
index = mid;
}
}
return index;
}
bool nextpermutation(string& s)
{
int len = s.length(), i = len - 2;
while (i >= 0 && s[i] >= s[i + 1])
--i;
if (i < 0)
return false;
else {
int index = bsearch(s, i + 1, len - 1, s[i]);
swap(&s[i], &s[index]);
rev(s, i + 1, len - 1);
return true;
}
}
// Driver code
int main()
{
string s = { "gfg" };
bool val = nextpermutation(s);
if (val == false)
cout << "No Word Possible" << endl;
else
cout << s << endl;
return 0;
}
//this code is contributed by Nishant Choudhary