Next Greater Number Formed From The Digits Of Given Number in Python

In this post we will describe the method to generate the just next greater number that can be formed from the digits of the given number. Here the next greater number will have the same number of digits as in the given number. The repetition of digits is also allowed.

In order to make the immediate next number which will be greater than the given number, we must increase the sequence as little as possible. Therefore we need to start modifying the rightmost element and leave the left side unchanged.

You may also learn,

• Build a Number Guessing Game in Python
• Pascal Triangle in Python -A Problem on Looping Construct

Algorithm to find Next Greater Number Formed From The Digits Of Given Number

Firstly we need to identify the longest continuous substring (which we will refer as suffix) that is non-increasing. Consider the example:

1 3 4 7 5 5 2

Here the longest suffix that is non-increasing is 7 5 5 2.

Now this suffix is already the highest permutation, so we can’t make a next greater permutation just by modifying it. Hence, we will modify the elements to the left of the suffix.

Secondly, choose the element immediately to the left of suffix (here its 4) which we will refer as pivot. If there is no such element then it implies that the entire sequence is non-increasing. In this case, the given number is already the greatest number that can be formed from the digits of number chosen. Therefore, we can not generate a number which will be greater than it. For example:

7 5 4 2 1 0 0

Here the length of longest non-increasing substring is equal to the number of digits in the number. Therefore no pivot element exists. In this case no number exists which will be greater than the above number using the same digits.

Now, if pivot element exists then it will be necessarily smaller than the head of the suffix ( 4 is less than 7 in the first example). Our aim is to swap the pivot element with the smallest element in the suffix which is greater than pivot. This will provide us the starting digits of next greater number to be formed.

In our first example, we will swap 4 with the 5 which is near the end of suffix.

1 3 5 7 5 4 2

Finally, we need to sort the suffix in non-decreasing order so that the new suffix formed is as low as possible. This can also be done by reversing the order of suffix.

New number formed after sorting is:

1 3 5 2 4 5 7

Generate Next Greater Number Formed From The Digits Of Given Number in Python

# user-defined function to generate next greater number formed from the digits of given number
def next_greater(l):

    # i is the pointer which will keep track of the length of longest continuous non-increasing substring
    i = len(l) - 1
    while(i > 0 and l[i - 1] >= l[i]):
        i -= 1

    # i will become zero if the complete sequence of digit is in non-decreasing order
    if(i <= 0):
        return False
    
    # j is the pointer to the elements of suffix in reverse order 
    j = len(l) - 1

    # to find the smallest element in suffix which is greater than the pivot element
    # here i-1 is the pointer to pivot element
    while(l[j] <= l[i - 1]):
        j -= 1

    # swap the pivot with the smallest element in suffix greater than the pivot
    l[i - 1], l[j] = l[j], l[i - 1]
    
    # in the original list, reverse the order of suffix obtained above to form the suffix in sorted order
    l[i : ] = l[len(l) - 1 : i - 1 : -1]
     
    # print the next greater number generated from the chosen digits
    for z in l:
        print(z,end='')
    return True

#n is the no. of digits in the number
n=int(input())

#l is the list which contains the sequence of digits from which number is to be formed
l=list(map(int,input().split()))

check=next_greater(l)
if(check==False):
        print("no greater number can be formed")
    

Output generated will be:

1352457