Next highest int from digits: Difference between revisions
Added FreeBASIC
(→{{header|Ruby}}: Add Ruby) |
(Added FreeBASIC) |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 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 763 ⟶ 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 791 ⟶ 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,513 ⟶ 2,890:
{{libheader|Wren-fmt}}
{{libheader|Wren-str}}
<syntaxhighlight lang="
import "./fmt" for Fmt
import "./str" for Str
var permute = Fn.new { |s|
| |||