'Algorithm to find next greater permutation of a given string
I want an efficient algorithm to find the next greater permutation of the given string.
Solution 1:[1]
A great solution that works is described here: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm. And the solution that, if next permutation exists, returns it, otherwise returns false:
function nextPermutation(array) {
var i = array.length - 1;
while (i > 0 && array[i - 1] >= array[i]) {
i--;
}
if (i <= 0) {
return false;
}
var j = array.length - 1;
while (array[j] <= array[i - 1]) {
j--;
}
var temp = array[i - 1];
array[i - 1] = array[j];
array[j] = temp;
j = array.length - 1;
while (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
return array;
}
Solution 2:[2]
Using the source cited by @Fleischpfanzerl:
We follow the steps as below to find the next lexicographical permutation:
nums = [0,1,2,5,3,3,0]
nums = [0]*5
curr = nums[-1]
pivot = -1
for items in nums[-2::-1]:
if items >= curr:
pivot -= 1
curr = items
else:
break
if pivot == - len(nums):
print('break') # The input is already the last possible permutation
j = len(nums) - 1
while nums[j] <= nums[pivot - 1]:
j -= 1
nums[j], nums[pivot - 1] = nums[pivot - 1], nums[j]
nums[pivot:] = nums[pivot:][::-1]
> [1, 3, 0, 2, 3, 5]
So the idea is: The idea is to follow steps -
- Find a index 'pivot' from the end of the array such that nums[i - 1] < nums[i]
- Find index j, such that nums[j] > nums[pivot - 1]
- Swap both these indexes
- Reverse the suffix starting at pivot
Solution 3:[3]
Homework? Anyway, can look at the C++ function std::next_permutation, or this:
http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html
Solution 4:[4]
We can find the next largest lexicographic string for a given string S using the following step.
1. Iterate over every character, we will get the last value i (starting from the first character) that satisfies the given condition S[i] < S[i + 1]
2. Now, we will get the last value j such that S[i] < S[j]
3. We now interchange S[i] and S[j]. And for every character from i+1 till the end, we sort the characters. i.e., sort(S[i+1]..S[len(S) - 1])
The given string is the next largest lexicographic string of S. One can also use next_permutation function call in C++.
Solution 5:[5]
nextperm(a, n)
1. find an index j such that a[j….n - 1] forms a monotonically decreasing sequence.
2. If j == 0 next perm not possible
3. Else
1. Reverse the array a[j…n - 1]
2. Binary search for index of a[j - 1] in a[j….n - 1]
3. Let i be the returned index
4. Increment i until a[j - 1] < a[i]
5. Swap a[j - 1] and a[i]
O(n) for each permutation.
Solution 6:[6]
I came across a great tutorial. link : https://www.youtube.com/watch?v=quAS1iydq7U
void Solution::nextPermutation(vector<int> &a) {
int k=0;
int n=a.size();
for(int i=0;i<n-1;i++)
{
if(a[i]<a[i+1])
{
k=i;
}
}
int ele=INT_MAX;
int pos=0;
for(int i=k+1;i<n;i++)
{
if(a[i]>a[k] && a[i]<ele)
{
ele=a[i];pos=i;
}
}
if(pos!=0)
{
swap(a[k],a[pos]);
reverse(a.begin()+k+1,a.end());
}
}
Solution 7:[7]
void Solution::nextPermutation(vector<int> &a) {
int i, j=-1, k, n=a.size();
for(i=0; i<n-1; i++) if(a[i] < a[i+1]) j=i;
if(j==-1) reverse(a.begin(), a.end());
else {
for(i=j+1; i<n; i++) if(a[j] < a[i]) k=i;
swap(a[j],a[k]);
reverse(a.begin()+j+1, a.end());
}}
Solution 8:[8]
A great solution that works is described here: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm. and if you are looking for
source code:
/**
* method to find the next lexicographical greater string
*
* @param w
* @return a new string
*/
static String biggerIsGreater(String w) {
char charArray[] = w.toCharArray();
int n = charArray.length;
int endIndex = 0;
// step-1) Start from the right most character and find the first character
// that is smaller than previous character.
for (endIndex = n - 1; endIndex > 0; endIndex--) {
if (charArray[endIndex] > charArray[endIndex - 1]) {
break;
}
}
// If no such char found, then all characters are in descending order
// means there cannot be a greater string with same set of characters
if (endIndex == 0) {
return "no answer";
} else {
int firstSmallChar = charArray[endIndex - 1], nextSmallChar = endIndex;
// step-2) Find the smallest character on right side of (endIndex - 1)'th
// character that is greater than charArray[endIndex - 1]
for (int startIndex = endIndex + 1; startIndex < n; startIndex++) {
if (charArray[startIndex] > firstSmallChar && charArray[startIndex] < charArray[nextSmallChar]) {
nextSmallChar = startIndex;
}
}
// step-3) Swap the above found next smallest character with charArray[endIndex - 1]
swap(charArray, endIndex - 1, nextSmallChar);
// step-4) Sort the charArray after (endIndex - 1)in ascending order
Arrays.sort(charArray, endIndex , n);
}
return new String(charArray);
}
/**
* method to swap ith character with jth character inside charArray
*
* @param charArray
* @param i
* @param j
*/
static void swap(char charArray[], int i, int j) {
char temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
}
If you are looking for video explanation for the same, you can visit here.
Solution 9:[9]
This problem can be solved just by using two simple algorithms searching and find smaller element in just O(1) extra space and O(nlogn ) time and also easy to implement .
To understand this approach clearly . Watch this Video : https://www.youtube.com/watch?v=DREZ9pb8EQI
Solution 10:[10]
def result(lst):
if len(lst) == 0:
return 0
if len(lst) == 1:
return [lst]
l = []
for i in range(len(lst)):
m = lst[i]
remLst = lst[:i] + lst[i+1:]
for p in result(remLst):
l.append([m] + p)
return l
result(['1', '2', '3'])
Solution 11:[11]
- Start traversing from the end of the list. Compare each one with the previous index value.
- If the previous index (say at index
i-1) value, considerx, is lower than the current index (indexi) value, sort the sublist on right side starting from current positioni. Pick one value from the current position till end which is just higher than
x, and put it at indexi-1. At the index the value was picked from, putx. That is:swap(list[i-1], list[j]) where j >= i, and the list is sorted from index "i" onwards
Code:
public void nextPermutation(ArrayList<Integer> a) {
for (int i = a.size()-1; i > 0; i--){
if (a.get(i) > a.get(i-1)){
Collections.sort(a.subList(i, a.size()));
for (int j = i; j < a.size(); j++){
if (a.get(j) > a.get(i-1)) {
int replaceWith = a.get(j); // Just higher than ith element at right side.
a.set(j, a.get(i-1));
a.set(i-1, replaceWith);
return;
}
}
}
}
// It means the values are already in non-increasing order. i.e. Lexicographical highest
// So reset it back to lowest possible order by making it non-decreasing order.
for (int i = 0, j = a.size()-1; i < j; i++, j--){
int tmp = a.get(i);
a.set(i, a.get(j));
a.set(j, tmp);
}
}
Example :
10 40 30 20 => 20 10 30 40 // 20 is just bigger than 10
10 40 30 20 5 => 20 5 10 30 40 // 20 is just bigger than 10. Numbers on right side are just sorted form of this set {numberOnRightSide - justBigger + numberToBeReplaced}.
Solution 12:[12]
This is efficient enough up to strings with 11 letters.
// next_permutation example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void nextPerm(string word) {
vector<char> v(word.begin(), word.end());
vector<string> permvec; // permutation vector
string perm;
int counter = 0; //
int position = 0; // to find the position of keyword in the permutation vector
sort (v.begin(),v.end());
do {
perm = "";
for (vector<char>::const_iterator i = v.begin(); i != v.end(); ++i) {
perm += *i;
}
permvec.push_back(perm); // add permutation to vector
if (perm == word) {
position = counter +1;
}
counter++;
} while (next_permutation(v.begin(),v.end() ));
if (permvec.size() < 2 || word.length() < 2) {
cout << "No answer" << endl;
}
else if (position !=0) {
cout << "Answer: " << permvec.at(position) << endl;
}
}
int main () {
string word = "nextperm";
string key = "mreptxen";
nextPerm(word,key); // will check if the key is a permutation of the given word and return the next permutation after the key.
return 0;
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow