Next highest int from digits: Difference between revisions
Added FreeBASIC
(Added Quackery.) |
(Added FreeBASIC) |
||
| (8 intermediate revisions by 7 users not shown) | |||
Line 102:
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}}==
Line 274 ⟶ 392:
9589776899767587796600 -> 9589776899767587900667
</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++}}==
Line 645 ⟶ 955:
readln; {$ENDIF}
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}}==
Line 673 ⟶ 1,027:
9589776899767587796600 -> 9589776899767587900667
</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}}==
Line 2,211 ⟶ 2,706:
</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}}==
<syntaxhighlight lang="rust">fn next_permutation<T: PartialOrd>(array: &mut [T]) -> bool {
Line 2,305 ⟶ 2,890:
{{libheader|Wren-fmt}}
{{libheader|Wren-str}}
<syntaxhighlight lang="
import "./fmt" for Fmt
import "./str" for Str
var permute = Fn.new { |s|
| |||