Next highest int from digits: Difference between revisions
(→{{header|Lua}}: added Lua solution) |
m (→{{header|Phix}}: use pygments) |
||
(13 intermediate revisions by 11 users not shown) | |||
Line 1: | Line 1: | ||
{{task}} |
{{task}} |
||
Given a zero or positive integer, the task is to generate the next largest |
Given a zero or positive integer, the task is to generate the next largest integer with the same digits<sup>*1</sup>. |
||
integer using only the given digits<sup>*1</sup>. |
|||
* Numbers will not be padded to the left with zeroes. |
* Numbers will not be padded to the left with zeroes. |
||
Line 25: | Line 24: | ||
;Algorithm 2: |
;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. |
# 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 |
# Exchange that digit with the smallest digit on the right that is greater than it. |
||
# Order the digits to the right of this position, after the swap; lowest-to-highest, left-to-right. ( |
# 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) |
||
Line 50: | Line 49: | ||
;Task requirements: |
;Task requirements: |
||
Calculate the next highest |
Calculate the next highest integer from the digits of the following numbers: |
||
:* 0 |
:* 0 |
||
:* 9 |
:* 9 |
||
Line 68: | Line 67: | ||
{{trans|Python: Algorithm 2}} |
{{trans|Python: Algorithm 2}} |
||
< |
<syntaxhighlight lang="11l">F closest_more_than(n, lst) |
||
V large = max(lst) + 1 |
V large = max(lst) + 1 |
||
R lst.index(min(lst, key' x -> (I x <= @n {@large} E x))) |
R lst.index(min(lst, key' x -> (I x <= @n {@large} E x))) |
||
Line 88: | Line 87: | ||
L(x) [‘0’, ‘9’, ‘12’, ‘21’, ‘12453’, ‘738440’, ‘45072010’, ‘95322020’, |
L(x) [‘0’, ‘9’, ‘12’, ‘21’, ‘12453’, ‘738440’, ‘45072010’, ‘95322020’, |
||
‘9589776899767587796600’] |
‘9589776899767587796600’] |
||
print(‘#12 -> #12’.format(x, nexthigh(x)))</ |
print(‘#12 -> #12’.format(x, nexthigh(x)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 102: | Line 101: | ||
9589776899767587796600 -> 9589776899767587900667 |
9589776899767587796600 -> 9589776899767587900667 |
||
</pre> |
</pre> |
||
=={{header|Ada}}== |
|||
This uses a variation of Algorithm 1 that only makes one pass through the permutations, and a variation of Algorithm 2 that simplifies finding the digit to swap with. |
|||
<syntaxhighlight lang="ada"> |
|||
-- Next highest integer with same digits |
|||
-- J. Carter 2024 June |
|||
-- Uses the PragmAda Reusable Components (https://github.com/jrcarter/PragmARC) |
|||
with Ada.Text_IO; |
|||
with PragmARC.Permutations; |
|||
with PragmARC.Sorting.Insertion; |
|||
procedure Next_Highest is |
|||
package Permutations is new PragmARC.Permutations (Element => Character); |
|||
procedure Sort is new PragmARC.Sorting.Insertion (Element => Character, Index => Positive, Sort_Set => String); |
|||
subtype Digit is Character range '0' .. '9'; |
|||
function Valid (S : in String) return Boolean is |
|||
(S'First = 1 and S'Length > 0 and (for all C of S => C in Digit) ); |
|||
function Next_P (Value : in String) return String with |
|||
Pre => Valid (Value); |
|||
-- Returns the smallest integer > Value that can be produced from Value's decimal digits, using permutations |
|||
-- Returns zero if there is no such integer |
|||
function Next_S (Value : in String) return String with |
|||
Pre => Valid (Value); |
|||
-- Returns the smallest integer > Value that can be produced from Value's decimal digits, using the Scan, Sort, Scan, and Swap |
|||
-- (SSSS) algorithm |
|||
-- Returns zero if there is no such integer |
|||
function Next_P (Value : in String) return String is |
|||
procedure Check (Image : in Permutations.Sequence; Stop : in out Boolean); |
|||
-- Checks if Image represents an integer > Value and smaller than Smallest |
|||
-- If so, sets Found to True and Smallest to the represented value |
|||
Found : Boolean := False; |
|||
Smallest : String := (Value'Range => '9'); |
|||
procedure Check (Image : in Permutations.Sequence; Stop : in out Boolean) is |
|||
Number : constant String := String (Image); |
|||
begin -- Check |
|||
if Number > Value then |
|||
Found := True; |
|||
Smallest := (if Number < Smallest then Number else Smallest); |
|||
end if; |
|||
end Check; |
|||
begin -- Next_P |
|||
if Value'Length < 2 or (Value'Length = 2 and Value < "12") then |
|||
return "0"; |
|||
end if; |
|||
Permutations.Generate (Initial => Permutations.Sequence (Value), Process => Check'Access); |
|||
return (if Found then Smallest else "0"); |
|||
end Next_P; |
|||
function Next_S (Value : in String) return String is |
|||
Work : String := Value; |
|||
Found : Boolean := False; |
|||
Lower : Positive; |
|||
Higher : Positive; |
|||
begin -- Next_S |
|||
Scan_Lower : for I in reverse 1 .. Work'Last - 1 loop |
|||
if (for some C of Work (I + 1 .. Work'Last) => Work (I) < C) then |
|||
Found := True; |
|||
Lower := I; |
|||
exit Scan_Lower; |
|||
end if; |
|||
end loop Scan_Lower; |
|||
if not Found then |
|||
return "0"; |
|||
end if; |
|||
Sort (Set => Work (Lower + 1 .. Work'Last) ); |
|||
Scan_Higher : for I in Lower + 1 .. Work'Last loop -- The Found test above ensures that this will always assign to Higher |
|||
if Work (I) > Work (Lower) then |
|||
Higher := I; |
|||
exit Scan_Higher; |
|||
end if; |
|||
end loop Scan_Higher; |
|||
Swap : declare |
|||
Temp : constant Character := Work (Lower); |
|||
begin -- Swap |
|||
Work (Lower) := Work (Higher); |
|||
Work (Higher) := Temp; |
|||
end Swap; |
|||
return Work; |
|||
end Next_S; |
|||
Test_1 : constant String := "0"; |
|||
Test_2 : constant String := "9"; |
|||
Test_3 : constant String := "12"; |
|||
Test_4 : constant String := "21"; |
|||
Test_5 : constant String := "12453"; |
|||
Test_6 : constant String := "738440"; |
|||
Test_7 : constant String := "45072010"; |
|||
Test_8 : constant String := "95322020"; |
|||
Stretch : constant String := "9589776899767587796600"; |
|||
begin -- Next_Highest |
|||
Ada.Text_IO.Put_Line (Item => "Using permutations"); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_1'Length => ' ') & Test_1 & ' ' & Next_P (Test_1) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_2'Length => ' ') & Test_2 & ' ' & Next_P (Test_2) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_3'Length => ' ') & Test_3 & ' ' & Next_P (Test_3) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_4'Length => ' ') & Test_4 & ' ' & Next_P (Test_4) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_5'Length => ' ') & Test_5 & ' ' & Next_P (Test_5) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_6'Length => ' ') & Test_6 & ' ' & Next_P (Test_6) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_7'Length => ' ') & Test_7 & ' ' & Next_P (Test_7) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_8'Length => ' ') & Test_8 & ' ' & Next_P (Test_8) ); |
|||
Ada.Text_IO.New_Line; |
|||
Ada.Text_IO.Put_Line (Item => "Using SSSS"); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_1'Length => ' ') & Test_1 & ' ' & Next_S (Test_1) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_2'Length => ' ') & Test_2 & ' ' & Next_S (Test_2) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_3'Length => ' ') & Test_3 & ' ' & Next_S (Test_3) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_4'Length => ' ') & Test_4 & ' ' & Next_S (Test_4) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_5'Length => ' ') & Test_5 & ' ' & Next_S (Test_5) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_6'Length => ' ') & Test_6 & ' ' & Next_S (Test_6) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_7'Length => ' ') & Test_7 & ' ' & Next_S (Test_7) ); |
|||
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_8'Length => ' ') & Test_8 & ' ' & Next_S (Test_8) ); |
|||
Ada.Text_IO.New_Line; |
|||
Ada.Text_IO.Put_Line (Item => Stretch & ' ' & Next_S (Stretch) ); |
|||
end Next_Highest; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Using permutations |
|||
0 0 |
|||
9 0 |
|||
12 21 |
|||
21 0 |
|||
12453 12534 |
|||
738440 740348 |
|||
45072010 45072100 |
|||
95322020 95322200 |
|||
Using SSSS |
|||
0 0 |
|||
9 0 |
|||
12 21 |
|||
21 0 |
|||
12453 12534 |
|||
738440 740348 |
|||
45072010 45072100 |
|||
95322020 95322200 |
|||
9589776899767587796600 9589776899767587900667 |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
|||
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}} |
|||
Should work with any Algol 68 implementation if LONG INT is large to hold the stretch test case.<br> |
|||
Implements algorithm 2. |
|||
<syntaxhighlight lang="algol68"> |
|||
BEGIN # find the next integer > a given integer with the same digits # |
|||
OP - = ( CHAR a, b )INT: ABS a - ABS b; # character subtraction # |
|||
PROC swap = ( REF STRING s, INT a, b )VOID: # swap chars at a and b in s # |
|||
BEGIN CHAR t = s[ a ]; s[ a ] := s[ b ]; s[ b ] := t END; |
|||
# returns the next integer greater than v with the same digits as v # |
|||
OP NEXT = ( LONG INT v )LONG INT: |
|||
BEGIN |
|||
LONG INT result := 0; |
|||
STRING s := whole( v, 0 ); |
|||
INT c pos := UPB s - 1; |
|||
# find the rightmost digit that has a lower digit to the left # |
|||
WHILE IF c pos < LWB s |
|||
THEN FALSE |
|||
ELSE s[ c pos ] >= s[ c pos + 1 ] |
|||
FI |
|||
DO |
|||
c pos -:=1 |
|||
OD; |
|||
IF c pos >= LWB s THEN |
|||
# the digit at c pos is lower than one to its right # |
|||
# swap the lower digit with the smallest right digit greater # |
|||
# than the lower digit # |
|||
CHAR c = s[ c pos ]; |
|||
INT min pos := c pos + 1; |
|||
INT min diff := s[ c pos + 1 ] - c; |
|||
FOR m pos FROM c pos + 2 TO UPB s DO |
|||
IF s[ m pos ] > c THEN |
|||
IF INT this diff = s[ m pos ] - c; |
|||
this diff < min diff |
|||
THEN |
|||
min diff := this diff; |
|||
min pos := m pos |
|||
FI |
|||
FI |
|||
OD; |
|||
swap( s, min pos, c pos ); |
|||
# sort the right digits # |
|||
FOR u FROM UPB s - 1 BY -1 TO c pos + 1 |
|||
WHILE BOOL sorted := TRUE; |
|||
FOR p FROM c pos + 1 BY 1 TO u DO |
|||
IF s[ p ] > s[ p + 1 ] THEN |
|||
swap( s, p, p + 1 ); |
|||
sorted := FALSE |
|||
FI |
|||
OD; |
|||
NOT sorted |
|||
DO SKIP OD; |
|||
# convert back to an integer # |
|||
result := s[ LWB s ] - "0"; |
|||
FOR i FROM LWB s + 1 TO UPB s DO |
|||
result *:= 10 +:= s[ i ] - "0" |
|||
OD |
|||
FI; |
|||
result |
|||
END # NEXT # ; |
|||
# task test cases # |
|||
[]LONG INT tests = ( 0, 9, 12, 21, 12453, 738440, 45072010, 95322020 |
|||
, 9589776899767587796600 |
|||
); |
|||
FOR i FROM LWB tests TO UPB tests DO |
|||
print( ( whole( tests[ i ], -24 ), " -> ", whole( NEXT tests[ i ], 0 ), newline ) ) |
|||
OD |
|||
END |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
0 -> 0 |
|||
9 -> 0 |
|||
12 -> 21 |
|||
21 -> 0 |
|||
12453 -> 12534 |
|||
738440 -> 740348 |
|||
45072010 -> 45072100 |
|||
95322020 -> 95322200 |
|||
9589776899767587796600 -> 9589776899767587900667 |
|||
</pre> |
|||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="arturo">canHaveGreater?: function [n][ |
|||
mydigs: digits n |
|||
maxdigs: reverse sort mydigs |
|||
return some? 0..dec size mydigs 'i -> |
|||
maxdigs\[i] > mydigs\[i] |
|||
] |
|||
nextHighest: function [n][ |
|||
if not? canHaveGreater? n -> return n |
|||
ndigs: sort digits n |
|||
i: n + 1 |
|||
while [ndigs <> sort digits i]-> |
|||
i: i + 1 |
|||
return i |
|||
] |
|||
loop [0, 9, 12, 21, 12453, 738440, 45072010, 95322020] 'num -> |
|||
print [pad (to :string num) 9 "->" nextHighest num]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 0 -> 0 |
|||
9 -> 9 |
|||
12 -> 21 |
|||
21 -> 21 |
|||
12453 -> 12534 |
|||
738440 -> 740348 |
|||
45072010 -> 45072100 |
|||
95322020 -> 95322200</pre> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
===Permutation Version=== |
===Permutation Version=== |
||
< |
<syntaxhighlight lang="autohotkey">Next_highest_int(num){ |
||
Arr := [] |
Arr := [] |
||
for i, v in permute(num) |
for i, v in permute(num) |
||
Line 138: | Line 410: | ||
res .= x[A_Index] |
res .= x[A_Index] |
||
return res |
return res |
||
}</ |
}</syntaxhighlight> |
||
Examples:< |
Examples:<syntaxhighlight lang="autohotkey">MsgBox % "" Next_highest_int(0) |
||
. "`n" Next_highest_int(9) |
. "`n" Next_highest_int(9) |
||
. "`n" Next_highest_int(12) |
. "`n" Next_highest_int(12) |
||
Line 146: | Line 418: | ||
. "`n" Next_highest_int(738440) |
. "`n" Next_highest_int(738440) |
||
. "`n" Next_highest_int(45072010) |
. "`n" Next_highest_int(45072010) |
||
. "`n" Next_highest_int(95322020)</ |
. "`n" Next_highest_int(95322020)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0 |
<pre>0 |
||
Line 157: | Line 429: | ||
95322200</pre> |
95322200</pre> |
||
===Scanning Version=== |
===Scanning Version=== |
||
< |
<syntaxhighlight lang="autohotkey">Next_highest_int(num){ |
||
Loop % StrLen(num){ |
Loop % StrLen(num){ |
||
i := A_Index |
i := A_Index |
||
Line 184: | Line 456: | ||
res .= v |
res .= v |
||
return res |
return res |
||
}</ |
}</syntaxhighlight> |
||
Examples:< |
Examples:<syntaxhighlight lang="autohotkey">MsgBox % "" Next_highest_int(0) |
||
. "`n" Next_highest_int(9) |
. "`n" Next_highest_int(9) |
||
. "`n" Next_highest_int(12) |
. "`n" Next_highest_int(12) |
||
Line 193: | Line 465: | ||
. "`n" Next_highest_int(45072010) |
. "`n" Next_highest_int(45072010) |
||
. "`n" Next_highest_int(95322020) |
. "`n" Next_highest_int(95322020) |
||
. "`n" Next_highest_int("9589776899767587796600") ; pass long numbers as text (between quotes)</ |
. "`n" Next_highest_int("9589776899767587796600") ; pass long numbers as text (between quotes)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0 |
<pre>0 |
||
Line 206: | Line 478: | ||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <stdbool.h> |
||
#include <stdio.h> |
#include <stdio.h> |
||
#include <stdint.h> |
#include <stdint.h> |
||
Line 260: | Line 532: | ||
printf("%s -> %s\n", big, next); |
printf("%s -> %s\n", big, next); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 274: | Line 546: | ||
9589776899767587796600 -> 9589776899767587900667 |
9589776899767587796600 -> 9589776899767587900667 |
||
</pre> |
</pre> |
||
=={{header|C#}}== |
|||
{{trans|Java}} |
|||
<syntaxhighlight lang="C#"> |
|||
using System; |
|||
using System.Collections.Generic; |
|||
using System.Globalization; |
|||
using System.Numerics; |
|||
using System.Text; |
|||
public class NextHighestIntFromDigits |
|||
{ |
|||
public static void Main(string[] args) |
|||
{ |
|||
foreach (var s in new string[] { "0", "9", "12", "21", "12453", "738440", "45072010", "95322020", "9589776899767587796600", "3345333" }) |
|||
{ |
|||
Console.WriteLine($"{Format(s)} -> {Format(Next(s))}"); |
|||
} |
|||
TestAll("12345"); |
|||
TestAll("11122"); |
|||
} |
|||
private static string Format(string s) |
|||
{ |
|||
return BigInteger.Parse(s).ToString("N0", CultureInfo.InvariantCulture); |
|||
} |
|||
private static void TestAll(string s) |
|||
{ |
|||
Console.WriteLine($"Test all permutations of: {s}"); |
|||
var sOrig = s; |
|||
var sPrev = s; |
|||
int count = 1; |
|||
// Check permutation order. Each is greater than the last |
|||
bool orderOk = true; |
|||
var uniqueMap = new Dictionary<string, int>(); |
|||
uniqueMap[s] = 1; |
|||
while ((s = Next(s)) != "0") |
|||
{ |
|||
count++; |
|||
if (BigInteger.Parse(s) < BigInteger.Parse(sPrev)) |
|||
{ |
|||
orderOk = false; |
|||
} |
|||
if (uniqueMap.ContainsKey(s)) |
|||
{ |
|||
uniqueMap[s]++; |
|||
} |
|||
else |
|||
{ |
|||
uniqueMap[s] = 1; |
|||
} |
|||
sPrev = s; |
|||
} |
|||
Console.WriteLine($" Order: OK = {orderOk}"); |
|||
// Test last permutation |
|||
var reverse = Reverse(sOrig); |
|||
Console.WriteLine($" Last permutation: Actual = {sPrev}, Expected = {reverse}, OK = {sPrev == reverse}"); |
|||
// Check permutations unique |
|||
bool unique = true; |
|||
foreach (var key in uniqueMap.Keys) |
|||
{ |
|||
if (uniqueMap[key] > 1) |
|||
{ |
|||
unique = false; |
|||
} |
|||
} |
|||
Console.WriteLine($" Permutations unique: OK = {unique}"); |
|||
// Check expected count. |
|||
var charMap = new Dictionary<char, int>(); |
|||
foreach (var c in sOrig) |
|||
{ |
|||
if (charMap.ContainsKey(c)) |
|||
{ |
|||
charMap[c]++; |
|||
} |
|||
else |
|||
{ |
|||
charMap[c] = 1; |
|||
} |
|||
} |
|||
BigInteger permCount = Factorial(sOrig.Length); |
|||
foreach (var c in charMap.Keys) |
|||
{ |
|||
permCount /= Factorial(charMap[c]); |
|||
} |
|||
Console.WriteLine($" Permutation count: Actual = {count}, Expected = {permCount}, OK = {count == permCount}"); |
|||
} |
|||
private static BigInteger Factorial(int n) |
|||
{ |
|||
BigInteger fact = 1; |
|||
for (int num = 2; num <= n; num++) |
|||
{ |
|||
fact *= num; |
|||
} |
|||
return fact; |
|||
} |
|||
private static string Next(string s) |
|||
{ |
|||
var 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[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. |
|||
int index2 = index; |
|||
for (int i = index + 1; i < s.Length; i++) |
|||
{ |
|||
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.Substring(0, index - 1)); |
|||
} |
|||
// Append found, place next |
|||
sb.Append(s[index2]); |
|||
// Get remaining characters |
|||
List<char> chars = new List<char>(); |
|||
chars.Add(s[index - 1]); |
|||
for (int i = index; i < s.Length; i++) |
|||
{ |
|||
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(); |
|||
foreach (var c in chars) |
|||
{ |
|||
sb.Append(c); |
|||
} |
|||
return sb.ToString(); |
|||
} |
|||
private static string Reverse(string s) |
|||
{ |
|||
var charArray = s.ToCharArray(); |
|||
Array.Reverse(charArray); |
|||
return new string(charArray); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
Line 279: | Line 743: | ||
{{libheader|GMP}} |
{{libheader|GMP}} |
||
This solution makes use of std::next_permutation, which is essentially the same as Algorithm 2. |
This solution makes use of std::next_permutation, which is essentially the same as Algorithm 2. |
||
< |
<syntaxhighlight lang="cpp">#include <algorithm> |
||
#include <iostream> |
#include <iostream> |
||
#include <sstream> |
#include <sstream> |
||
Line 306: | Line 770: | ||
std::cout << big << " -> " << next_highest(big) << '\n'; |
std::cout << big << " -> " << next_highest(big) << '\n'; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 323: | Line 787: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="d">import std.algorithm; |
||
import std.array; |
import std.array; |
||
import std.conv; |
import std.conv; |
||
Line 446: | Line 910: | ||
testAll("12345"); |
testAll("12345"); |
||
testAll("11122"); |
testAll("11122"); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0 -> 0 |
<pre>0 -> 0 |
||
Line 472: | Line 936: | ||
{{libheader| System.Generics.Collections}} |
{{libheader| System.Generics.Collections}} |
||
{{Trans|Go}} |
{{Trans|Go}} |
||
<syntaxhighlight lang="delphi"> |
|||
<lang Delphi> |
|||
program Next_highest_int_from_digits; |
program Next_highest_int_from_digits; |
||
Line 644: | Line 1,108: | ||
{$IFNDEF UNIX} |
{$IFNDEF UNIX} |
||
readln; {$ENDIF} |
readln; {$ENDIF} |
||
end.</ |
end.</syntaxhighlight> |
||
=={{header|EasyLang}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight> |
|||
proc reverse i j . dig[] . |
|||
while i < j |
|||
swap dig[i] dig[j] |
|||
i += 1 |
|||
j -= 1 |
|||
. |
|||
. |
|||
proc next_perm . dig[] . |
|||
if len dig[] >= 2 |
|||
for i = 2 to len dig[] |
|||
if dig[i] < dig[i - 1] |
|||
k = 1 |
|||
while dig[i] >= dig[k] |
|||
k += 1 |
|||
. |
|||
swap dig[i] dig[k] |
|||
reverse 1 i - 1 dig[] |
|||
return |
|||
. |
|||
. |
|||
. |
|||
dig[] = [ ] |
|||
. |
|||
func next_highest n . |
|||
while n > 0 |
|||
digs[] &= n mod 10 |
|||
n = n div 10 |
|||
. |
|||
next_perm digs[] |
|||
for i = len digs[] downto 1 |
|||
r = r * 10 + digs[i] |
|||
. |
|||
return r |
|||
. |
|||
nums[] = [ 0 9 12 21 12453 738440 45072010 95322020 ] |
|||
for n in nums[] |
|||
print n & " -> " & next_highest n |
|||
. |
|||
</syntaxhighlight> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
This uses the <code>next-permutation</code> word from the <code>math.combinatorics</code> vocabulary. <code>next-permutation</code> 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 <code>next-permutation</code> [https://docs.factorcode.org/content/word-next-permutation%2Cmath.combinatorics.html here]. |
This uses the <code>next-permutation</code> word from the <code>math.combinatorics</code> vocabulary. <code>next-permutation</code> 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 <code>next-permutation</code> [https://docs.factorcode.org/content/word-next-permutation%2Cmath.combinatorics.html here]. |
||
{{works with|Factor|0.99 2020-01-23}} |
{{works with|Factor|0.99 2020-01-23}} |
||
< |
<syntaxhighlight lang="factor">USING: formatting grouping kernel math math.combinatorics |
||
math.parser sequences ; |
math.parser sequences ; |
||
Line 660: | Line 1,168: | ||
9589776899767587796600 |
9589776899767587796600 |
||
} |
} |
||
[ dup next-highest "%d -> %d\n" printf ] each</ |
[ dup next-highest "%d -> %d\n" printf ] each</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 673: | Line 1,181: | ||
9589776899767587796600 -> 9589776899767587900667 |
9589776899767587796600 -> 9589776899767587900667 |
||
</pre> |
</pre> |
||
=={{header|FreeBASIC}}== |
|||
===algorithm 1=== |
|||
{{trans|Python}} |
|||
<syntaxhighlight lang="vbnet">Function factorial(n As Integer) As Uinteger |
|||
Return Iif(n = 0, 1, n * factorial(n - 1)) |
|||
End Function |
|||
Sub swap_(s As String, i As Integer, j As Integer) |
|||
Dim As String temp = Mid(s, i, 1) |
|||
Mid(s, i, 1) = Mid(s, j, 1) |
|||
Mid(s, j, 1) = temp |
|||
End Sub |
|||
Sub permute(s As String, l As Integer, r As Integer, perms() As String) |
|||
If l = r Then |
|||
Redim Preserve perms(Ubound(perms) + 1) |
|||
perms(Ubound(perms)) = s |
|||
Else |
|||
For i As Uinteger = l To r |
|||
swap_(s, l, i) |
|||
permute(s, l + 1, r, perms()) |
|||
swap_(s, l, i) ' backtrack |
|||
Next i |
|||
End If |
|||
End Sub |
|||
Sub bubbleSort(arr() As String) |
|||
Dim As Integer i, j, n = Ubound(arr) |
|||
Dim As String temp |
|||
For i = 0 To n - 1 |
|||
For j = 0 To n - i - 1 |
|||
If arr(j) > arr(j + 1) Then |
|||
temp = arr(j) |
|||
arr(j) = arr(j + 1) |
|||
arr(j + 1) = temp |
|||
End If |
|||
Next j |
|||
Next i |
|||
End Sub |
|||
Function nextHigh1(Byref n As String) As String |
|||
Dim As String perms() |
|||
Dim As Uinteger i, idx |
|||
permute(n, 1, Len(n), perms()) |
|||
bubbleSort perms() |
|||
Dim As Uinteger k = Ubound(perms) |
|||
For i = 0 To k |
|||
If perms(i) = n Then |
|||
idx = i |
|||
Exit For |
|||
End If |
|||
Next i |
|||
Return Iif(idx < k, perms(idx + 1), "0") |
|||
End Function |
|||
Dim As String tests1(7) = {"0", "9", "12", "21", "12453", "738440", "45072010", "95322020"} |
|||
Dim As Double t0 = Timer |
|||
For i As Uinteger = 0 To Ubound(tests1) |
|||
Print tests1(i); " => "; nextHigh1(tests1(i)) |
|||
Next i |
|||
Print Chr(10); Timer - t0; "sec."</syntaxhighlight> |
|||
{{out}} |
|||
<pre>0 => 0 |
|||
9 => 0 |
|||
12 => 21 |
|||
21 => 0 |
|||
12453 => 12534 |
|||
738440 => 738440 |
|||
45072010 => 45072010 |
|||
95322020 => 95322020 |
|||
67.04065610002726sec.</pre> |
|||
===algorithm 2=== |
|||
{{trans|Phix}} |
|||
<syntaxhighlight lang="vbnet">Function sort(s As String) As String |
|||
Dim As Uinteger i, j, n = Len(s) |
|||
Dim As String temp |
|||
For i = 1 To n |
|||
For j = i + 1 To n |
|||
If Asc(Mid(s, i, 1)) > Asc(Mid(s, j, 1)) Then |
|||
temp = Mid(s, i, 1) |
|||
Mid(s, i, 1) = Mid(s, j, 1) |
|||
Mid(s, j, 1) = temp |
|||
End If |
|||
Next j |
|||
Next i |
|||
Return s |
|||
End Function |
|||
Function rfind(c As String, s As String) As Uinteger |
|||
Return Instr(s, c) |
|||
End Function |
|||
Function nextHigh2(n As String) As String |
|||
Dim As Uinteger hi = Asc(Right(n, 1)) |
|||
Dim As Uinteger i, ni, idx |
|||
Dim As String sr |
|||
For i = Len(n) - 1 To 1 Step -1 |
|||
ni = Asc(Mid(n, i, 1)) |
|||
If ni < hi Then |
|||
sr = sort(Mid(n, i)) |
|||
idx = rfind(Chr(ni), sr) + 1 |
|||
Mid(n, i, 1) = Mid(sr, idx, 1) |
|||
Mid(sr, idx, 1) = "" |
|||
Mid(n, i + 1) = sr |
|||
Return n |
|||
End If |
|||
hi = Iif(hi > ni, hi, ni) |
|||
Next i |
|||
Return "0" |
|||
End Function |
|||
Dim As String tests2(8) = { "0", "9", "12", "21", "12453", _ |
|||
"738440", "45072010", "95322020", "9589776899767587796600" } |
|||
Dim As Double t1 = Timer |
|||
For i As Uinteger = 0 To Ubound(tests2) |
|||
Print tests2(i); " => "; nextHigh2(tests2(i)) |
|||
Next i |
|||
Print Chr(10); Timer - t1; "sec."</syntaxhighlight> |
|||
{{out}} |
|||
<pre>0 => 0 |
|||
9 => 0 |
|||
12 => 21 |
|||
21 => 0 |
|||
12453 => 12534 |
|||
738440 => 740344 |
|||
45072010 => 45072000 |
|||
95322020 => 95322000 |
|||
9589776899767587796600 => 9589776899767587900667 |
|||
0.004686999949626625sec.</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||
This uses a modified version of the recursive code in the [[https://rosettacode.org/wiki/Permutations#Go Permutations#Go]] task. |
This uses a modified version of the recursive code in the [[https://rosettacode.org/wiki/Permutations#Go Permutations#Go]] task. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 790: | Line 1,439: | ||
algorithm1(nums[:len(nums)-1]) // exclude the last one |
algorithm1(nums[:len(nums)-1]) // exclude the last one |
||
algorithm2(nums) // include the last one |
algorithm2(nums) // include the last one |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 824: | Line 1,473: | ||
{{Trans|Python}} |
{{Trans|Python}} |
||
(Generator version) |
(Generator version) |
||
< |
<syntaxhighlight lang="haskell">import Data.List (nub, permutations, sort) |
||
digitShuffleSuccessors :: Integer -> [Integer] |
digitShuffleSuccessors :: Integer -> [Integer] |
||
Line 862: | Line 1,511: | ||
rjust :: Int -> Char -> String -> String |
rjust :: Int -> Char -> String -> String |
||
rjust n c = drop . length <*> (replicate n c <>)</ |
rjust n c = drop . length <*> (replicate n c <>)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Taking up to 5 digit-shuffle successors of a positive integer: |
<pre>Taking up to 5 digit-shuffle successors of a positive integer: |
||
Line 880: | Line 1,529: | ||
(The digit-swap approach makes it feasible to obtain successors of this kind for much larger numbers) |
(The digit-swap approach makes it feasible to obtain successors of this kind for much larger numbers) |
||
< |
<syntaxhighlight lang="haskell">import Data.List (unfoldr) |
||
------------------- MINIMAL DIGIT-SWAPS ------------------ |
------------------- MINIMAL DIGIT-SWAPS ------------------ |
||
Line 972: | Line 1,621: | ||
rjust :: Int -> Char -> String -> String |
rjust :: Int -> Char -> String -> String |
||
rjust n c = drop . length <*> (replicate n c <>)</ |
rjust n c = drop . length <*> (replicate n c <>)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Taking up to 5 digit-shuffle successors of a positive integer: |
<pre>Taking up to 5 digit-shuffle successors of a positive integer: |
||
Line 1,018: | Line 1,667: | ||
=={{header|Java}}== |
=={{header|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. |
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. |
||
< |
<syntaxhighlight lang="java"> |
||
import java.math.BigInteger; |
import java.math.BigInteger; |
||
import java.text.NumberFormat; |
import java.text.NumberFormat; |
||
Line 1,144: | Line 1,793: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,171: | Line 1,820: | ||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
< |
<syntaxhighlight lang="javascript">const compose = (...fn) => (...x) => fn.reduce((a, b) => c => a(b(c)))(...x); |
||
const toString = x => x + ''; |
const toString = x => x + ''; |
||
const reverse = x => Array.from(x).reduce((p, c) => [c, ...p], []); |
const reverse = x => Array.from(x).reduce((p, c) => [c, ...p], []); |
||
Line 1,214: | Line 1,863: | ||
test(95322020); |
test(95322020); |
||
test('9589776899767587796600'); |
test('9589776899767587796600'); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>0 => 0 |
<pre>0 => 0 |
||
Line 1,227: | Line 1,876: | ||
=={{header|jq}}== |
=={{header|jq}}== |
||
< |
<syntaxhighlight lang="jq"># Generate a stream of all the permutations of the input array |
||
def permutations: |
def permutations: |
||
# Given an array as input, generate a stream by inserting $x at different positions |
# Given an array as input, generate a stream by inserting $x at different positions |
||
Line 1,258: | Line 1,907: | ||
95322020; |
95322020; |
||
task | "\(.) => \(next_highest)"</ |
task | "\(.) => \(next_highest)"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,271: | Line 1,920: | ||
</pre> |
</pre> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Combinatorics, BenchmarkTools |
||
asint(dig) = foldl((i, j) -> 10i + Int128(j), dig) |
asint(dig) = foldl((i, j) -> 10i + Int128(j), dig) |
||
Line 1,361: | Line 2,010: | ||
@btime nexthighest_2(n) |
@btime nexthighest_2(n) |
||
println(" for method 2 and n $n.") |
println(" for method 2 and n $n.") |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
N 1A 1B 2 |
N 1A 1B 2 |
||
Line 1,387: | Line 2,036: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="scala">import java.math.BigInteger |
||
import java.text.NumberFormat |
import java.text.NumberFormat |
||
Line 1,512: | Line 2,161: | ||
} |
} |
||
return sb.toString() |
return sb.toString() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0 -> 0 |
<pre>0 -> 0 |
||
Line 1,537: | Line 2,186: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
Algorithm 2 with a reverse index of digit positions. |
Algorithm 2 with a reverse index of digit positions. |
||
< |
<syntaxhighlight lang="lua">unpack = unpack or table.unpack -- <=5.2 vs >=5.3 polyfill |
||
function nexthighestint(n) |
function nexthighestint(n) |
||
Line 1,569: | Line 2,218: | ||
for _,n in ipairs(tests) do |
for _,n in ipairs(tests) do |
||
print(n .. " -> " .. (nexthighestint(n) or "(none)")) |
print(n .. " -> " .. (nexthighestint(n) or "(none)")) |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>0 -> (none) |
<pre>0 -> (none) |
||
Line 1,584: | Line 2,233: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[NextHighestIntFromDigits] |
||
NextHighestIntFromDigits[n_Integer?NonNegative]:=Module[{digs}, |
NextHighestIntFromDigits[n_Integer?NonNegative]:=Module[{digs}, |
||
digs=IntegerDigits[n]; |
digs=IntegerDigits[n]; |
||
Line 1,591: | Line 2,240: | ||
If[Length[digs]==1,First[digs],RankedMin[digs,2]] |
If[Length[digs]==1,First[digs],RankedMin[digs,2]] |
||
] |
] |
||
NextHighestIntFromDigits/@{0,9,12,21,12453,738440,45072010,95322020}</ |
NextHighestIntFromDigits/@{0,9,12,21,12453,738440,45072010,95322020}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{0, 9, 21, 21, 12534, 740348, 45072100, 95322200}</pre> |
<pre>{0, 9, 21, 21, 12534, 740348, 45072100, 95322200}</pre> |
||
Line 1,597: | Line 2,246: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
Using the scanning algorithm. |
Using the scanning algorithm. |
||
< |
<syntaxhighlight lang="nim">import algorithm |
||
type Digit = range[0..9] |
type Digit = range[0..9] |
||
Line 1,639: | Line 2,288: | ||
when isMainModule: |
when isMainModule: |
||
for n in [0, 9, 12, 21, 12453, 738440, 45072010, 95322020]: |
for n in [0, 9, 12, 21, 12453, 738440, 45072010, 95322020]: |
||
echo n, " → ", nextHighest(n)</ |
echo n, " → ", nextHighest(n)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,653: | Line 2,302: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 1,683: | Line 2,332: | ||
for (0, 9, 12, 21, 12453, 738440, 45072010, 95322020, 9589776899767587796600, 3345333) { |
for (0, 9, 12, 21, 12453, 738440, 45072010, 95322020, 9589776899767587796600, 3345333) { |
||
printf "%30s -> %s\n", comma($_), comma next_greatest_integer $_; |
printf "%30s -> %s\n", comma($_), comma next_greatest_integer $_; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 0 -> 0 |
<pre> 0 -> 0 |
||
Line 1,698: | Line 2,347: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
===algorithm 1=== |
===algorithm 1=== |
||
<!-- |
<!--(phixonline)--> |
||
<syntaxhighlight lang="phix"> |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">nigh</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
function nigh(string n) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)))</span> |
|||
sequence p = repeat("",factorial(length(n))) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
for i=1 to length(p) do |
|||
<span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
p[i] = permute(i,n) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> |
|||
p = sort(p) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">rfind</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> |
|||
integer k = rfind(n,p) |
|||
<span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)?</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> |
|||
return iff(k=length(p)?"0",p[k+1]) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
end function |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"9"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"12"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"21"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"12453"</span><span style="color: #0000FF;">,</span> |
|||
constant tests = {"0","9","12","21","12453", |
|||
<span style="color: #008000;">"738440"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"45072010"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"95322020"</span><span style="color: #0000FF;">}</span> |
|||
"738440","45072010","95322020"} |
|||
<span style="color: #000080;font-style:italic;">-- (crashes on) "9589776899767587796600"}</span> |
|||
-- (crashes on) "9589776899767587796600"} |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
atom t0 = time() |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
for i=1 to length(tests) do |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
string t = tests[i] |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%22s => %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nigh</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)})</span> |
|||
printf(1,"%22s => %s\n",{t,nigh(t)}) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span> |
|||
?elapsed(time()-t0) |
|||
<!--</lang>--> |
|||
</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,732: | Line 2,382: | ||
</pre> |
</pre> |
||
===algorithm 2=== |
===algorithm 2=== |
||
<syntaxhighlight lang="phix"> |
|||
<!--<lang Phix>(phixonline)--> |
|||
function nigh(string n) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">nigh</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
integer hi = n[$] |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">[$]</span> |
|||
for i=length(n)-1 to 1 by -1 do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
integer ni = n[i] |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">ni</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
if ni<hi then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">ni</span><span style="color: #0000FF;"><</span><span style="color: #000000;">hi</span> <span style="color: #008080;">then</span> |
|||
string sr = sort(n[i..$]) |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">sr</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..$])</span> |
|||
integer k = rfind(ni,sr)+1 |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">rfind</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ni</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sr</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> |
|||
n[i] = sr[k] |
|||
<span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> |
|||
sr[k..k] = "" |
|||
<span style="color: #000000;">sr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">..</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span> |
|||
n[i+1..$] = sr |
|||
<span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sr</span> |
|||
return n |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
hi = max(hi,ni) |
|||
<span style="color: #000000;">hi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">hi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ni</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
return "0" |
|||
<span style="color: #008080;">return</span> <span style="color: #008000;">"0"</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
constant tests = {"0","9","12","21","12453", |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"0"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"9"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"12"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"21"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"12453"</span><span style="color: #0000FF;">,</span> |
|||
"738440","45072010","95322020", |
|||
<span style="color: #008000;">"738440"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"45072010"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"95322020"</span><span style="color: #0000FF;">,</span> |
|||
"9589776899767587796600"} |
|||
atom t0 = time() |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
for i=1 to length(tests) do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
string t = tests[i] |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
printf(1,"%22s => %s\n",{t,nigh(t)}) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%22s => %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nigh</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)})</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
?elapsed(time()-t0) |
|||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span> |
|||
</syntaxhighlight> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,777: | Line 2,427: | ||
===Python: Algorithm 2=== |
===Python: Algorithm 2=== |
||
Like Algorithm 2, but digit order is reversed for easier indexing, then reversed on return. |
Like Algorithm 2, but digit order is reversed for easier indexing, then reversed on return. |
||
< |
<syntaxhighlight lang="python">def closest_more_than(n, lst): |
||
"(index of) closest int from lst, to n that is also > n" |
"(index of) closest int from lst, to n that is also > n" |
||
large = max(lst) + 1 |
large = max(lst) + 1 |
||
Line 1,801: | Line 2,451: | ||
for x in [0, 9, 12, 21, 12453, 738440, 45072010, 95322020, |
for x in [0, 9, 12, 21, 12453, 738440, 45072010, 95322020, |
||
9589776899767587796600]: |
9589776899767587796600]: |
||
print(f"{x:>12_d} -> {nexthigh(x):>12_d}")</ |
print(f"{x:>12_d} -> {nexthigh(x):>12_d}")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,817: | Line 2,467: | ||
===Python: Algorithm 1=== |
===Python: Algorithm 1=== |
||
I would not try it on the stretch goal, otherwise results as above. |
I would not try it on the stretch goal, otherwise results as above. |
||
< |
<syntaxhighlight lang="python">from itertools import permutations |
||
Line 1,828: | Line 2,478: | ||
if perm != this: |
if perm != this: |
||
return int(''.join(perm)) |
return int(''.join(perm)) |
||
return 0</ |
return 0</syntaxhighlight> |
||
===Python: Generator=== |
===Python: Generator=== |
||
Line 1,834: | Line 2,484: | ||
A variant which defines (in terms of a concatMap over permutations), a generator of '''all''' digit-shuffle successors for a given integer: |
A variant which defines (in terms of a concatMap over permutations), a generator of '''all''' digit-shuffle successors for a given integer: |
||
< |
<syntaxhighlight lang="python">'''Next highest int from digits''' |
||
from itertools import chain, islice, permutations, tee |
from itertools import chain, islice, permutations, tee |
||
Line 1,956: | Line 2,606: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>Taking up to 5 digit-shuffle successors for each: |
<pre>Taking up to 5 digit-shuffle successors for each: |
||
Line 1,968: | Line 2,618: | ||
45072010 -> 5 of 1861: [45072100, 45100027, 45100072, 45100207, 45100270] |
45072010 -> 5 of 1861: [45072100, 45100027, 45100072, 45100207, 45100270] |
||
95322020 -> 1 of 1: [95322200]</pre> |
95322020 -> 1 of 1: [95322200]</pre> |
||
=={{header|Quackery}}== |
|||
<code>nextperm</code> is defined at [[Permutations with some identical elements#Quackery]]. |
|||
<syntaxhighlight lang="Quackery"> [ [] swap |
|||
[ 10 /mod |
|||
rot join swap |
|||
dup 0 = until ] |
|||
drop ] is ->digits ( n --> [ ) |
|||
[ 0 swap |
|||
witheach |
|||
[ swap 10 * + ] ] is digits-> ( [ --> n ) |
|||
[ dup ->digits |
|||
nextperm |
|||
digits-> |
|||
tuck < not if |
|||
[ drop 0 ] ] is task ( n- -> n ) |
|||
' [ 0 9 12 21 12453 738440 45072010 |
|||
95322020 9589776899767587796600 ] |
|||
witheach [ task echo sp ]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>0 0 21 0 12534 740348 45072100 95322200 9589776899767587900667</pre> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Line 1,974: | Line 2,653: | ||
Minimal error trapping. Assumes that the passed number is an integer. Handles positive or negative integers, always returns next largest regardless (if possible). |
Minimal error trapping. Assumes that the passed number is an integer. Handles positive or negative integers, always returns next largest regardless (if possible). |
||
<lang |
<syntaxhighlight lang="raku" line>use Lingua::EN::Numbers; |
||
sub next-greatest-index ($str, &op = &infix:«<» ) { |
sub next-greatest-index ($str, &op = &infix:«<» ) { |
||
Line 2,006: | Line 2,685: | ||
printf "%30s -> %s%s\n", .&comma, .&next-greatest-integer < 0 ?? '' !! ' ', .&next-greatest-integer.&comma for |
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, |
flat 0, (9, 12, 21, 12453, 738440, 45072010, 95322020, 9589776899767587796600, 3345333, |
||
95897768997675877966000000000000000000000000000000000000000000000000000000000000000000).map: { $_, -$_ };</ |
95897768997675877966000000000000000000000000000000000000000000000000000000000000000000).map: { $_, -$_ };</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Next largest integer able to be made from these digits, or zero if no larger exists: |
<pre>Next largest integer able to be made from these digits, or zero if no larger exists: |
||
Line 2,032: | Line 2,711: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight 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*/ |
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?*/ |
if n='' | n="," then n= 0 9 12 21 12453 738440 45072010 95322020 /*use the defaults?*/ |
||
Line 2,056: | Line 2,735: | ||
end /*k*/ |
end /*k*/ |
||
do m=0 for 10; if @.m==0 then iterate; $= $ || copies(m, @.m) |
do m=0 for 10; if @.m==0 then iterate; $= $ || copies(m, @.m) |
||
end /*m*/; return $ /* [↑] build a sorted digit mask.*/</ |
end /*m*/; return $ /* [↑] build a sorted digit mask.*/</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 2,070: | Line 2,749: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
load "stdlib.ring" |
load "stdlib.ring" |
||
Line 2,169: | Line 2,848: | ||
last -= 1 |
last -= 1 |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,182: | Line 2,861: | ||
</pre> |
</pre> |
||
=={{header|RPL}}== |
|||
{{works with|HP|48G}} |
|||
{| class="wikitable" ≪ |
|||
! RPL code |
|||
! Comment |
|||
|- |
|||
| |
|||
≪ '''IF''' DUP SIZE 1 == '''THEN''' DROP 1 GET '''ELSE''' STREAM '''END''' |
|||
≫ '<span style="color:blue">REDUCE</span>' STO |
|||
≪ |
|||
'''IF''' DUP 9 > '''THEN''' |
|||
DUP MANT IP SWAP →STR DUP SIZE 0 → digit num size pos |
|||
≪ { } digit + |
|||
2 size '''FOR''' j |
|||
num j DUP SUB STR→ |
|||
'''IF''' DUP digit > '''THEN''' j 1 - ‘pos’ STO '''END''' |
|||
DUP ‘digit’ STO + |
|||
'''NEXT''' |
|||
'''IF''' pos '''THEN''' |
|||
DUP pos GET ‘digit’ STO |
|||
DUP pos 1 + size SUB |
|||
DUP digit - DUP 0 ≤ 100 * ADD |
|||
≪ MIN ≫ <span style="color:blue">REDUCE</span> digit + POS pos + |
|||
DUP2 GET ROT pos ROT PUT SWAP digit PUT |
|||
DUP ‘pos’ INCR size SUB SORT pos SWAP REPL |
|||
≪ SWAP 10 * + ≫ <span style="color:blue">REDUCE</span> |
|||
'''ELSE''' DROP num STR→ '''END''' |
|||
≫ '''END''' |
|||
≫ '<span style="color:blue">NEXTHI</span>' STO |
|||
| |
|||
<span style="color:blue">REDUCE</span> ''( { list } ≪ func ≫ → func(list) ) '' |
|||
<span style="color:blue">NEXTHI</span> ''( int → next_highest_int ) '' |
|||
if int > 9 then |
|||
initialize variables |
|||
initialize list of digits with digit #1 |
|||
for j = 2 to last digit index |
|||
get digit |
|||
if higher than previous digit, store position |
|||
store digit as previous and append to list |
|||
end loop |
|||
if there is an highest int |
|||
get d1 = first digit to swap |
|||
take the rest of list |
|||
look for d2 = lowest digit being greater than d1 |
|||
swap d1 and d2 |
|||
sort all digits at right of d1 |
|||
turn the list of digits into a number |
|||
else return the initial number |
|||
|} |
|||
{0 9 12 21 12453 738440 45072010 95322020} 1 ≪ <span style="color:blue">NEXTHI</span> ≫ DOLIST |
|||
{{out}} |
|||
<pre> |
|||
1: { 0 9 21 21 12534 740348 45072100 95322200 } |
|||
</pre> |
|||
=={{header|Ruby}}== |
|||
<syntaxhighlight lang="ruby">def next_perm(ar) |
|||
ar = ar.dup |
|||
rev_ar = ar.reverse |
|||
(a, pivot), i = rev_ar.each_cons(2).with_index(1).detect{|(e1, e2),i| e1 > e2} |
|||
return [0] if i.nil? |
|||
suffix = ar[-i..] |
|||
min_dif = suffix.map{|el|el-pivot }.reject{|el|el <= 0}.min |
|||
ri = ar.rindex{|el| el == min_dif + pivot} |
|||
ar[-(i+1)], ar[ri] = ar[ri], ar[-(i+1)] |
|||
ar[-i..] = ar[-i..].reverse |
|||
ar |
|||
end |
|||
tests = [0, 9, 12, 21, 12453, 738440, 45072010, 95322020, 9589776899767587796600] |
|||
tests.each{|t| puts "%25d -> %d" % [t, next_perm(t.to_s.chars.map(&:to_i)).join]} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 0 -> 0 |
|||
9 -> 0 |
|||
12 -> 21 |
|||
21 -> 0 |
|||
12453 -> 12534 |
|||
738440 -> 740348 |
|||
45072010 -> 45072100 |
|||
95322020 -> 95322200 |
|||
9589776899767587796600 -> 9589776899767587900667 |
|||
</pre> |
|||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">fn next_permutation<T: PartialOrd>(array: &mut [T]) -> bool { |
||
let len = array.len(); |
let len = array.len(); |
||
if len < 2 { |
if len < 2 { |
||
Line 2,218: | Line 2,987: | ||
println!("{} -> {}", n, next_highest_int(*n)); |
println!("{} -> {}", n, next_highest_int(*n)); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,234: | Line 3,003: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">func next_from_digits(n, b = 10) { |
||
var a = n.digits(b).flip |
var a = n.digits(b).flip |
||
Line 2,254: | Line 3,023: | ||
) { |
) { |
||
printf("%30s -> %s\n", n, next_from_digits(n)) |
printf("%30s -> %s\n", n, next_from_digits(n)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,276: | Line 3,045: | ||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
{{libheader|Wren-str}} |
{{libheader|Wren-str}} |
||
< |
<syntaxhighlight lang="wren">import "./sort" for Sort, Find |
||
import "/fmt" for Fmt |
import "./fmt" for Fmt |
||
import "/str" for Str |
import "./str" for Str |
||
var permute = Fn.new { |s| |
var permute = Fn.new { |s| |
||
Line 2,383: | Line 3,152: | ||
var nums = ["0", "9", "12", "21", "12453", "738440", "45072010", "95322020", "9589776899767587796600"] |
var nums = ["0", "9", "12", "21", "12453", "738440", "45072010", "95322020", "9589776899767587796600"] |
||
algorithm1.call(nums[0...-1]) // exclude the last one |
algorithm1.call(nums[0...-1]) // exclude the last one |
||
algorithm2.call(nums) // include the last one</ |
algorithm2.call(nums) // include the last one</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,412: | Line 3,181: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl">fcn nextHightest(N){ // N is int, BigInt or string -->String. Algorithm 2 |
||
// ds:=N.split().copy(); // mutable, int |
// ds:=N.split().copy(); // mutable, int |
||
ds:=N.toString().split("").apply("toInt").copy(); // handle "234" or BigInt |
ds:=N.toString().split("").apply("toInt").copy(); // handle "234" or BigInt |
||
Line 2,428: | Line 3,197: | ||
} |
} |
||
"0" |
"0" |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">ns:=T(0, 9, 12, 21, 12453, 738440, 45072010, 95322020); |
||
foreach n in (ns){ println("%,d --> %,d".fmt(n,nextHightest(n))) } |
foreach n in (ns){ println("%,d --> %,d".fmt(n,nextHightest(n))) } |
||
n:="9589776899767587796600"; // or BigInt(n) |
n:="9589776899767587796600"; // or BigInt(n) |
||
println("%s --> %s".fmt(n,nextHightest(n)));</ |
println("%s --> %s".fmt(n,nextHightest(n)));</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 13:56, 3 June 2024
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 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
- 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 smallest digit on the right that is greater than it.
- 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
11l
F closest_more_than(n, lst)
V large = max(lst) + 1
R lst.index(min(lst, key' x -> (I x <= @n {@large} E x)))
F nexthigh(n)
V this = reversed(Array(n.map(digit -> Int(digit))))
V mx = this[0]
L(digit) this[1..]
V i = L.index + 1
I digit < mx
V mx_index = closest_more_than(digit, this[0 .< i + 1])
swap(&this[mx_index], &this[i])
this.sort_range(0 .< i, reverse' 1B)
R reversed(this).map(d -> String(d)).join(‘’)
E I digit > mx
mx = digit
R ‘0’
L(x) [‘0’, ‘9’, ‘12’, ‘21’, ‘12453’, ‘738440’, ‘45072010’, ‘95322020’,
‘9589776899767587796600’]
print(‘#12 -> #12’.format(x, nexthigh(x)))
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667
Ada
This uses a variation of Algorithm 1 that only makes one pass through the permutations, and a variation of Algorithm 2 that simplifies finding the digit to swap with.
-- Next highest integer with same digits
-- J. Carter 2024 June
-- Uses the PragmAda Reusable Components (https://github.com/jrcarter/PragmARC)
with Ada.Text_IO;
with PragmARC.Permutations;
with PragmARC.Sorting.Insertion;
procedure Next_Highest is
package Permutations is new PragmARC.Permutations (Element => Character);
procedure Sort is new PragmARC.Sorting.Insertion (Element => Character, Index => Positive, Sort_Set => String);
subtype Digit is Character range '0' .. '9';
function Valid (S : in String) return Boolean is
(S'First = 1 and S'Length > 0 and (for all C of S => C in Digit) );
function Next_P (Value : in String) return String with
Pre => Valid (Value);
-- Returns the smallest integer > Value that can be produced from Value's decimal digits, using permutations
-- Returns zero if there is no such integer
function Next_S (Value : in String) return String with
Pre => Valid (Value);
-- Returns the smallest integer > Value that can be produced from Value's decimal digits, using the Scan, Sort, Scan, and Swap
-- (SSSS) algorithm
-- Returns zero if there is no such integer
function Next_P (Value : in String) return String is
procedure Check (Image : in Permutations.Sequence; Stop : in out Boolean);
-- Checks if Image represents an integer > Value and smaller than Smallest
-- If so, sets Found to True and Smallest to the represented value
Found : Boolean := False;
Smallest : String := (Value'Range => '9');
procedure Check (Image : in Permutations.Sequence; Stop : in out Boolean) is
Number : constant String := String (Image);
begin -- Check
if Number > Value then
Found := True;
Smallest := (if Number < Smallest then Number else Smallest);
end if;
end Check;
begin -- Next_P
if Value'Length < 2 or (Value'Length = 2 and Value < "12") then
return "0";
end if;
Permutations.Generate (Initial => Permutations.Sequence (Value), Process => Check'Access);
return (if Found then Smallest else "0");
end Next_P;
function Next_S (Value : in String) return String is
Work : String := Value;
Found : Boolean := False;
Lower : Positive;
Higher : Positive;
begin -- Next_S
Scan_Lower : for I in reverse 1 .. Work'Last - 1 loop
if (for some C of Work (I + 1 .. Work'Last) => Work (I) < C) then
Found := True;
Lower := I;
exit Scan_Lower;
end if;
end loop Scan_Lower;
if not Found then
return "0";
end if;
Sort (Set => Work (Lower + 1 .. Work'Last) );
Scan_Higher : for I in Lower + 1 .. Work'Last loop -- The Found test above ensures that this will always assign to Higher
if Work (I) > Work (Lower) then
Higher := I;
exit Scan_Higher;
end if;
end loop Scan_Higher;
Swap : declare
Temp : constant Character := Work (Lower);
begin -- Swap
Work (Lower) := Work (Higher);
Work (Higher) := Temp;
end Swap;
return Work;
end Next_S;
Test_1 : constant String := "0";
Test_2 : constant String := "9";
Test_3 : constant String := "12";
Test_4 : constant String := "21";
Test_5 : constant String := "12453";
Test_6 : constant String := "738440";
Test_7 : constant String := "45072010";
Test_8 : constant String := "95322020";
Stretch : constant String := "9589776899767587796600";
begin -- Next_Highest
Ada.Text_IO.Put_Line (Item => "Using permutations");
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_1'Length => ' ') & Test_1 & ' ' & Next_P (Test_1) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_2'Length => ' ') & Test_2 & ' ' & Next_P (Test_2) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_3'Length => ' ') & Test_3 & ' ' & Next_P (Test_3) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_4'Length => ' ') & Test_4 & ' ' & Next_P (Test_4) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_5'Length => ' ') & Test_5 & ' ' & Next_P (Test_5) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_6'Length => ' ') & Test_6 & ' ' & Next_P (Test_6) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_7'Length => ' ') & Test_7 & ' ' & Next_P (Test_7) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_8'Length => ' ') & Test_8 & ' ' & Next_P (Test_8) );
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line (Item => "Using SSSS");
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_1'Length => ' ') & Test_1 & ' ' & Next_S (Test_1) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_2'Length => ' ') & Test_2 & ' ' & Next_S (Test_2) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_3'Length => ' ') & Test_3 & ' ' & Next_S (Test_3) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_4'Length => ' ') & Test_4 & ' ' & Next_S (Test_4) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_5'Length => ' ') & Test_5 & ' ' & Next_S (Test_5) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_6'Length => ' ') & Test_6 & ' ' & Next_S (Test_6) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_7'Length => ' ') & Test_7 & ' ' & Next_S (Test_7) );
Ada.Text_IO.Put_Line (Item => (1 .. 8 - Test_8'Length => ' ') & Test_8 & ' ' & Next_S (Test_8) );
Ada.Text_IO.New_Line;
Ada.Text_IO.Put_Line (Item => Stretch & ' ' & Next_S (Stretch) );
end Next_Highest;
- Output:
Using permutations 0 0 9 0 12 21 21 0 12453 12534 738440 740348 45072010 45072100 95322020 95322200 Using SSSS 0 0 9 0 12 21 21 0 12453 12534 738440 740348 45072010 45072100 95322020 95322200 9589776899767587796600 9589776899767587900667
ALGOL 68
Should work with any Algol 68 implementation if LONG INT is large to hold the stretch test case.
Implements algorithm 2.
BEGIN # find the next integer > a given integer with the same digits #
OP - = ( CHAR a, b )INT: ABS a - ABS b; # character subtraction #
PROC swap = ( REF STRING s, INT a, b )VOID: # swap chars at a and b in s #
BEGIN CHAR t = s[ a ]; s[ a ] := s[ b ]; s[ b ] := t END;
# returns the next integer greater than v with the same digits as v #
OP NEXT = ( LONG INT v )LONG INT:
BEGIN
LONG INT result := 0;
STRING s := whole( v, 0 );
INT c pos := UPB s - 1;
# find the rightmost digit that has a lower digit to the left #
WHILE IF c pos < LWB s
THEN FALSE
ELSE s[ c pos ] >= s[ c pos + 1 ]
FI
DO
c pos -:=1
OD;
IF c pos >= LWB s THEN
# the digit at c pos is lower than one to its right #
# swap the lower digit with the smallest right digit greater #
# than the lower digit #
CHAR c = s[ c pos ];
INT min pos := c pos + 1;
INT min diff := s[ c pos + 1 ] - c;
FOR m pos FROM c pos + 2 TO UPB s DO
IF s[ m pos ] > c THEN
IF INT this diff = s[ m pos ] - c;
this diff < min diff
THEN
min diff := this diff;
min pos := m pos
FI
FI
OD;
swap( s, min pos, c pos );
# sort the right digits #
FOR u FROM UPB s - 1 BY -1 TO c pos + 1
WHILE BOOL sorted := TRUE;
FOR p FROM c pos + 1 BY 1 TO u DO
IF s[ p ] > s[ p + 1 ] THEN
swap( s, p, p + 1 );
sorted := FALSE
FI
OD;
NOT sorted
DO SKIP OD;
# convert back to an integer #
result := s[ LWB s ] - "0";
FOR i FROM LWB s + 1 TO UPB s DO
result *:= 10 +:= s[ i ] - "0"
OD
FI;
result
END # NEXT # ;
# task test cases #
[]LONG INT tests = ( 0, 9, 12, 21, 12453, 738440, 45072010, 95322020
, 9589776899767587796600
);
FOR i FROM LWB tests TO UPB tests DO
print( ( whole( tests[ i ], -24 ), " -> ", whole( NEXT tests[ i ], 0 ), newline ) )
OD
END
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667
Arturo
canHaveGreater?: function [n][
mydigs: digits n
maxdigs: reverse sort mydigs
return some? 0..dec size mydigs 'i ->
maxdigs\[i] > mydigs\[i]
]
nextHighest: function [n][
if not? canHaveGreater? n -> return n
ndigs: sort digits n
i: n + 1
while [ndigs <> sort digits i]->
i: i + 1
return i
]
loop [0, 9, 12, 21, 12453, 738440, 45072010, 95322020] 'num ->
print [pad (to :string num) 9 "->" nextHighest num]
- Output:
0 -> 0 9 -> 9 12 -> 21 21 -> 21 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200
AutoHotkey
Permutation Version
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
}
Examples:
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)
- Output:
0 0 21 0 12534 740348 45072100 95322200
Scanning Version
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
}
Examples:
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)
- Output:
0 0 21 0 12534 780344 45072100 95322200 9589776899767587900667
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;
}
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667
C#
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Numerics;
using System.Text;
public class NextHighestIntFromDigits
{
public static void Main(string[] args)
{
foreach (var s in new string[] { "0", "9", "12", "21", "12453", "738440", "45072010", "95322020", "9589776899767587796600", "3345333" })
{
Console.WriteLine($"{Format(s)} -> {Format(Next(s))}");
}
TestAll("12345");
TestAll("11122");
}
private static string Format(string s)
{
return BigInteger.Parse(s).ToString("N0", CultureInfo.InvariantCulture);
}
private static void TestAll(string s)
{
Console.WriteLine($"Test all permutations of: {s}");
var sOrig = s;
var sPrev = s;
int count = 1;
// Check permutation order. Each is greater than the last
bool orderOk = true;
var uniqueMap = new Dictionary<string, int>();
uniqueMap[s] = 1;
while ((s = Next(s)) != "0")
{
count++;
if (BigInteger.Parse(s) < BigInteger.Parse(sPrev))
{
orderOk = false;
}
if (uniqueMap.ContainsKey(s))
{
uniqueMap[s]++;
}
else
{
uniqueMap[s] = 1;
}
sPrev = s;
}
Console.WriteLine($" Order: OK = {orderOk}");
// Test last permutation
var reverse = Reverse(sOrig);
Console.WriteLine($" Last permutation: Actual = {sPrev}, Expected = {reverse}, OK = {sPrev == reverse}");
// Check permutations unique
bool unique = true;
foreach (var key in uniqueMap.Keys)
{
if (uniqueMap[key] > 1)
{
unique = false;
}
}
Console.WriteLine($" Permutations unique: OK = {unique}");
// Check expected count.
var charMap = new Dictionary<char, int>();
foreach (var c in sOrig)
{
if (charMap.ContainsKey(c))
{
charMap[c]++;
}
else
{
charMap[c] = 1;
}
}
BigInteger permCount = Factorial(sOrig.Length);
foreach (var c in charMap.Keys)
{
permCount /= Factorial(charMap[c]);
}
Console.WriteLine($" Permutation count: Actual = {count}, Expected = {permCount}, OK = {count == permCount}");
}
private static BigInteger Factorial(int n)
{
BigInteger fact = 1;
for (int num = 2; num <= n; num++)
{
fact *= num;
}
return fact;
}
private static string Next(string s)
{
var 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[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.
int index2 = index;
for (int i = index + 1; i < s.Length; i++)
{
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.Substring(0, index - 1));
}
// Append found, place next
sb.Append(s[index2]);
// Get remaining characters
List<char> chars = new List<char>();
chars.Add(s[index - 1]);
for (int i = index; i < s.Length; i++)
{
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();
foreach (var c in chars)
{
sb.Append(c);
}
return sb.ToString();
}
private static string Reverse(string s)
{
var charArray = s.ToCharArray();
Array.Reverse(charArray);
return new string(charArray);
}
}
- 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
C++
This solution makes use of std::next_permutation, which is essentially the same as Algorithm 2.
#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;
}
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667
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");
}
- 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
Delphi
program Next_highest_int_from_digits;
{$APPTYPE CONSOLE}
uses
System.SysUtils,
System.Generics.Collections;
function StrToBytes(str: AnsiString): TArray<byte>;
begin
SetLength(result, Length(str));
Move(Pointer(str)^, Pointer(result)^, Length(str));
end;
function BytesToStr(bytes: TArray<byte>): AnsiString;
begin
SetLength(Result, Length(bytes));
Move(Pointer(bytes)^, Pointer(Result)^, Length(bytes));
end;
function Commatize(s: string): string;
begin
var le := length(s);
var i := le - 3;
while i >= 1 do
begin
s := s.Substring(0, i) + ',' + s.Substring(i);
inc(i, -3);
end;
Result := s;
end;
function Permute(s: string): TArray<string>;
var
res: TArray<string>;
b: string;
procedure rc(np: Integer);
begin
if np = 1 then
begin
SetLength(res, Length(res) + 1);
res[High(res)] := b;
exit;
end;
var np1 := np - 1;
var pp := length(b) - np1;
rc(np1);
for var i := pp downto 1 do
begin
var tmp := b[i + 1];
b[i + 1] := b[i];
b[i] := tmp;
rc(np1);
end;
var w := b[1];
delete(b, 1, 1);
Insert(w, b, pp + 1);
end;
begin
if s.Length = 0 then
exit;
res := [];
b := s;
rc(length(b));
result := res;
end;
procedure Algorithm1(nums: TArray<string>);
begin
writeln('Algorithm 1');
writeln('-----------');
for var num in nums do
begin
var perms := permute(num);
var le := length(perms);
if le = 0 then
Continue;
TArray.Sort<string>(perms);
var ix := 0;
TArray.BinarySearch<string>(perms, num, ix);
var next := '';
if ix < le - 1 then
for var i := ix + 1 to le - 1 do
if perms[i] > num then
begin
next := perms[i];
Break;
end;
if length(next) > 0 then
writeln(format('%29s -> %s', [Commatize(num), Commatize(next)]))
else
writeln(format('%29s -> 0', [Commatize(num)]));
end;
writeln;
end;
procedure Algorithm2(nums: TArray<string>);
var
ContinueMainFor: boolean;
begin
writeln('Algorithm 2');
writeln('-----------');
for var num in nums do
begin
ContinueMainFor := false;
var le := num.Length;
if le = 0 then
Continue;
var b := StrToBytes(num);
var max := b[le - 1];
var mi := le - 1;
for var i := le - 2 downto 0 do
begin
if b[i] < max then
begin
var min := max - b[i];
for var j := mi + 1 to le - 1 do
begin
var min2 := b[j] - b[i];
if (min2 > 0) and (min2 < min) then
begin
min := min2;
mi := j;
end;
end;
var tmp := b[i];
b[i] := b[mi];
b[mi] := tmp;
var c := copy(b, i + 1, le);
TArray.Sort<byte>(c);
var next: string := BytesToStr(copy(b, 0, i + 1));
next := next + BytesToStr(c);
writeln(format('%29s -> %s', [Commatize(num), Commatize(next)]));
ContinueMainFor := true;
Break;
end
else if b[i] > max then
begin
max := b[i];
mi := i;
end;
end;
if ContinueMainFor then
Continue;
writeln(format('%29s -> 0', [Commatize(num)]));
end;
end;
begin
var nums: TArray<string> := ['0', '9', '12', '21', '12453', '738440',
'45072010', '95322020'];
algorithm1(nums); // exclude the last one
SetLength(nums, Length(nums) + 1);
nums[High(nums)] := '9589776899767587796600';
algorithm2(nums); // include the last one
{$IFNDEF UNIX}
readln; {$ENDIF}
end.
EasyLang
proc reverse i j . dig[] .
while i < j
swap dig[i] dig[j]
i += 1
j -= 1
.
.
proc next_perm . dig[] .
if len dig[] >= 2
for i = 2 to len dig[]
if dig[i] < dig[i - 1]
k = 1
while dig[i] >= dig[k]
k += 1
.
swap dig[i] dig[k]
reverse 1 i - 1 dig[]
return
.
.
.
dig[] = [ ]
.
func next_highest n .
while n > 0
digs[] &= n mod 10
n = n div 10
.
next_perm digs[]
for i = len digs[] downto 1
r = r * 10 + digs[i]
.
return r
.
nums[] = [ 0 9 12 21 12453 738440 45072010 95322020 ]
for n in nums[]
print n & " -> " & next_highest n
.
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.
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
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667
FreeBASIC
algorithm 1
Function factorial(n As Integer) As Uinteger
Return Iif(n = 0, 1, n * factorial(n - 1))
End Function
Sub swap_(s As String, i As Integer, j As Integer)
Dim As String temp = Mid(s, i, 1)
Mid(s, i, 1) = Mid(s, j, 1)
Mid(s, j, 1) = temp
End Sub
Sub permute(s As String, l As Integer, r As Integer, perms() As String)
If l = r Then
Redim Preserve perms(Ubound(perms) + 1)
perms(Ubound(perms)) = s
Else
For i As Uinteger = l To r
swap_(s, l, i)
permute(s, l + 1, r, perms())
swap_(s, l, i) ' backtrack
Next i
End If
End Sub
Sub bubbleSort(arr() As String)
Dim As Integer i, j, n = Ubound(arr)
Dim As String temp
For i = 0 To n - 1
For j = 0 To n - i - 1
If arr(j) > arr(j + 1) Then
temp = arr(j)
arr(j) = arr(j + 1)
arr(j + 1) = temp
End If
Next j
Next i
End Sub
Function nextHigh1(Byref n As String) As String
Dim As String perms()
Dim As Uinteger i, idx
permute(n, 1, Len(n), perms())
bubbleSort perms()
Dim As Uinteger k = Ubound(perms)
For i = 0 To k
If perms(i) = n Then
idx = i
Exit For
End If
Next i
Return Iif(idx < k, perms(idx + 1), "0")
End Function
Dim As String tests1(7) = {"0", "9", "12", "21", "12453", "738440", "45072010", "95322020"}
Dim As Double t0 = Timer
For i As Uinteger = 0 To Ubound(tests1)
Print tests1(i); " => "; nextHigh1(tests1(i))
Next i
Print Chr(10); Timer - t0; "sec."
- Output:
0 => 0 9 => 0 12 => 21 21 => 0 12453 => 12534 738440 => 738440 45072010 => 45072010 95322020 => 95322020 67.04065610002726sec.
algorithm 2
Function sort(s As String) As String
Dim As Uinteger i, j, n = Len(s)
Dim As String temp
For i = 1 To n
For j = i + 1 To n
If Asc(Mid(s, i, 1)) > Asc(Mid(s, j, 1)) Then
temp = Mid(s, i, 1)
Mid(s, i, 1) = Mid(s, j, 1)
Mid(s, j, 1) = temp
End If
Next j
Next i
Return s
End Function
Function rfind(c As String, s As String) As Uinteger
Return Instr(s, c)
End Function
Function nextHigh2(n As String) As String
Dim As Uinteger hi = Asc(Right(n, 1))
Dim As Uinteger i, ni, idx
Dim As String sr
For i = Len(n) - 1 To 1 Step -1
ni = Asc(Mid(n, i, 1))
If ni < hi Then
sr = sort(Mid(n, i))
idx = rfind(Chr(ni), sr) + 1
Mid(n, i, 1) = Mid(sr, idx, 1)
Mid(sr, idx, 1) = ""
Mid(n, i + 1) = sr
Return n
End If
hi = Iif(hi > ni, hi, ni)
Next i
Return "0"
End Function
Dim As String tests2(8) = { "0", "9", "12", "21", "12453", _
"738440", "45072010", "95322020", "9589776899767587796600" }
Dim As Double t1 = Timer
For i As Uinteger = 0 To Ubound(tests2)
Print tests2(i); " => "; nextHigh2(tests2(i))
Next i
Print Chr(10); Timer - t1; "sec."
- Output:
0 => 0 9 => 0 12 => 21 21 => 0 12453 => 12534 738440 => 740344 45072010 => 45072000 95322020 => 95322000 9589776899767587796600 => 9589776899767587900667 0.004686999949626625sec.
Go
This uses a modified version of the recursive code in the [Permutations#Go] task.
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
}
- 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)
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 <>)
- 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)
import Data.List (unfoldr)
------------------- MINIMAL DIGIT-SWAPS ------------------
digitShuffleSuccessors :: Integral b => b -> [b]
digitShuffleSuccessors n =
unDigits <$> unfoldr nexts (go $ reversedDigits n)
where
go = minimalSwap . splitBy (>)
nexts x
| null x = Nothing
| otherwise = Just (((,) <*> go . reverse) x)
minimalSwap :: Ord a => ([a], [a]) -> [a]
minimalSwap ([], x : y : xs) = reverse (y : x : xs)
minimalSwap ([], xs) = []
minimalSwap (_, []) = []
minimalSwap (reversedSuffix, pivot : prefix) =
reverse (h : prefix) <> less <> (pivot : more)
where
(less, h : more) = break (> pivot) reversedSuffix
--------------------------- 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 :: Integral a => [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 <>)
- 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.
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();
}
}
- 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
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');
- Output:
0 => 0 9 => 0 12 => 21 21 => 0 12453 => 12534 738440 => 740348 45072010 => 45072100 95322020 => 95322200 9589776899767587796600 => 9589776899767587900667
jq
# Generate a stream of all the permutations of the input array
def permutations:
# Given an array as input, generate a stream by inserting $x at different positions
def insert($x):
range (0; length + 1) as $pos
| .[0:$pos] + [$x] + .[$pos:];
if length <= 1 then .
else
.[0] as $first
| .[1:] | permutations | insert($first)
end;
def next_highest:
(tostring | explode) as $digits
| ([$digits | permutations] | unique) as $permutations
| ($permutations | bsearch($digits)) as $i
| if $i == (($permutations|length) - 1) then 0
else $permutations[$i+1] | implode
end;
def task:
0,
9,
12,
21,
12453,
738440,
45072010,
95322020;
task | "\(.) => \(next_highest)"
- Output:
0 => 0 9 => 0 12 => 21 21 => 0 12453 => 12534 738440 => 740348 45072010 => 45072100 95322020 => 95322200
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.")
- 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
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()
}
- 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
Lua
Algorithm 2 with a reverse index of digit positions.
unpack = unpack or table.unpack -- <=5.2 vs >=5.3 polyfill
function nexthighestint(n)
local digits, index = {}, {[0]={},{},{},{},{},{},{},{},{},{}}
for d in tostring(n):gmatch("%d") do digits[#digits+1]=tonumber(d) end
for i,d in ipairs(digits) do index[d][#index[d]+1]=i end
local function findswap(i,d)
for D=d+1,9 do
for I=1,#index[D] do
if index[D][I] > i then return index[D][I] end
end
end
end
for i = #digits-1,1,-1 do
local j = findswap(i,digits[i])
if j then
digits[i],digits[j] = digits[j],digits[i]
local sorted = {unpack(digits,i+1)}
table.sort(sorted)
for k=1,#sorted do digits[i+k]=sorted[k] end
return table.concat(digits)
end
end
end
tests = { 0, 9, 12, 21, 12453, 738440, 45072010, 95322020, -- task
"9589776899767587796600", -- stretch
"123456789098765432109876543210", -- stretchier
"1234567890999888777666555444333222111000" -- stretchiest
}
for _,n in ipairs(tests) do
print(n .. " -> " .. (nexthighestint(n) or "(none)"))
end
- Output:
0 -> (none) 9 -> (none) 12 -> 21 21 -> (none) 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667 123456789098765432109876543210 -> 123456789098765432110023456789 1234567890999888777666555444333222111000 -> 1234567891000011222333444555666777888999
Mathematica/Wolfram Language
ClearAll[NextHighestIntFromDigits]
NextHighestIntFromDigits[n_Integer?NonNegative]:=Module[{digs},
digs=IntegerDigits[n];
digs=FromDigits/@Permutations[digs];
digs=Select[digs,GreaterEqualThan[n]];
If[Length[digs]==1,First[digs],RankedMin[digs,2]]
]
NextHighestIntFromDigits/@{0,9,12,21,12453,738440,45072010,95322020}
- Output:
{0, 9, 21, 21, 12534, 740348, 45072100, 95322200}
Nim
Using the scanning algorithm.
import algorithm
type Digit = range[0..9]
func digits(n: Natural): seq[Digit] =
## Return the list of digits of "n" in reverse order.
if n == 0: return @[Digit 0]
var n = n
while n != 0:
result.add n mod 10
n = n div 10
func nextHighest(n: Natural): Natural =
## Find the next highest integer of "n".
## If none is found, "n" is returned.
var d = digits(n) # Warning: in reverse order.
var m = d[0]
for i in 1..d.high:
if d[i] < m:
# Find the digit greater then d[i] and closest to it.
var delta = m - d[i] + 1
var best: int
for j in 0..<i:
let diff = d[j] - d[i]
if diff > 0 and diff < delta:
# Greater and closest.
delta = diff
best = j
# Exchange digits.
swap d[i], d[best]
# Sort previous digits.
d[0..<i] = sorted(d.toOpenArray(0, i - 1), Descending)
break
else:
m = d[i]
# Compute the value from the digits.
for val in reversed(d):
result = 10 * result + val
when isMainModule:
for n in [0, 9, 12, 21, 12453, 738440, 45072010, 95322020]:
echo n, " → ", nextHighest(n)
- Output:
0 → 0 9 → 9 12 → 21 21 → 21 12453 → 12534 738440 → 740348 45072010 → 45072100 95322020 → 95322200
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 $_;
}
- 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
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)
- Output:
0 => 0 9 => 0 12 => 21 21 => 0 12453 => 12534 738440 => 740348 45072010 => 45072100 95322020 => 95322200 "0.2s"
algorithm 2
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)
- 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.
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}")
- 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.
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
Python: Generator
A variant which defines (in terms of a concatMap over permutations), a generator of all digit-shuffle successors for a given integer:
'''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()
- 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]
Quackery
nextperm
is defined at Permutations with some identical elements#Quackery.
[ [] swap
[ 10 /mod
rot join swap
dup 0 = until ]
drop ] is ->digits ( n --> [ )
[ 0 swap
witheach
[ swap 10 * + ] ] is digits-> ( [ --> n )
[ dup ->digits
nextperm
digits->
tuck < not if
[ drop 0 ] ] is task ( n- -> n )
' [ 0 9 12 21 12453 738440 45072010
95322020 9589776899767587796600 ]
witheach [ task echo sp ]
- Output:
0 0 21 0 12534 740348 45072100 95322200 9589776899767587900667
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).
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
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.*/
- 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
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
Output:
0 => 0 9 => 0 12 => 21 21 => 0 12453 => 12534 738440 => 740348 45072010 => 45072100 95322020 => 95322200
RPL
RPL code | Comment |
---|---|
≪ IF DUP SIZE 1 == THEN DROP 1 GET ELSE STREAM END ≫ 'REDUCE' STO ≪ IF DUP 9 > THEN DUP MANT IP SWAP →STR DUP SIZE 0 → digit num size pos ≪ { } digit + 2 size FOR j num j DUP SUB STR→ IF DUP digit > THEN j 1 - ‘pos’ STO END DUP ‘digit’ STO + NEXT IF pos THEN DUP pos GET ‘digit’ STO DUP pos 1 + size SUB DUP digit - DUP 0 ≤ 100 * ADD ≪ MIN ≫ REDUCE digit + POS pos + DUP2 GET ROT pos ROT PUT SWAP digit PUT DUP ‘pos’ INCR size SUB SORT pos SWAP REPL ≪ SWAP 10 * + ≫ REDUCE ELSE DROP num STR→ END ≫ END ≫ 'NEXTHI' STO |
REDUCE ( { list } ≪ func ≫ → func(list) ) NEXTHI ( int → next_highest_int ) if int > 9 then initialize variables initialize list of digits with digit #1 for j = 2 to last digit index get digit if higher than previous digit, store position store digit as previous and append to list end loop if there is an highest int get d1 = first digit to swap take the rest of list look for d2 = lowest digit being greater than d1 swap d1 and d2 sort all digits at right of d1 turn the list of digits into a number else return the initial number |
{0 9 12 21 12453 738440 45072010 95322020} 1 ≪ NEXTHI ≫ DOLIST
- Output:
1: { 0 9 21 21 12534 740348 45072100 95322200 }
Ruby
def next_perm(ar)
ar = ar.dup
rev_ar = ar.reverse
(a, pivot), i = rev_ar.each_cons(2).with_index(1).detect{|(e1, e2),i| e1 > e2}
return [0] if i.nil?
suffix = ar[-i..]
min_dif = suffix.map{|el|el-pivot }.reject{|el|el <= 0}.min
ri = ar.rindex{|el| el == min_dif + pivot}
ar[-(i+1)], ar[ri] = ar[ri], ar[-(i+1)]
ar[-i..] = ar[-i..].reverse
ar
end
tests = [0, 9, 12, 21, 12453, 738440, 45072010, 95322020, 9589776899767587796600]
tests.each{|t| puts "%25d -> %d" % [t, next_perm(t.to_s.chars.map(&:to_i)).join]}
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667
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));
}
}
- Output:
0 -> 0 9 -> 0 12 -> 21 21 -> 0 12453 -> 12534 738440 -> 740348 45072010 -> 45072100 95322020 -> 95322200 9589776899767587796600 -> 9589776899767587900667
Sidef
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))
}
- 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
Wren
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
- 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
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"
}
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)));
- 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
- Programming Tasks
- Solutions by Programming Task
- 11l
- Ada
- ALGOL 68
- Arturo
- AutoHotkey
- C
- C sharp
- C++
- GMP
- D
- Delphi
- System.SysUtils
- System.Generics.Collections
- EasyLang
- Factor
- FreeBASIC
- Go
- Haskell
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- Lua
- Mathematica
- Wolfram Language
- Nim
- Perl
- Phix
- Python
- Quackery
- Raku
- REXX
- Ring
- RPL
- Ruby
- Rust
- Sidef
- Wren
- Wren-sort
- Wren-fmt
- Wren-str
- Zkl