3
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Could you tell me what is the correct way to name the functions, variables, modules etc.. in python ? \$\endgroup\$ – python_lover Oct 20 '14 at 9:46
  • \$\begingroup\$ @python_lover that information is all in the style guide, to which I've provided a link in the answer \$\endgroup\$ – jonrsharpe Oct 20 '14 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.