Next Permutattion: Vivek Sir
4 posters
Page 1 of 1
Next Permutattion: Vivek Sir
shivang Mon Feb 02, 2009 3:34 am
Write a prog to find the next permutation of a given String in Lexicographic order?
shivang- Posts : 42
Join date : 2009-01-30
Age : 35
Re: Next Permutattion: Vivek Sir
ramthegreatcv Mon Feb 02, 2009 11:58 pm
- Code:
#include<iostream>
#include<string>
/*
1) Find the largest position i such that a_{i} < a_{i+1}
2) Replace a_i with the smallest value a_{i+1}...a_{n} that is bigger than the value of a_{i}
3) Reassign the values from the remaining elements a_{i+1}...a_{n} (including the original a_{i})
in lexicographically increasing order.
*/
using namespace std;
string func(string str)
{
char temp;
int min,index;
/*find index*/
for(int i=str.length()-2;i>0;i--)
{
if(str[i] < str[i+1])
{
index = i;
break;
}
}
/*swap as in step 2*/
min = index+1;
for(int i=index+2 ; i<str.length() ; i++)
{
if(str[min] > str[i] && str[i]>str[index] )
min = i;
}
if(min<str.length() && str[min]>str[index])
{
temp = str[min];
str[min] = str[index];
str[index] = temp;
}
/*
sort from the index
*/
for(int i=index+1;i<str.length()-1;i++)
{
min=i;
for(int j=i+1;j<str.length();j++)
{
if(str[min] > str[j])
min=j;
}
if(min !=i)
{
temp = str[min];
str[min] = str[i];
str[i] = temp;
}
}
return str;
}
int main()
{
string str="abcd";
cout<<"first "<<str<<endl;
string nextPermutation = func(str);
cout<<"next: "<<nextPermutation<<endl;
nextPermutation = func(nextPermutation);
cout<<"next: "<<nextPermutation<<endl;
nextPermutation = func(nextPermutation);
cout<<"next: "<<nextPermutation<<endl;
nextPermutation = func(nextPermutation);
cout<<"next: "<<nextPermutation<<endl;
}
ramthegreatcv- Posts : 55
Join date : 2009-01-30
Age : 35
Re: Next Permutattion: Vivek Sir
Beagle Tue Feb 03, 2009 10:02 am
Take any string of any length.
Suppose i take 'abedc'
I have to find the next permutation of this string ( lexicographically )
Start from the end of the string.
if (str[j] < str[j-1]) { // moving left.
//...... keep on moving to the left
j--;
continue;
}
else if (str[j] > str[j-1]) { // we found our first element which has to be replaced by next lexicographic character in the string, because that //alone will give the next permuation
save (j-1);
<any>sortFromIndex(j); // sort from index j (non decreasingly) to the end of the string.
//Now from the sorted string swap the characters present at location str[j] and str[len-1]
str[j]<->str[len-1];
} // this will give next permutation.
For the example string taken by me... the next permuation will be step by step...
a..b..e..d..c
...........j-1..j
a..b..e..d..c
.......j-1..j
a..b..e..d..c
....j-1..j.....// stop here
a..b..c..d..e // after sorting from j to strlen(str)
a..e..c..d..b // next permutation (swapping str[j] with str[len-1])
Suppose i take 'abedc'
I have to find the next permutation of this string ( lexicographically )
Start from the end of the string.
if (str[j] < str[j-1]) { // moving left.
//...... keep on moving to the left
j--;
continue;
}
else if (str[j] > str[j-1]) { // we found our first element which has to be replaced by next lexicographic character in the string, because that //alone will give the next permuation
save (j-1);
<any>sortFromIndex(j); // sort from index j (non decreasingly) to the end of the string.
//Now from the sorted string swap the characters present at location str[j] and str[len-1]
str[j]<->str[len-1];
} // this will give next permutation.
For the example string taken by me... the next permuation will be step by step...
a..b..e..d..c
...........j-1..j
a..b..e..d..c
.......j-1..j
a..b..e..d..c
....j-1..j.....// stop here
a..b..c..d..e // after sorting from j to strlen(str)
a..e..c..d..b // next permutation (swapping str[j] with str[len-1])
Beagle- Posts : 40
Join date : 2009-01-30
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum|
|
|