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.

### Like this:

Like Loading...

*Related*

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)