user
Given a zero or positive integer, the task is to generate the next largest integer with the same digits\*1.

* Numbers will not be padded to the left with zeroes.
* Use all given digits, with their given multiplicity. (If a digit appears twice in the input number, it should appear twice in the result).
* If there is no next highest integer return zero.

:   \*1   Alternatively phrased as:   "Find the smallest integer larger than the (positive or zero) integer   **N**

    :   which can be obtained by reordering the (base ten) digits of   **N**".

Algorithm 1

1. Generate all the permutations of the digits and sort into numeric order.
2. Find the number in the list.
3. Return the next highest number from the list.

The above could prove slow and memory hungry for numbers with large numbers of
digits, but should be easy to reason about its correctness.

Algorithm 2

1. Scan right-to-left through the digits of the number until you find a digit with a larger digit somewhere to the right of it.
2. Exchange that digit with the smallest digit on the right that is greater than it.
3. Order the digits to the right of this position, after the swap; lowest-to-highest, left-to-right. (that is, so they form the lowest numerical representation)

**E.g.:**

```
    n = 12453
<scan>
    12_4_53
<swap>
    12_5_43
<order-right>
    12_5_34

    return: 12534

```

This second algorithm is faster and more memory efficient, but implementations
may be harder to test.

One method of testing, (as used in developing the task),   is to compare results from both
algorithms for random numbers generated from a range that the first algorithm can handle.

Task requirements

Calculate the next highest integer from the digits of the following numbers:

:   * 0
    * 9
    * 12
    * 21
    * 12453
    * 738440
    * 45072010
    * 95322020

Optional stretch goal
:   * 9589776899767587796600
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2020.01

Minimal error trapping. Assumes that the passed number is an integer. Handles positive or negative integers, always returns next largest regardless (if possible).

```
use Lingua::EN::Numbers;

sub next-greatest-index ($str, &op = &infix:«<» ) {
    my @i = $str.comb;
    (1..^@i).first: { &op(@i[$_ - 1], @i[$_]) }, :end, :k;
}

multi next-greatest-integer (Int $num where * >= 0) {
    return 0 if $num.chars < 2;
    return $num.flip > $num ?? $num.flip !! 0 if $num.chars == 2;
    return 0 unless my $i = next-greatest-index( $num ) // 0;
    my $digit = $num.substr($i, 1);
    my @rest  = (flat $num.substr($i).comb).sort(+*);
    my $next  = @rest.first: * > $digit, :k;
    $digit    = @rest.splice($next,1);
    join '', flat $num.substr(0,$i), $digit, @rest;
}

multi next-greatest-integer (Int $num where * < 0) {
    return 0 if $num.chars < 3;
    return $num.abs.flip < -$num ?? -$num.abs.flip !! 0 if $num.chars == 3;
    return 0 unless my $i = next-greatest-index( $num, &CORE::infix:«>» ) // 0;
    my $digit = $num.substr($i, 1);
    my @rest  = (flat $num.substr($i).comb).sort(-*);
    my $next  = @rest.first: * < $digit, :k;
    $digit    = @rest.splice($next,1);
    join '', flat $num.substr(0,$i), $digit, @rest;
}

say "Next largest integer able to be made from these digits, or zero if no larger exists:";
printf "%30s  -> %s%s\n", .&comma, .&next-greatest-integer < 0 ?? '' !! ' ', .&next-greatest-integer.&comma for
    flat 0, (9, 12, 21, 12453, 738440, 45072010, 95322020, 9589776899767587796600, 3345333,
    95897768997675877966000000000000000000000000000000000000000000000000000000000000000000).map: { $_, -$_ };

```

Output:

```
Next largest integer able to be made from these digits, or zero if no larger exists:
                             0  ->  0
                             9  ->  0
                            -9  ->  0
                            12  ->  21
                           -12  ->  0
                            21  ->  0
                           -21  -> -12
                        12,453  ->  12,534
                       -12,453  -> -12,435
                       738,440  ->  740,348
                      -738,440  -> -738,404
                    45,072,010  ->  45,072,100
                   -45,072,010  -> -45,072,001
                    95,322,020  ->  95,322,200
                   -95,322,020  -> -95,322,002
 9,589,776,899,767,587,796,600  ->  9,589,776,899,767,587,900,667
-9,589,776,899,767,587,796,600  -> -9,589,776,899,767,587,796,060
                     3,345,333  ->  3,353,334
                    -3,345,333  -> -3,343,533
95,897,768,997,675,877,966,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000  ->  95,897,768,997,675,879,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,667
-95,897,768,997,675,877,966,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000  -> -95,897,768,997,675,877,960,600,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
```