Given a zero or positive integer, the task is to generate the next largest
integer using only the given 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

   Generate all the permutations of the digits and sort into numeric order.
   Find the number in the list.
   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

   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.
   Exchange that digit with the digit on the right that is both more than it, and closest to it.
   Order the digits to the right of this position, after the swap; lowest-to-highest, left-to-right. (I.e. 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 int from the digits of the following numbers:

   0
   9
   12
   21
   12453
   738440
   45072010
   95322020


Optional stretch goal

   9589776899767587796600


import "/sort" for Sort, Find
import "/fmt" for Fmt
import "/str" for Str
 
var permute = Fn.new { |s|
    var res = []
    if (s.count == 0) return res
    var bytes = s.bytes.toList
    var rc // recursive closure
    rc = Fn.new { |np|
        if (np == 1) {
            res.add(bytes.map { |b| String.fromByte(b) }.join())
            return
        }
        var np1 = np - 1
        var pp = bytes.count - np1
        rc.call(np1)
        var i = pp
        while (i > 0) {
            var t = bytes[i]
            bytes[i] = bytes[i-1]
            bytes[i-1] = t
            rc.call(np1)
            i = i - 1
        }
        var w = bytes[0]
        for (i in 1...pp+1) bytes[i-1] = bytes[i]
        bytes[pp] = w
    }
    rc.call(bytes.count)
    return res
}
 
var algorithm1 = Fn.new { |nums|
    System.print("Algorithm 1")
    System.print("-----------")
    for (num in nums) {
        var perms = permute.call(num)
        var le = perms.count
        if (le > 0) { // ignore blanks
            Sort.quick(perms)
            var ix = Find.all(perms, num)[2].from
            var next = ""
            if (ix < le-1) {
                for (i in ix + 1...le) {
                    if (Str.gt(perms[i], num)) {
                        next = perms[i]
                        break
                    }
                }
            }
            if (next.count > 0) {
                Fmt.print("$,29s -> $,s", num, next)
            } else {
                Fmt.print("$,29s -> 0", num)
            }
        }
    }
    System.print()
}
 
var algorithm2 = Fn.new { |nums|
    System.print("Algorithm 2")
    System.print("-----------")
    for (num in nums) {
        var bytes = num.bytes.toList
        var le = bytes.count
        var outer = false
        if (le > 0) { // ignore blanks
            var max = num[-1].bytes[0]
            var mi = le - 1
            var i = le - 2
            while (i >= 0) {
                if (bytes[i] < max) {
                    var min = max - bytes[i]
                    var j = mi + 1
                    while (j < le) {
                        var min2 = bytes[j] - bytes[i]
                        if (min2 > 0 && min2 < min) {
                            min = min2
                            mi = j
                        }
                        j = j + 1
                    }
                    var t = bytes[i]
                    bytes[i] = bytes[mi]
                    bytes[mi] = t
                    var c = bytes[i+1..-1]
                    Sort.quick(c)
                    var next = bytes[0...i+1].map { |b| String.fromByte(b) }.join()
                    next = next + c.map { |b| String.fromByte(b) }.join()
                    Fmt.print("$,29s -> $,s", num, next)
                    outer = true
                    break
                } else if (bytes[i] > max) {
                    max = num[i].bytes[0]
                    mi = i
                }
                i = i - 1
            }
        }
        if (!outer) Fmt.print("$29s -> 0", num)
    }
}
 
var nums = ["0", "9", "12", "21", "12453", "738440", "45072010", "95322020", "9589776899767587796600"]
algorithm1.call(nums[0...-1]) // exclude the last one
algorithm2.call(nums)         // include the last one