3
votes

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]?

2
The word "numerically" is a bit confusing; "lexically" is what they mean. - molbdnilo
And to solve this, we have std::next_permutation. - Jarod42

2 Answers

6
votes

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.

0
votes
  1. How is [20, 113, 50] greater than [20, 50, 113]?

    In [20, 50, 113], the last increasing length-2 interval is [50, 113], then we pick the first element in [113, 113](eq. to [113]) from right to left so that it is greater than 50. Swap it with 50, then reverse the interval (50, 113], This will give you [20, 113, 50].

  2. Output : [9, 5, 18]\n How is this next permutation rather than [5,9,18]?

    From A = [5, 18, 9] Found [5, 18],
    From [18, 9] Found 9,
    Swap(5,9) Get [9, 18, 5],
    Reverse([18, 5]) Get [5, 18],
    So you get: [9, 5, 18].