# Algorithm to find the Lexicographical Next Permutation of a Number or a String – Code in Python

Firstly I am back to writing. I hope to put many articles and code here in the coming weeks.

Problem statement is simple: We need to find the next permutation of a number or string.

For example 112 has next permutation of 121

and a string for example chin has next permutation of chni.

The code has explanation.

def NextPerm(s): Len = len(s) # char at the end of string EndChar = s[Len-1] for i in range (Len-2,-1,-1): # compare with char to left of the last char c = s[i] # if smaller, then it has to be substituted if(c < EndChar): # left to the char under check is remaining the same and put into buffer buff = s[:i] #print buff # find next biggest digit on the right starting from end and notice the last char is the smallest) for j in range(Len-1,i,-1): # check if the digit is bigger if(s[j] > c): break # Add the char to buffer buff = buff + s[j] # book keep the index index = j # add remaining chars in ascending order(reverse order) and put also insert C in its index for j in range(Len-1,i,-1): # check if the the char was used to replace 'c' if(j == index): # if yes, keep 'c' in its place buff = buff + c else: # else copy next char buff = buff + s[j] return(buff) # last char is stored for the loop process EndChar = c # if char are in descending order its the biggest permutation return("its already the biggest permutation") input = raw_input("Enter any number or string : ") print "The next perm is :",NextPerm(input)

OUTPUT:

labuser@ubuntu:~$ python NextPerm.py

Enter any number or string : abc

The next perm is : acb

labuser@ubuntu:~$ python NextPerm.py

Enter any number or string : acb

The next perm is : bac

labuser@ubuntu:~$ python NextPerm.py

Enter any number or string : bac

The next perm is : bca

labuser@ubuntu:~$ python NextPerm.py

Enter any number or string : bca

The next perm is : cab

labuser@ubuntu:~$ python NextPerm.py

Enter any number or string : cab

The next perm is : cba

labuser@ubuntu:~$ python NextPerm.py

Enter any number or string : cba

The next perm is : its already the biggest permutation

labuser@ubuntu:~$

labuser@ubuntu:~$ python NextPerm.py

Enter any number or string : 112

The next perm is : 121

labuser@ubuntu:~$ python NextPerm.py

Enter any number or string : 121

The next perm is : 211

labuser@ubuntu:~$ python NextPerm.py

Enter any number or string : 211

The next perm is : its already the biggest permutation

labuser@ubuntu:~$

Thanks for reading ! Watch out for more articles this month.

complexity is O(n^2) i think we can solve it in O(nlogn) also ..

You can take a look at Algorithm L of Donald Knuth which serves as basis for C++ STL implementation of next_permutation()

blog post

and yeah the one above is O(n^2)