Algorithm to find next greater permutation of a given string

Question

I want an efficient algorithm to find the next greater permutation of the given string.

Answer 1

Wikipedia has a nice article on lexicographical order generation. It also describes an algorithm to generate the next permutation.

Quoting:

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation.
2. Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
3. Swap s[i] with s[j].
4. Reverse the order of all of the elements after index i till the last element.

Answer 2

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;
}

Answer 3

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 -

1. Find a index 'pivot' from the end of the array such that nums[i - 1] < nums[i]
2. Find index j, such that nums[j] > nums[pivot - 1]
3. Swap both these indexes
4. Reverse the suffix starting at pivot

Answer 4

Homework? Anyway, can look at the C++ function std::next_permutation, or this:

http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html

Answer 5

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++.

Answer 6

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.

Answer 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());
}}

Answer 8

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()); 

}    

}

Answer 9

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.

Answer 10

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

Answer 11

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'])

Answer 12

1. Start traversing from the end of the list. Compare each one with the previous index value.
2. If the previous index (say at index i-1) value, consider x, is lower than the current index (index i) value, sort the sublist on right side starting from current position i.

3. Pick one value from the current position till end which is just higher than x, and put it at index i-1. At the index the value was picked from, put x. 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}.

Answer 13

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;
}

Answer 14

I hope this code might be helpful.

int main() {

    char str[100];
    cin>>str;
    int len=strlen(len);
    int f=next_permutation(str,str+len);    
    if(f>0) {
        print the string
    } else {
        cout<<"no answer";
    }
}