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.

About these ads