Next Permutation definition

Question

Implement the next permutation, which rearranges numbers into the numerically next greater permutation of numbers for a given array A of size N.

If such arrangement is not possible, it must be rearranged as the lowest possible order i.e., sorted in an ascending order.

The test cases of this problem include :

Input : A = [20, 50, 113]

Output : [20, 113, 50]

How is [20, 113, 50] greater than [20, 50, 113]?

Similarly , Input : A = [5, 18, 9]

Output : [9, 5, 18]

How is this next permutation rather than [5,9,18]?

Answer 1

How is [20, 113, 50] greater than [20, 50, 113]?

Because it's lexicographically greater than, this works as follows:

1. If the first item is greater than or less than then this is the result.

2. Otherwise if they're equal then if the second item is greater than or less than then this is the result.

3. Otherwise if they're equal then if the third item is greater than or less than then this is the result.

4. Otherwise they're equal.

So [20, 113, 50] > [20, 50, 113] because in step 1: 20 == 20 and in step 2: 113 > 50.

Likewise: [5, 9, 18] < [5, 18, 9] because 9 < 18 and [9, 5, 18] > [5, 18, 9] because 9 > 5.