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 std.algorithm;
import std.array;
import std.conv;
import std.stdio;
 
string next(string s) {
    auto sb = appender!string;
    auto index = s.length - 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.
    while (index > 0 && s[index - 1] >= s[index]) {
        index--;
    }
    //  Reached beginning.  No next number.
    if (index == 0) {
        return "0";
    }
 
    //  Find digit on the right that is both more than it, and closest to it.
    auto index2 = index;
    foreach (i; index + 1 .. s.length) {
        if (s[i] < s[index2] && s[i] > s[index - 1]) {
            index2 = i;
        }
    }
 
    //  Found data, now build string
    //  Beginning of String
    if (index > 1) {
        sb ~= s[0 .. index - 1];
    }
 
    //  Append found, place next
    sb ~= s[index2];
 
    //  Get remaining characters
    auto chars = [cast(dchar) s[index - 1]];
    foreach (i; index .. s.length) {
        if (i != index2) {
            chars ~= s[i];
        }
    }
 
    //  Order the digits to the right of this position, after the swap; lowest-to-highest, left-to-right.
    chars.sort;
    sb ~= chars;
 
    return sb.data;
}
 
long factorial(long n) {
    long fact = 1;
    foreach (num; 2 .. n + 1) {
        fact *= num;
    }
    return fact;
}
 
void testAll(string s) {
    writeln("Test all permutations of: ", s);
    string sOrig = s;
    string sPrev = s;
    int count = 1;
 
    //  Check permutation order.  Each is greater than the last
    bool orderOk = true;
    int[string] uniqueMap = [s: 1];
    while (true) {
        s = next(s);
        if (s == "0") {
            break;
        }
 
        count++;
        if (s.to!long < sPrev.to!long) {
            orderOk = false;
        }
        uniqueMap.update(s, {
            return 1;
        }, (int a) {
            return a + 1;
        });
        sPrev = s;
    }
    writeln("    Order:  OK =  ", orderOk);
 
    //  Test last permutation
    auto reverse = sOrig.dup.to!(dchar[]).reverse.to!string;
    writefln("    Last permutation:  Actual = %s, Expected = %s, OK = %s", sPrev, reverse, sPrev == reverse);
 
    //  Check permutations unique
    bool unique = true;
    foreach (k, v; uniqueMap) {
        if (v > 1) {
            unique = false;
            break;
        }
    }
    writeln("    Permutations unique:  OK =  ", unique);
 
    //  Check expected count.
    int[char] charMap;
    foreach (c; sOrig) {
        charMap.update(c, {
            return 1;
        }, (int v) {
            return v + 1;
        });
    }
    long permCount = factorial(sOrig.length);
    foreach (k, v; charMap) {
        permCount /= factorial(v);
    }
    writefln("    Permutation count:  Actual = %d, Expected = %d, OK = %s", count, permCount, count == permCount);
}
 
void main() {
    foreach (s; ["0", "9", "12", "21", "12453", "738440", "45072010", "95322020", "9589776899767587796600", "3345333"]) {
        writeln(s, " -> ", next(s));
    }
 
    testAll("12345");
    testAll("11122");
}