Next highest int from digits: Difference between revisions
Content added Content deleted
Line 284: | Line 284: | ||
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|Julia}}== |
|||
<lang julia>using Combinatorics, BenchmarkTools |
|||
asint(dig) = foldl((i, j) -> 10i + Int128(j), dig) |
|||
""" |
|||
Algorithm 1(A) |
|||
Generate all the permutations of the digits and sort into numeric order. |
|||
Find the number in the list. |
|||
Return the next highest number from the list. |
|||
""" |
|||
function nexthighest_1A(N) |
|||
n = Int128(abs(N)) |
|||
dig = digits(n) |
|||
perms = unique(sort([asint(arr) for arr in permutations(digits(n))])) |
|||
length(perms) < 2 && return 0 |
|||
((N > 0 && perms[end] == n) || (N < 0 && perms[1] == n)) && return 0 |
|||
pos = findfirst(x -> x == n, perms) |
|||
ret = N > 0 ? perms[pos + 1] : -perms[pos - 1] |
|||
return ret == N ? 0 : ret |
|||
end |
|||
""" |
|||
Algorithm 1(B) |
|||
Iterate through the permutations of the digits of a number and get the permutation that |
|||
represents the integer having a minimum distance above the given number. |
|||
Return the number plus the minimum distance. Does not store all the permutations. |
|||
This saves memory versus algorithm 1A, but we still go through all permutations (slow). |
|||
""" |
|||
function nexthighest_1B(N) |
|||
n = Int128(abs(N)) |
|||
dig = reverse(digits(n)) |
|||
length(dig) < 2 && return 0 |
|||
mindelta = n |
|||
for perm in permutations(dig) |
|||
if (perm[1] != 0) && ((N > 0 && perm > dig) || (N < 0 && perm < dig)) |
|||
delta = abs(asint(perm) - n) |
|||
if delta < mindelta |
|||
mindelta = delta |
|||
end |
|||
end |
|||
end |
|||
return mindelta < n ? N + mindelta : 0 |
|||
end |
|||
""" |
|||
Algorithm 2 |
|||
Scan right-to-left through the digits of the number until you find a digit with a larger digit somewhere to the right of it. |
|||
Exchange that digit with the digit on the right that is both more than it, and closest to it. |
|||
Order the digits to the right of this position, after the swap; lowest-to-highest, left-to-right. |
|||
Very fast, as it does not need to run through all the permutations of digits. |
|||
""" |
|||
function nexthighest_2(N) |
|||
n = Int128(abs(N)) |
|||
dig, ret = digits(n), N |
|||
length(dig) < 2 && return 0 |
|||
for (i, d) in enumerate(dig) |
|||
if N > 0 && i > 1 |
|||
rdig = dig[1:i-1] |
|||
ltdig = filter(x -> x > d, rdig) |
|||
if length(ltdig) > 0 |
|||
j = findfirst(x -> x > d, rdig) |
|||
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] |
|||
ltdig = filter(x -> x < d, rdig) |
|||
if length(ltdig) > 0 |
|||
j = findfirst(x -> x < d, rdig) |
|||
dig[i], dig[j] = dig[j], dig[i] |
|||
arr = (i == 2) ? dig : [sort(dig[1:i-1]); dig[i:end]] |
|||
ret = -asint(reverse(arr)) |
|||
break |
|||
end |
|||
end |
|||
end |
|||
return ret == N ? 0 : ret |
|||
end |
|||
println(" N 1A 1B 2\n", "="^98) |
|||
for n in [0, 9, 12, 21, -453, -8888, 12453, 738440, 45072010, 95322020, -592491602, 9589776899767587796600] |
|||
println(rpad(n, 25), abs(n) > typemax(Int) ? " "^50 : rpad(nexthighest_1A(n), 25) * |
|||
rpad(nexthighest_1B(n), 25), nexthighest_2(n)) |
|||
end |
|||
const n = 7384440 |
|||
@btime nexthighest_1A(n) |
|||
println(" for method 1A and n $n.") |
|||
@btime nexthighest_1B(n) |
|||
println(" for method 1B and n $n.") |
|||
@btime nexthighest_2(n) |
|||
println(" for method 2 and n $n.") |
|||
</lang>{{out}} |
|||
<pre> |
|||
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.015 ms (40364 allocations: 2.43 MiB) |
|||
for method 1A and n 7384440. |
|||
1.234 ms (28804 allocations: 1.92 MiB) |
|||
for method 1B and n 7384440. |
|||
1.440 μs (19 allocations: 1.89 KiB) |
|||
for method 2 and n 7384440. |
|||
</pre> |
|||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |