next permutation Algorithm
The survey of permutations of finite sets is an important subject in the fields of combinatorics and group theory. In elementary combinatorics, the K-permutations, or partial permutations, are the ordered agreements of K distinct components choose from a set. Stedman widens the consideration of permutations; he goes on to consider the number of permutations of the letters of the alphabet and of horses from a stable of 20.A first case in which apparently unrelated mathematical questions were study with the help of permutations happened around 1770, when Joseph Louis Lagrange, in the survey of polynomial equations, detected that property of the permutations of the beginnings of an equation are associated to the possibility to solve it. Fabian Stedman in 1677 described factorials when explaining the number of permutations of Bell in change ringing. The rule to determine the number of permutations of n objects was known in Indian culture around 1150.
/**
* Implement next permutation algorithm. i.e
* Given a word w, rearrange the letters of w to construct another word s in such a way that
* s is lexicographically greater than w.
* In case of multiple possible answers, find the lexicographically smallest one.
* Example:
* ab --> ba
* bb --> bb
* hefg --> hegf
* dhck --> dhkc
* dkhc --> hcdk
*/
#include <iostream>
std::string
next_permutation( std::string str)
{
int len = str.length();
int i = len -1;
// We will iterate string from end, and once we have encountered a pair of letters
// such that str[i] < str[i-1] , i-1 would become our pivot
while( i > 0 && str[i] <= str[i-1] ) {
--i;
}
if ( i == 0 ) {
return str;
}
//our pivot right now would be str[i-1]
int j = len - 1;
while( j >= i && str[j] <= str[i-1] ) {
--j;
}
std::swap(str[i-1], str[j]);
j = len - 1;
//reverse the suffix
while( i < j ) {
std::swap(str[i], str[j]);
--j;
++i;
}
return str;
}
int main()
{
std::string str, str_next;
std::cout << "Enter a string : ";
std::cin >> str;
str_next = next_permutation(str);
std::cout << "Next permutation of " << str << " is "
<< str_next << std::endl;
return 0;
}
