Next highest int from digits: Difference between revisions
Line 1,678: | Line 1,678: | ||
for 45,072,010 ─── the next highest integer is: 45,072,100 |
for 45,072,010 ─── the next highest integer is: 45,072,100 |
||
for 95,322,020 ─── the next highest integer is: 95,322,200 |
for 95,322,020 ─── the next highest integer is: 95,322,200 |
||
</pre> |
|||
=={{header|Ring}}== |
|||
<lang ring> |
|||
load "stdlib.ring" |
|||
nhi = [0,9,12,21,12453,738440,45072010,95322020] |
|||
for p2 = 1 to len(nhi) |
|||
permut = [] |
|||
num2 = nhi[p2] |
|||
nextHighestInt(num2) |
|||
next |
|||
func nextHighestInt(num) |
|||
list = [] |
|||
numStr = string(num) |
|||
lenNum = len(numStr) |
|||
if lenNum = 1 |
|||
see "" + num + " => " + "0" + nl |
|||
return |
|||
ok |
|||
for n = 1 to len(numStr) |
|||
p = number(substr(numStr,n,1)) |
|||
add(list,p) |
|||
next |
|||
lenList = len(list) |
|||
calmo = [] |
|||
permut(list) |
|||
for n = 1 to len(permut)/lenList |
|||
str = "" |
|||
for m = (n-1)*lenList+1 to n*lenList |
|||
str = str + string(permut[m]) |
|||
next |
|||
if str != "" |
|||
strNum = number(str) |
|||
add(calmo,strNum) |
|||
ok |
|||
next |
|||
for n = len(calmo) to 1 step -1 |
|||
lenCalmo = len(string(calmo[n])) |
|||
if lenCalmo < lenNum |
|||
del(calmo,n) |
|||
ok |
|||
next |
|||
calmo = sort(calmo) |
|||
for n = len(calmo) to 2 step -1 |
|||
if calmo[n] = calmo[n-1] |
|||
del(calmo,n) |
|||
ok |
|||
next |
|||
ind = find(calmo,num) |
|||
if ind = len(calmo) |
|||
see "" + num + " => " + "0" + nl |
|||
else |
|||
see "" + num + " => " + calmo[ind+1] + nl |
|||
ok |
|||
func permut(list) |
|||
for perm = 1 to factorial(len(list)) |
|||
for i = 1 to len(list) |
|||
add(permut,list[i]) |
|||
next |
|||
perm(list) |
|||
next |
|||
func perm(a) |
|||
elementcount = len(a) |
|||
if elementcount < 1 then return ok |
|||
pos = elementcount-1 |
|||
while a[pos] >= a[pos+1] |
|||
pos -= 1 |
|||
if pos <= 0 permutationReverse(a, 1, elementcount) |
|||
return ok |
|||
end |
|||
last = elementcount |
|||
while a[last] <= a[pos] |
|||
last -= 1 |
|||
end |
|||
temp = a[pos] |
|||
a[pos] = a[last] |
|||
a[last] = temp |
|||
permReverse(a, pos+1, elementcount) |
|||
func permReverse(a,first,last) |
|||
while first < last |
|||
temp = a[first] |
|||
a[first] = a[last] |
|||
a[last] = temp |
|||
first += 1 |
|||
last -= 1 |
|||
end |
|||
</lang> |
|||
Output: |
|||
<pre> |
|||
0 => 0 |
|||
9 => 0 |
|||
12 => 21 |
|||
21 => 0 |
|||
12453 => 12534 |
|||
738440 => 740348 |
|||
45072010 => 45072100 |
|||
95322020 => 95322200 |
|||
</pre> |
</pre> |
||
Revision as of 10:09, 14 January 2021
You are encouraged to solve this task according to the task description, using any language you may know.
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
AutoHotkey
Permutation Version
<lang AutoHotkey>Next_highest_int(num){ Arr := [] for i, v in permute(num) Arr[v] := true for n, v in Arr if found return n else if (n = num) found := true return 0 } permute(str, k:=0, l:=1){ static res:=[] r := StrLen(str) k := k ? k : r if (l = r) return SubStr(str, 1, k) i := l while (i <= r){ str := swap(str, l, i) x := permute(str, k, l+1) if (x<>"") res.push(x) str := swap(str, l, i++) } if (l=1) return x:=res, res := [] } swap(str, l, i){ x := StrSplit(str), var := x[l], x[l] := x[i], x[i] := var Loop, % x.count() res .= x[A_Index] return res }</lang> Examples:<lang AutoHotkey>MsgBox % "" Next_highest_int(0) . "`n" Next_highest_int(9) . "`n" Next_highest_int(12) . "`n" Next_highest_int(21) . "`n" Next_highest_int(12453) . "`n" Next_highest_int(738440) . "`n" Next_highest_int(45072010) . "`n" Next_highest_int(95322020)</lang>
- Output:
0 0 21 0 12534 740348 45072100 95322200
Scanning Version
<lang AutoHotkey>Next_highest_int(num){ Loop % StrLen(num){ i := A_Index if (left := SubStr(num, 0-i, 1)) < (right := SubStr(num, 1-i, 1)) break } if !(left < right) return 0 x := StrLen(num) - i num := swap(num, x, x+1) Rdigits := rSort(SubStr(num, 1-i)) return SubStr(num,1, StrLen(num)-StrLen(Rdigits)) . Rdigits } swap(str, l, i){ x := StrSplit(str), var := x[l], x[l] := x[i], x[i] := var Loop, % x.count() res .= x[A_Index] return res } rSort(num){ Arr := [] for i, v in StrSplit(num) Arr[v, i] := v for i, obj in Arr for k, v in obj res .= v return res }</lang> Examples:<lang AutoHotkey>MsgBox % "" Next_highest_int(0) . "`n" Next_highest_int(9) . "`n" Next_highest_int(12) . "`n" Next_highest_int(21) . "`n" Next_highest_int(12453) . "`n" Next_highest_int(738440) . "`n" Next_highest_int(45072010) . "`n" Next_highest_int(95322020) . "`n" Next_highest_int("9589776899767587796600") ; pass long numbers as text (between quotes)</lang>
- Output:
0 0 21 0 12534 780344 45072100 95322200 9589776899767587900667
C
<lang c>#include <stdbool.h>
- include <stdio.h>
- include <stdint.h>
- include <stdlib.h>
- include <string.h>
void swap(char* str, int i, int j) {
char c = str[i]; str[i] = str[j]; str[j] = c;
}
void reverse(char* str, int i, int j) {
for (; i < j; ++i, --j) swap(str, i, j);
}
bool next_permutation(char* str) {
int len = strlen(str); if (len < 2) return false; for (int i = len - 1; i > 0; ) { int j = i, k; if (str[--i] < str[j]) { k = len; while (str[i] >= str[--k]) {} swap(str, i, k); reverse(str, j, len - 1); return true; } } return false;
}
uint32_t next_highest_int(uint32_t n) {
char str[16]; snprintf(str, sizeof(str), "%u", n); if (!next_permutation(str)) return 0; return strtoul(str, 0, 10);
}
int main() {
uint32_t numbers[] = {0, 9, 12, 21, 12453, 738440, 45072010, 95322020}; const int count = sizeof(numbers)/sizeof(int); for (int i = 0; i < count; ++i) printf("%d -> %d\n", numbers[i], next_highest_int(numbers[i])); // Last one is too large to convert to an integer const char big[] = "9589776899767587796600"; char next[sizeof(big)]; memcpy(next, big, sizeof(big)); next_permutation(next); printf("%s -> %s\n", big, next); return 0;
}</lang>
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667
C++
This solution makes use of std::next_permutation, which is essentially the same as Algorithm 2. <lang cpp>#include <algorithm>
- include <iostream>
- include <sstream>
- include <gmpxx.h>
using integer = mpz_class;
std::string to_string(const integer& n) {
std::ostringstream out; out << n; return out.str();
}
integer next_highest(const integer& n) {
std::string str(to_string(n)); if (!std::next_permutation(str.begin(), str.end())) return 0; return integer(str);
}
int main() {
for (integer n : {0, 9, 12, 21, 12453, 738440, 45072010, 95322020}) std::cout << n << " -> " << next_highest(n) << '\n'; integer big("9589776899767587796600"); std::cout << big << " -> " << next_highest(big) << '\n'; return 0;
}</lang>
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667
D
<lang d>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");
}</lang>
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667 3345333 -> 3353334 Test all permutations of: 12345 Order: OK = true Last permutation: Actual = 54321, Expected = 54321, OK = true Permutations unique: OK = true Permutation count: Actual = 120, Expected = 120, OK = true Test all permutations of: 11122 Order: OK = true Last permutation: Actual = 22111, Expected = 22111, OK = true Permutations unique: OK = true Permutation count: Actual = 10, Expected = 10, OK = true
Factor
This uses the next-permutation
word from the math.combinatorics
vocabulary. next-permutation
wraps around and returns the smallest lexicographic permutation after the largest one, so additionally we must check if we're at the largest permutation and return zero if so. See the implementation of next-permutation
here.
<lang factor>USING: formatting grouping kernel math math.combinatorics math.parser sequences ;
- next-highest ( m -- n )
number>string dup [ >= ] monotonic? [ drop 0 ] [ next-permutation string>number ] if ;
{
0 9 12 21 12453 738440 45072010 95322020 9589776899767587796600
} [ dup next-highest "%d -> %d\n" printf ] each</lang>
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667
Go
This uses a modified version of the recursive code in the [Permutations#Go] task. <lang go>package main
import (
"fmt" "sort"
)
func permute(s string) []string {
var res []string if len(s) == 0 { return res } b := []byte(s) var rc func(int) // recursive closure rc = func(np int) { if np == 1 { res = append(res, string(b)) return } np1 := np - 1 pp := len(b) - np1 rc(np1) for i := pp; i > 0; i-- { b[i], b[i-1] = b[i-1], b[i] rc(np1) } w := b[0] copy(b, b[1:pp+1]) b[pp] = w } rc(len(b)) return res
}
func algorithm1(nums []string) {
fmt.Println("Algorithm 1") fmt.Println("-----------") for _, num := range nums { perms := permute(num) le := len(perms) if le == 0 { // ignore blanks continue } sort.Strings(perms) ix := sort.SearchStrings(perms, num) next := "" if ix < le-1 { for i := ix + 1; i < le; i++ { if perms[i] > num { next = perms[i] break } } } if len(next) > 0 { fmt.Printf("%29s -> %s\n", commatize(num), commatize(next)) } else { fmt.Printf("%29s -> 0\n", commatize(num)) } } fmt.Println()
}
func algorithm2(nums []string) {
fmt.Println("Algorithm 2") fmt.Println("-----------")
outer:
for _, num := range nums { b := []byte(num) le := len(b) if le == 0 { // ignore blanks continue } max := num[le-1] mi := le - 1 for i := le - 2; i >= 0; i-- { if b[i] < max { min := max - b[i] for j := mi + 1; j < le; j++ { min2 := b[j] - b[i] if min2 > 0 && min2 < min { min = min2 mi = j } } b[i], b[mi] = b[mi], b[i] c := (b[i+1:]) sort.Slice(c, func(i, j int) bool { return c[i] < c[j] }) next := string(b[0:i+1]) + string(c) fmt.Printf("%29s -> %s\n", commatize(num), commatize(next)) continue outer } else if b[i] > max { max = num[i] mi = i } } fmt.Printf("%29s -> 0\n", commatize(num)) }
}
func commatize(s string) string {
le := len(s) for i := le - 3; i >= 1; i -= 3 { s = s[0:i] + "," + s[i:] } return s
}
func main() {
nums := []string{"0", "9", "12", "21", "12453", "738440", "45072010", "95322020", "9589776899767587796600"} algorithm1(nums[:len(nums)-1]) // exclude the last one algorithm2(nums) // include the last one
}</lang>
- Output:
Algorithm 1 ----------- 0 -> 0 9 -> 0 12 -> 21 21 -> 0 12,453 -> 12,534 738,440 -> 740,348 45,072,010 -> 45,072,100 95,322,020 -> 95,322,200 Algorithm 2 ----------- 0 -> 0 9 -> 0 12 -> 21 21 -> 0 12,453 -> 12,534 738,440 -> 740,348 45,072,010 -> 45,072,100 95,322,020 -> 95,322,200 9,589,776,899,767,587,796,600 -> 9,589,776,899,767,587,900,667
Haskell
Permutations
Defining a list of all (if any) digit-shuffle successors of a positive integer, in terms of permutations.
(Generator version) <lang haskell>import Data.List (nub, permutations, sort)
digitShuffleSuccessors :: Integer -> [Integer] digitShuffleSuccessors n =
(fmap . (+) <*> (nub . sort . concatMap go . permutations . show)) n where go ds | 0 >= delta = [] | otherwise = [delta] where delta = (read ds :: Integer) - n
TEST ---------------------------
main :: IO () main =
putStrLn $ fTable "Taking up to 5 digit-shuffle successors of a positive integer:\n" show (\xs -> let harvest = take 5 xs in rjust 12 ' ' (show (length harvest) <> " of " <> show (length xs) <> ": ") <> show harvest) digitShuffleSuccessors [0, 9, 12, 21, 12453, 738440, 45072010, 95322020]
DISPLAY --------------------------
fTable :: String -> (a -> String) -> (b -> String) -> (a -> b) -> [a] -> String fTable s xShow fxShow f xs =
unlines $ s : fmap (((<>) . rjust w ' ' . xShow) <*> ((" -> " <>) . fxShow . f)) xs where w = maximum (length . xShow <$> xs)
rjust :: Int -> Char -> String -> String rjust n c = drop . length <*> (replicate n c <>)</lang>
- Output:
Taking up to 5 digit-shuffle successors of a positive integer: 0 -> 0 of 0: [] 9 -> 0 of 0: [] 12 -> 1 of 1: [21] 21 -> 0 of 0: [] 12453 -> 5 of 116: [12534,12543,13245,13254,13425] 738440 -> 5 of 96: [740348,740384,740438,740483,740834] 45072010 -> 5 of 1861: [45072100,45100027,45100072,45100207,45100270] 95322020 -> 1 of 1: [95322200]
Minimal digit-swaps
Defining a lazily-evaluated list of all digit-shuffle successors, this time in terms of minimal digit swaps (rather than the full set of permutations).
(The digit-swap approach makes it feasible to obtain successors of this kind for much larger numbers)
<lang haskell>import Data.List (unfoldr) import Data.Bool (bool)
MINIMAL DIGIT-SWAPS --------------------
digitShuffleSuccessors
:: Integral b => b -> [b]
digitShuffleSuccessors n =
let go = minimalSwap . splitBy (>) in unDigits <$> unfoldr ((\x -> bool (Just (((,) <*> go . reverse) x)) Nothing) <*> null) (go (reversedDigits n))
minimalSwap
:: Ord a => ([a], [a]) -> [a]
minimalSwap ([], x:y:xs) = reverse (y : x : xs) minimalSwap ([], xs) = [] minimalSwap (_, []) = [] minimalSwap (reversedSuffix, pivot:prefix) =
let (less, h:more) = break (> pivot) reversedSuffix in reverse (h : prefix) ++ less ++ pivot : more
TEST ---------------------------
main :: IO () main = do
putStrLn $ fTable "Taking up to 5 digit-shuffle successors of a positive integer:\n" show (\xs -> let harvest = take 5 xs in rjust 12 ' ' (show (length harvest) <> " of " <> show (length xs) ++ ": ") ++ show harvest) digitShuffleSuccessors [0, 9, 12, 21, 12453, 738440, 45072010, 95322020] putStrLn $ fTable "Taking up to 10 digit-shuffle successors of a larger integer:\n" show (('\n' :) . unlines . fmap ((" " <>) . show)) (take 10 . digitShuffleSuccessors) [9589776899767587796600]
GENERIC --------------------------
reversedDigits
:: Integral a => a -> [a]
reversedDigits 0 = [0] reversedDigits n = go n
where go 0 = [] go x = rem x 10 : go (quot x 10)
splitBy :: (a -> a -> Bool) -> [a] -> ([a], [a]) splitBy f xs = go $ break (uncurry f) $ zip xs (tail xs)
where go (ys, zs) | null ys = ([], xs) | otherwise = (fst (head ys) : map snd ys, map snd zs)
unDigits
:: (Foldable t, Num a) => t a -> a
unDigits = foldl (\a b -> 10 * a + b) 0
DISPLAY --------------------------
fTable :: String -> (a -> String) -> (b -> String) -> (a -> b) -> [a] -> String fTable s xShow fxShow f xs =
unlines $ s : fmap (((<>) . rjust w ' ' . xShow) <*> ((" -> " <>) . fxShow . f)) xs where w = maximum (length . xShow <$> xs)
rjust :: Int -> Char -> String -> String rjust n c = drop . length <*> (replicate n c <>)</lang>
- Output:
Taking up to 5 digit-shuffle successors of a positive integer: 0 -> 0 of 0: [] 9 -> 0 of 0: [] 12 -> 1 of 1: [21] 21 -> 0 of 0: [] 12453 -> 5 of 116: [12534,12543,13245,13254,13425] 738440 -> 5 of 96: [740348,740384,740438,740483,740834] 45072010 -> 5 of 1861: [45072100,45100027,45100072,45100207,45100270] 95322020 -> 1 of 1: [95322200] Taking up to 10 digit-shuffle successors of a larger integer: 9589776899767587796600 -> 9589776899767587900667 9589776899767587900676 9589776899767587900766 9589776899767587906067 9589776899767587906076 9589776899767587906607 9589776899767587906670 9589776899767587906706 9589776899767587906760 9589776899767587907066
J
permutations=: A.&i.~ ! ordered_numbers_from_digits=: [: /:~ ({~ permutations@#)&.": next_highest=: (>:@i:~ { 0 ,~ ]) ordered_numbers_from_digits (,. next_highest)&>0 9 12 21 12453 738440 45072010 95322020 0 0 9 0 12 21 21 0 12453 12534 738440 740348 45072010 45072100 95322020 95322200
Java
Additional testing is performed, including a number with all unique digits and a number with duplicate digits. Included test of all permutations, that the order and correct number of permutations is achieved, and that each permutation is different than all others. If a library is not used, then this testing will provide a better proof of correctness. <lang java> import java.math.BigInteger; import java.text.NumberFormat; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map;
public class NextHighestIntFromDigits {
public static void main(String[] args) { for ( String s : new String[] {"0", "9", "12", "21", "12453", "738440", "45072010", "95322020", "9589776899767587796600", "3345333"} ) { System.out.printf("%s -> %s%n", format(s), format(next(s))); } testAll("12345"); testAll("11122"); }
private static NumberFormat FORMAT = NumberFormat.getNumberInstance(); private static String format(String s) { return FORMAT.format(new BigInteger(s)); }
private static void testAll(String s) { System.out.printf("Test all permutations of: %s%n", s); String sOrig = s; String sPrev = s; int count = 1; // Check permutation order. Each is greater than the last boolean orderOk = true; Map <String,Integer> uniqueMap = new HashMap<>(); uniqueMap.put(s, 1); while ( (s = next(s)).compareTo("0") != 0 ) { count++; if ( Long.parseLong(s) < Long.parseLong(sPrev) ) { orderOk = false; } uniqueMap.merge(s, 1, (v1, v2) -> v1 + v2); sPrev = s; } System.out.printf(" Order: OK = %b%n", orderOk);
// Test last permutation String reverse = new StringBuilder(sOrig).reverse().toString(); System.out.printf(" Last permutation: Actual = %s, Expected = %s, OK = %b%n", sPrev, reverse, sPrev.compareTo(reverse) == 0);
// Check permutations unique boolean unique = true; for ( String key : uniqueMap.keySet() ) { if ( uniqueMap.get(key) > 1 ) { unique = false; } } System.out.printf(" Permutations unique: OK = %b%n", unique); // Check expected count. Map<Character,Integer> charMap = new HashMap<>(); for ( char c : sOrig.toCharArray() ) { charMap.merge(c, 1, (v1, v2) -> v1 + v2); } long permCount = factorial(sOrig.length()); for ( char c : charMap.keySet() ) { permCount /= factorial(charMap.get(c)); } System.out.printf(" Permutation count: Actual = %d, Expected = %d, OK = %b%n", count, permCount, count == permCount);
} private static long factorial(long n) { long fact = 1; for (long num = 2 ; num <= n ; num++ ) { fact *= num; } return fact; } private static String next(String s) { StringBuilder sb = new StringBuilder(); int 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.charAt(index-1) >= s.charAt(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. int index2 = index; for ( int i = index + 1 ; i < s.length() ; i++ ) { if ( s.charAt(i) < s.charAt(index2) && s.charAt(i) > s.charAt(index-1) ) { index2 = i; } } // Found data, now build string // Beginning of String if ( index > 1 ) { sb.append(s.subSequence(0, index-1)); }
// Append found, place next sb.append(s.charAt(index2)); // Get remaining characters List<Character> chars = new ArrayList<>(); chars.add(s.charAt(index-1)); for ( int i = index ; i < s.length() ; i++ ) { if ( i != index2 ) { chars.add(s.charAt(i)); } } // Order the digits to the right of this position, after the swap; lowest-to-highest, left-to-right. Collections.sort(chars); for ( char c : chars ) { sb.append(c); } return sb.toString(); }
} </lang>
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12,453 -> 12,534 738,440 -> 740,348 45,072,010 -> 45,072,100 95,322,020 -> 95,322,200 9,589,776,899,767,587,796,600 -> 9,589,776,899,767,587,900,667 3,345,333 -> 3,353,334 Test all permutations of: 12345 Order: OK = true Last permutation: Actual = 54321, Expected = 54321, OK = true Permutations unique: OK = true Permutation count: Actual = 120, Expected = 120, OK = true Test all permutations of: 11122 Order: OK = true Last permutation: Actual = 22111, Expected = 22111, OK = true Permutations unique: OK = true Permutation count: Actual = 10, Expected = 10, OK = true
JavaScript
<lang javascript>const compose = (...fn) => (...x) => fn.reduce((a, b) => c => a(b(c)))(...x); const toString = x => x + ; const reverse = x => Array.from(x).reduce((p, c) => [c, ...p], []); const minBiggerThanN = (arr, n) => arr.filter(e => e > n).sort()[0]; const remEl = (arr, e) => {
const r = arr.indexOf(e); return arr.filter((e,i) => i !== r);
}
const nextHighest = itr => {
const seen = []; let result = 0; for (const [i,v] of itr.entries()) { const n = +v; if (Math.max(n, ...seen) !== n) { const right = itr.slice(i + 1); const swap = minBiggerThanN(seen, n); const rem = remEl(seen, swap); const rest = [n, ...rem].sort(); result = [...reverse(right), swap, ...rest].join(); break; } else { seen.push(n); } } return result;
};
const check = compose(nextHighest, reverse, toString);
const test = v => {
console.log(v, '=>', check(v));
}
test(0); test(9); test(12); test(21); test(12453); test(738440); test(45072010); test(95322020); test('9589776899767587796600'); </lang>
- Output:
0 => 0 9 => 0 12 => 21 21 => 0 12453 => 12534 738440 => 740348 45072010 => 45072100 95322020 => 95322200 9589776899767587796600 => 9589776899767587900667
Julia
<lang julia>using Combinatorics, BenchmarkTools
asint(dig) = foldl((i, j) -> 10i + Int128(j), dig)
""" Algorithm 1(A) 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. """ function nexthighest_1A(N)
n = Int128(abs(N)) dig = digits(n) perms = unique(sort([asint(arr) for arr in permutations(digits(n))])) length(perms) < 2 && return 0 ((N > 0 && perms[end] == n) || (N < 0 && perms[1] == n)) && return 0 pos = findfirst(x -> x == n, perms) ret = N > 0 ? perms[pos + 1] : -perms[pos - 1] return ret == N ? 0 : ret
end
""" Algorithm 1(B) Iterate through the permutations of the digits of a number and get the permutation that represents the integer having a minimum distance above the given number. Return the number plus the minimum distance. Does not store all the permutations. This saves memory versus algorithm 1A, but we still go through all permutations (slow). """ function nexthighest_1B(N)
n = Int128(abs(N)) dig = reverse(digits(n)) length(dig) < 2 && return 0 mindelta = n for perm in permutations(dig) if (perm[1] != 0) && ((N > 0 && perm > dig) || (N < 0 && perm < dig)) delta = abs(asint(perm) - n) if delta < mindelta mindelta = delta end end end return mindelta < n ? N + mindelta : 0
end
""" 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. Very fast, as it does not need to run through all the permutations of digits. """ function nexthighest_2(N)
n = Int128(abs(N)) dig, ret = digits(n), N length(dig) < 2 && return 0 for (i, d) in enumerate(dig) if N > 0 && i > 1 rdig = dig[1:i-1] if (j = findfirst(x -> x > d, rdig)) != nothing dig[i], dig[j] = dig[j], dig[i] arr = (i == 2) ? dig : [sort(dig[1:i-1], rev=true); dig[i:end]] ret = asint(reverse(arr)) break end elseif N < 0 && i > 1 rdig = dig[1:i-1] if (j = findfirst(x -> x < d, rdig)) != nothing dig[i], dig[j] = dig[j], dig[i] arr = (i == 2) ? dig : [sort(dig[1:i-1]); dig[i:end]] ret = -asint(reverse(arr)) break end end end return ret == N ? 0 : ret
end
println(" N 1A 1B 2\n", "="^98) for n in [0, 9, 12, 21, -453, -8888, 12453, 738440, 45072010, 95322020, -592491602, 9589776899767587796600]
println(rpad(n, 25), abs(n) > typemax(Int) ? " "^50 : rpad(nexthighest_1A(n), 25) * rpad(nexthighest_1B(n), 25), nexthighest_2(n))
end
const n = 7384440 @btime nexthighest_1A(n) println(" for method 1A and n $n.") @btime nexthighest_1B(n) println(" for method 1B and n $n.") @btime nexthighest_2(n) println(" for method 2 and n $n.")
</lang>
- Output:
N 1A 1B 2 ================================================================================================== 0 0 0 0 9 0 0 0 12 21 21 21 21 0 0 0 -453 -435 -435 -435 -8888 0 0 0 12453 12534 12534 12534 738440 740348 740348 740348 45072010 45072100 45072100 45072100 95322020 95322200 95322200 95322200 -592491602 -592491260 -592491260 -592491260 9589776899767587796600 9589776899767587900667 4.027 ms (40364 allocations: 2.43 MiB) for method 1A and n 7384440. 1.237 ms (28804 allocations: 1.92 MiB) for method 1B and n 7384440. 1.260 μs (14 allocations: 1.36 KiB) for method 2 and n 7384440.
Kotlin
<lang scala>import java.math.BigInteger import java.text.NumberFormat
fun main() {
for (s in arrayOf( "0", "9", "12", "21", "12453", "738440", "45072010", "95322020", "9589776899767587796600", "3345333" )) { println("${format(s)} -> ${format(next(s))}") } testAll("12345") testAll("11122")
}
private val FORMAT = NumberFormat.getNumberInstance() private fun format(s: String): String {
return FORMAT.format(BigInteger(s))
}
private fun testAll(str: String) {
var s = str println("Test all permutations of: $s") val sOrig = s var sPrev = s var count = 1
// Check permutation order. Each is greater than the last var orderOk = true val uniqueMap: MutableMap<String, Int> = HashMap() uniqueMap[s] = 1 while (next(s).also { s = it }.compareTo("0") != 0) { count++ if (s.toLong() < sPrev.toLong()) { orderOk = false } uniqueMap.merge(s, 1) { a: Int?, b: Int? -> Integer.sum(a!!, b!!) } sPrev = s } println(" Order: OK = $orderOk")
// Test last permutation val reverse = StringBuilder(sOrig).reverse().toString() println(" Last permutation: Actual = $sPrev, Expected = $reverse, OK = ${sPrev.compareTo(reverse) == 0}")
// Check permutations unique var unique = true for (key in uniqueMap.keys) { if (uniqueMap[key]!! > 1) { unique = false } } println(" Permutations unique: OK = $unique")
// Check expected count. val charMap: MutableMap<Char, Int> = HashMap() for (c in sOrig.toCharArray()) { charMap.merge(c, 1) { a: Int?, b: Int? -> Integer.sum(a!!, b!!) } } var permCount = factorial(sOrig.length.toLong()) for (c in charMap.keys) { permCount /= factorial(charMap[c]!!.toLong()) } println(" Permutation count: Actual = $count, Expected = $permCount, OK = ${count.toLong() == permCount}")
}
private fun factorial(n: Long): Long {
var fact: Long = 1 for (num in 2..n) { fact *= num } return fact
}
private fun next(s: String): String {
val sb = StringBuilder() var 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. var index2 = index for (i in index + 1 until 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.append(s.subSequence(0, index - 1)) }
// Append found, place next sb.append(s[index2])
// Get remaining characters val chars: MutableList<Char> = ArrayList() chars.add(s[index - 1]) for (i in index until s.length) { if (i != index2) { chars.add(s[i]) } }
// Order the digits to the right of this position, after the swap; lowest-to-highest, left-to-right. chars.sort() for (c in chars) { sb.append(c) } return sb.toString()
}</lang>
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12,453 -> 12,534 738,440 -> 740,348 45,072,010 -> 45,072,100 95,322,020 -> 95,322,200 9,589,776,899,767,587,796,600 -> 9,589,776,899,767,587,900,667 3,345,333 -> 3,353,334 Test all permutations of: 12345 Order: OK = true Last permutation: Actual = 54321, Expected = 54321, OK = true Permutations unique: OK = true Permutation count: Actual = 120, Expected = 120, OK = true Test all permutations of: 11122 Order: OK = true Last permutation: Actual = 22111, Expected = 22111, OK = true Permutations unique: OK = true Permutation count: Actual = 10, Expected = 10, OK = true
Perl
<lang perl>use strict; use warnings; use feature 'say'; use bigint; use List::Util 'first';
sub comma { reverse ((reverse shift) =~ s/(.{3})/$1,/gr) =~ s/^,//r }
sub next_greatest_index {
my($str) = @_; my @i = reverse split //, $str; @i-1 - (1 + first { $i[$_] > $i[$_+1] } 0 .. @i-1);
}
sub next_greatest_integer {
my($num) = @_; my $numr; return 0 if length $num < 2; return ($numr = 0 + reverse $num) > $num ? $numr : 0 if length $num == 2; return 0 unless my $i = next_greatest_index( $num ) // 0; my $digit = substr($num, $i, 1); my @rest = sort split , substr($num, $i); my $next = first { $rest[$_] > $digit } 1..@rest; join , substr($num, 0, $i), (splice(@rest, $next, 1)), @rest;
}
say 'Next largest integer able to be made from these digits, or zero if no larger exists:';
for (0, 9, 12, 21, 12453, 738440, 45072010, 95322020, 9589776899767587796600, 3345333) {
printf "%30s -> %s\n", comma($_), comma next_greatest_integer $_;
}</lang>
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12,453 -> 12,534 738,440 -> 740,348 45,072,010 -> 45,072,100 95,322,020 -> 95,322,200 9,589,776,899,767,587,796,600 -> 9,589,776,899,767,587,900,667 3,345,333 -> 3,353,334
Phix
algorithm 1
<lang Phix>function nigh(string n)
sequence p = repeat("",factorial(length(n))) for i=1 to length(p) do p[i] = permute(i,n) end for p = sort(p) integer k = rfind(n,p) return iff(k=length(p)?"0",p[k+1])
end function
constant tests = {"0","9","12","21","12453",
"738440","45072010","95322020"}
-- (crashes on) "9589776899767587796600"} atom t0 = time() for i=1 to length(tests) do
string t = tests[i] printf(1,"%22s => %s\n",{t,nigh(t)})
end for ?elapsed(time()-t0)</lang>
- Output:
0 => 0 9 => 0 12 => 21 21 => 0 12453 => 12534 738440 => 740348 45072010 => 45072100 95322020 => 95322200 "0.2s"
algorithm 2
<lang Phix>function nigh(string n)
integer hi = n[$] for i=length(n)-1 to 1 by -1 do integer ni = n[i] if ni<hi then string sr = sort(n[i..$]) integer k = rfind(ni,sr)+1 n[i] = sr[k] sr[k..k] = "" n[i+1..$] = sr return n end if hi = max(hi,ni) end for return "0"
end function
constant tests = {"0","9","12","21","12453",
"738440","45072010","95322020", "9589776899767587796600"}
atom t0 = time() for i=1 to length(tests) do
string t = tests[i] printf(1,"%22s => %s\n",{t,nigh(t)})
end for ?elapsed(time()-t0)</lang>
- Output:
0 => 0 9 => 0 12 => 21 21 => 0 12453 => 12534 738440 => 740348 45072010 => 45072100 95322020 => 95322200 9589776899767587796600 => 9589776899767587900667 "0s"
Python
Python: Algorithm 2
Like Algorithm 2, but digit order is reversed for easier indexing, then reversed on return. <lang python>def closest_more_than(n, lst):
"(index of) closest int from lst, to n that is also > n" large = max(lst) + 1 return lst.index(min(lst, key=lambda x: (large if x <= n else x)))
def nexthigh(n):
"Return nxt highest number from n's digits using scan & re-order" assert n == int(abs(n)), "n >= 0" this = list(int(digit) for digit in str(int(n)))[::-1] mx = this[0] for i, digit in enumerate(this[1:], 1): if digit < mx: mx_index = closest_more_than(digit, this[:i + 1]) this[mx_index], this[i] = this[i], this[mx_index] this[:i] = sorted(this[:i], reverse=True) return int(.join(str(d) for d in this[::-1])) elif digit > mx: mx, mx_index = digit, i return 0
if __name__ == '__main__':
for x in [0, 9, 12, 21, 12453, 738440, 45072010, 95322020, 9589776899767587796600]: print(f"{x:>12_d} -> {nexthigh(x):>12_d}")</lang>
- Output:
Note underscores are used in integer representations to aid in comparisons.
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12_453 -> 12_534 738_440 -> 740_348 45_072_010 -> 45_072_100 95_322_020 -> 95_322_200 9_589_776_899_767_587_796_600 -> 9_589_776_899_767_587_900_667
Python: Algorithm 1
I would not try it on the stretch goal, otherwise results as above. <lang python>from itertools import permutations
def nexthigh(n):
"Return next highest number from n's digits using search of all digit perms" assert n == int(abs(n)), "n >= 0" this = tuple(str(int(n))) perms = sorted(permutations(this)) for perm in perms[perms.index(this):]: if perm != this: return int(.join(perm)) return 0</lang>
Python: Generator
A variant which defines (in terms of a concatMap over permutations), a generator of all digit-shuffle successors for a given integer:
<lang python>Next highest int from digits
from itertools import chain, islice, permutations, tee
- --------------- LAZY STREAM OF SUCCESSORS ----------------
- digitShuffleSuccessors :: Int -> [Int]
def digitShuffleSuccessors(n):
Iterator stream of all digit-shuffle successors of n, where 0 <= n. def go(ds): delta = int(.join(ds)) - n return [] if 0 >= delta else [delta] return map( add(n), sorted( set(concatMap(go)( permutations(str(n)) )) ) )
- -------------------------- TEST --------------------------
- main :: IO ()
def main():
Taking up to 5 digit-shuffle successors for each:
def showSuccs(n): def go(xs): ys, zs = tee(xs) harvest = take(n)(ys) return ( repr(len(harvest)) + ' of ' + ( repr(len(list(zs))) + ': ' ) ).rjust(12, ' ') + repr(harvest) return go
print( fTable(main.__doc__ + '\n')(str)(showSuccs(5))( digitShuffleSuccessors )([ 0, 9, 12, 21, 12453, 738440, 45072010, 95322020 ]) )
- ------------------------ GENERIC -------------------------
- add (+) :: Num a => a -> a -> a
def add(a):
Curried addition. def go(b): return a + b return go
- concatMap :: (a -> [b]) -> [a] -> [b]
def concatMap(f):
The concatenation of a mapping. The list monad can be derived by using a function f which wraps its output in a list, using an empty list to represent computational failure). def go(xs): return chain.from_iterable(map(f, xs)) return go
- fTable :: String -> (a -> String) ->
- (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
Heading -> x display function -> fx display function -> f -> xs -> tabular string. def gox(xShow): def gofx(fxShow): def gof(f): def goxs(xs): ys = [xShow(x) for x in xs] w = max(map(len, ys))
def arrowed(x, y): return y.rjust(w, ' ') + ( ' -> ' + fxShow(f(x)) ) return s + '\n' + '\n'.join( map(arrowed, xs, ys) ) return goxs return gof return gofx return gox
- take :: Int -> [a] -> [a]
- take :: Int -> String -> String
def take(n):
The prefix of xs of length n, or xs itself if n > length xs. def go(xs): return ( xs[0:n] if isinstance(xs, (list, tuple)) else list(islice(xs, n)) ) return go
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
Taking up to 5 digit-shuffle successors for each: 0 -> 0 of 0: [] 9 -> 0 of 0: [] 12 -> 1 of 1: [21] 21 -> 0 of 0: [] 12453 -> 5 of 116: [12534, 12543, 13245, 13254, 13425] 738440 -> 5 of 96: [740348, 740384, 740438, 740483, 740834] 45072010 -> 5 of 1861: [45072100, 45100027, 45100072, 45100207, 45100270] 95322020 -> 1 of 1: [95322200]
Raku
(formerly Perl 6)
Minimal error trapping. Assumes that the passed number is an integer. Handles positive or negative integers, always returns next largest regardless (if possible).
<lang perl6>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: { $_, -$_ };</lang>
- 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
REXX
<lang rexx>/*REXX program finds the next highest positive integer from a list of decimal digits. */ parse arg n /*obtain optional arguments from the CL*/ if n= | n="," then n= 0 9 12 21 12453 738440 45072010 95322020 /*use the defaults?*/ w= length( commas( word(n, words(n) ) ) ) /*maximum width number (with commas). */
do j=1 for words(n); y= word(n, j) /*process each of the supplied numbers.*/ masky= mask(y) /*build a digit mask for a supplied int*/ lim= copies(9, length(y) ) /*construct a LIMIT for the DO loop. */
do #=y+1 to lim until mask(#)==masky /*search for a number that might work. */ if verify(y, #) \== 0 then iterate /*does # have all the necessary digits?*/ end /*#*/
if #>lim then #= 0 /*if # > lim, then there is no valid #*/ say 'for ' right(commas(y),w) " ─── the next highest integer is: " right(commas(#),w) end /*j*/
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do ?=length(_)-3 to 1 by -3; _= insert(',', _, ?); end; return _ /*──────────────────────────────────────────────────────────────────────────────────────*/ mask: parse arg z, $; @.= 0 /* [↓] build an unsorted digit mask. */
do k=1 for length(z); parse var z _ +1 z; @._= @._ + 1 end /*k*/ do m=0 for 10; if @.m==0 then iterate; $= $ || copies(m, @.m) end /*m*/; return $ /* [↑] build a sorted digit mask.*/</lang>
- output when using the default inputs:
for 0 ─── the next highest integer is: 0 for 9 ─── the next highest integer is: 0 for 12 ─── the next highest integer is: 21 for 21 ─── the next highest integer is: 0 for 12,453 ─── the next highest integer is: 12,534 for 738,440 ─── the next highest integer is: 740,348 for 45,072,010 ─── the next highest integer is: 45,072,100 for 95,322,020 ─── the next highest integer is: 95,322,200
Ring
<lang ring> load "stdlib.ring"
nhi = [0,9,12,21,12453,738440,45072010,95322020]
for p2 = 1 to len(nhi)
permut = [] num2 = nhi[p2] nextHighestInt(num2)
next
func nextHighestInt(num)
list = [] numStr = string(num) lenNum = len(numStr)
if lenNum = 1
see "" + num + " => " + "0" + nl return
ok
for n = 1 to len(numStr)
p = number(substr(numStr,n,1)) add(list,p)
next
lenList = len(list) calmo = []
permut(list)
for n = 1 to len(permut)/lenList
str = "" for m = (n-1)*lenList+1 to n*lenList str = str + string(permut[m]) next if str != "" strNum = number(str) add(calmo,strNum) ok
next
for n = len(calmo) to 1 step -1
lenCalmo = len(string(calmo[n])) if lenCalmo < lenNum del(calmo,n) ok
next
calmo = sort(calmo)
for n = len(calmo) to 2 step -1
if calmo[n] = calmo[n-1] del(calmo,n) ok
next
ind = find(calmo,num) if ind = len(calmo)
see "" + num + " => " + "0" + nl
else
see "" + num + " => " + calmo[ind+1] + nl
ok
func permut(list)
for perm = 1 to factorial(len(list)) for i = 1 to len(list) add(permut,list[i]) next perm(list) next
func perm(a)
elementcount = len(a) if elementcount < 1 then return ok pos = elementcount-1 while a[pos] >= a[pos+1] pos -= 1 if pos <= 0 permutationReverse(a, 1, elementcount) return ok end last = elementcount while a[last] <= a[pos] last -= 1 end temp = a[pos] a[pos] = a[last] a[last] = temp permReverse(a, pos+1, elementcount) func permReverse(a,first,last) while first < last temp = a[first] a[first] = a[last] a[last] = temp first += 1 last -= 1 end
</lang> Output:
0 => 0 9 => 0 12 => 21 21 => 0 12453 => 12534 738440 => 740348 45072010 => 45072100 95322020 => 95322200
Rust
<lang rust>fn next_permutation<T: PartialOrd>(array: &mut [T]) -> bool {
let len = array.len(); if len < 2 { return false; } let mut i = len - 1; while i > 0 { let j = i; i -= 1; if array[i] < array[j] { let mut k = len - 1; while array[i] >= array[k] { k -= 1; } array.swap(i, k); array[j..len].reverse(); return true; } } false
}
fn next_highest_int(n: u128) -> u128 {
use std::iter::FromIterator; let mut chars: Vec<char> = n.to_string().chars().collect(); if !next_permutation(&mut chars) { return 0; } String::from_iter(chars).parse::<u128>().unwrap()
}
fn main() {
for n in &[0, 9, 12, 21, 12453, 738440, 45072010, 95322020, 9589776899767587796600] { println!("{} -> {}", n, next_highest_int(*n)); }
}</lang>
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667
Sidef
<lang ruby>func next_from_digits(n, b = 10) {
var a = n.digits(b).flip
while (a.next_permutation) { with (a.flip.digits2num(b)) { |t| return t if (t > n) } }
return 0
}
say 'Next largest integer able to be made from these digits, or zero if no larger exists:'
for n in (
0, 9, 12, 21, 12453, 738440, 3345333, 45072010, 95322020, 982765431, 9589776899767587796600,
) {
printf("%30s -> %s\n", n, next_from_digits(n))
}</lang>
- Output:
Next largest integer able to be made from these digits, or zero if no larger exists: 0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 3345333 -> 3353334 45072010 -> 45072100 95322020 -> 95322200 982765431 -> 983124567 9589776899767587796600 -> 9589776899767587900667
zkl
<lang zkl>fcn nextHightest(N){ // N is int, BigInt or string -->String. Algorithm 2 // ds:=N.split().copy(); // mutable, int
ds:=N.toString().split("").apply("toInt").copy(); // handle "234" or BigInt if(ds.len()<2) return(0); m:=ds[-1]; foreach i in ([ds.len()-1 .. 0,-1]){ d:=ds[i]; if(d<m){ dz,j,z := ds[i,*], dz.sort().filter1n('>(d)), dz[j];
dz.del(j); // return( ds[0,i].extend( z, dz.sort() ).concat().toInt() ); return( ds[0,i].extend( z, dz.sort() ).concat() );
} m=m.max(d); } "0"
}</lang> <lang zkl>ns:=T(0, 9, 12, 21, 12453, 738440, 45072010, 95322020); foreach n in (ns){ println("%,d --> %,d".fmt(n,nextHightest(n))) }
n:="9589776899767587796600"; // or BigInt(n) println("%s --> %s".fmt(n,nextHightest(n)));</lang>
- Output:
0 --> 0 9 --> 0 12 --> 21 21 --> 0 12,453 --> 12,534 738,440 --> 740,348 45,072,010 --> 45,072,100 95,322,020 --> 95,322,200 9589776899767587796600 --> 9589776899767587900667