Find next highest number with the same digits

Question

Question:

Given any integer, efficiently find the next highest integer that uses the same digits. For example if the number is 15432, you should return 21345.

Program: I have written a program which automatically generates a random number in the range random.randint(999, 999999):

print "Find the Next highest number!"
# Find the next highest digit which needs to be corrected.
# Two step approach.
#########
# Step1. Check all the digits expect the highest digit.
# Whether that needs to be corrected. 
# If yes, place next higest digit and sort the remaning digits after the placed
# digit.
#########
# Step2
# The highest digit needs to be changed. 
# This occurs when all the remaning digit except the highest digit is in decending order
# Perform the following task
# 1. Shift rotate the number right by one digit. i.e. place the last digit to the 
# hightest index and shift the current highest digit once place right.
# 2. sort the remaning digits in the acending order.
# 3. Join the digits in index 0 and 1 with the sorted list in step2
# eg: 15432
# 1. 21543
# 2. 345 
# 3. 21345
import sys
import random
number = random.randint(999,999999)
stringArr = str(number)
numberList = list(stringArr) # Given Number converted in list format
str_excpet_highest_digit = stringArr[1:]
array_excpet_highest_digit = list(str_excpet_highest_digit)
correct_Index = -1 
correct_Digit = -1 # current digit what is moved from the existing index 
digit_Moved = -1 # digit what is moved in to the correct index location
highestDigitChanged = -1 
###### Functions #######
def swapDigitAtInidix(fromIndex,toIndex,array):
 temp = array[fromIndex]
 array[fromIndex] = array[toIndex]
 array[toIndex] = temp
 return array # end function
def sortRemainingList(startIndex,array):
 sortedList = []
 temp = []
 for i in range(startIndex):
 sortedList.append(array[i]) 
 for j in range(startIndex,len(array)):
 temp.append(array[j]) 
 # sort the right part of the list
 temp=sorted(temp)
 convertToString1 = ''.join(sortedList)
 convertToString2 = ''.join(temp)
 sortedString = convertToString1 + convertToString2
 sortedList = list(sortedString)
 print "Number except the highest digit:",sortedList
 return sortedList # end function
# This will check the highest digit to be replaced. Returns the updated number
def highestDigitTobeChanged(numberList):
 highestDigit = numberList[0]
 newHighestDigit = -1 
 # find the next highest number
 for i in range(len(numberList)):
 if highestDigit < numberList[i]:
 numberList = swapDigitAtInidix(0,i,numberList) 
 strNUmber = ''.join(numberList)
 strTemp = strNUmber[1:]
 strSorted = ''.join(sorted(strTemp))
 strNUmber = strNUmber[0] + strSorted
 return strNUmber
##### All Fucntions Defined #####
###### Start ######
print "Given Number:", number
##### Step1 #####
print "List without highest digit:",array_excpet_highest_digit
for i in range(len(str_excpet_highest_digit)-1):
 # Find the higest index. 
 if (array_excpet_highest_digit[i] < array_excpet_highest_digit[i+1]) and correct_Index == -1:
 correct_Index = i 
 correct_Digit = array_excpet_highest_digit[i]
 # swap the digit 
 array_excpet_highest_digit = swapDigitAtInidix(i,i+1,array_excpet_highest_digit)
 digit_Moved = array_excpet_highest_digit[i] 
 print "MOdified List without higest digit",array_excpet_highest_digit 
 # To check whether the new moved digit is the next bigger digit 
 elif (correct_Index != -1 ) and ( correct_Digit < array_excpet_highest_digit[i] and digit_Moved > array_excpet_highest_digit[i] ):
 array_excpet_highest_digit = swapDigitAtInidix(correct_Index,i,array_excpet_highest_digit)
 digit_Moved = array_excpet_highest_digit[correct_Index]
 print "MOdified List without higest digit",array_excpet_highest_digit 
 # To check whether the new moved digit is the next bigger digit. Apply this for the last element in the list 
 if (correct_Index != -1 ) and ( correct_Digit < array_excpet_highest_digit[i+1] and digit_Moved > array_excpet_highest_digit[i+1] ):
 array_excpet_highest_digit = swapDigitAtInidix(correct_Index,i+1,array_excpet_highest_digit)
 digit_Moved = array_excpet_highest_digit[correct_Index]
 print "MOdified List without higest digit",array_excpet_highest_digit 
##### Step2 #####
if correct_Index == -1:
 # Except the highest digit all other digits in decending order. Which means Step1 needs to be done.
 finalNumber = highestDigitTobeChanged(numberList)
else:
 # Create the remaining sorted list 
 array_excpet_highest_digit = sortRemainingList(correct_Index+1,array_excpet_highest_digit)
 tmpfinalString=''.join(array_excpet_highest_digit)
 finalNumber = int(stringArr[0] + tmpfinalString)
print "Next Higest Number:", finalNumber

Please let me know if there are any better solutions.

• Martin R: This sounds like a programming contest question. Can you give a reference to the origin?
• SylvainD: Google found this : thereq.com/q/151/technical-software-interview-question/… . Not sure if this is the original question.

Answer 1

Your approach doesn't actually work; for example, for number = 217294 it gives the result as 221479 (what about 217429 or the other nine numbers between the two?)

---

Your code is not compliant with Python's style guide and documentation conventions, including the following:

1. import statements in the wrong order, not separated from the body of the code, and one isn't even used;
2. function and variable names not lowercase_with_underscores (or even consistent); and
3. block comments not in docstring form.

---

You could make much more use of function definitions; all that should run directly is something like the following, at the bottom of the script:

if __name__ == "__main__":
 import random # isn't needed by any other functions
 test = random.randint(999, 999999)
 print "Input number: {0}".format(test)
 result = find_next_highest(test)
 print "Next highest number with same digits: {0}".format(result)

This allows you to import your functions elsewhere without having to run anything. It would also make testing your code much easier if more of it were inside functions.

• python_lover: Could you tell me what is the correct way to name the functions, variables, modules etc.. in python ?
• jonrsharpe: @python_lover that information is all in the style guide, to which I've provided a link in the answer