Largest int from concatenated ints: Difference between revisions
→{{header|Picat}}
(R language) |
|||
Line 1,671:
<pre>998764543431
6054854654</pre>
=={{header|Picat}}==
On the simpler cases, four methods are tested: 2 using permutations and 2 with different sorting methods.
<lang Picat>import util.
go =>
Ls = [[1, 34, 3, 98, 9, 76, 45, 4],
[54, 546, 548, 60],
[97, 9, 13, 979],
[9, 1, 95, 17, 5]
],
foreach(L in Ls)
test(L)
end,
nl.
% Test all implementations
test(L) =>
println(l=L),
maxof_inc(s_perm1(L,Num1), Num1),
println(s_perm1=Num1),
s_perm2(L,Num2),
println(s_perm2=Num2),
s_sort_conc(L,Num3),
println(s_sort_conc=Num3),
s_extend(L,Num4),
println(s_extent=Num4),
nl.
% Using permutation/2
s_perm1(L, Num) =>
permutation(L,P),
Num = [I.to_string() : I in P].flatten().to_integer().
% Using permutations/1
s_perm2(L, Num) =>
Perms = permutations(L),
Num = max([ [I.to_string() : I in P].flatten().to_integer() : P in Perms]).
% Sort on concatenated numbers N1N2 <-> N2N1
s_sort_conc(L,Num) =>
Num = [to_string(I) : I in qsort(L,f3)].join('').to_integer().
% sort function for s_sort_conc/2
f3(N1,N2) =>
N1S = N1.to_string(),
N2S = N2.to_string(),
(N1S ++ N2S).to_integer() >= (N2S ++ N1S).to_integer().
% extend each element to the largest length
s_extend(L,Num) =>
LS = [I.to_string() : I in L],
MaxLen = 2*max([I.length : I in LS]),
L2 = [],
foreach(I in LS)
I2 = I,
% extend to a larger length
while(I2.length < MaxLen)
I2 := I2 ++ I
end,
% keep info of the original number
L2 := L2 ++ [[I2,I]]
end,
Num = [I[2] : I in qsort(L2,f4)].join('').to_integer().
% sort function for s_extend/2
f4(N1,N2) => N1[1].to_integer() >= N2[1].to_integer().
% qsort(List, SortFunction)
% returns a sorted list according to the sort function SortFunction.
qsort([],_F) = [].
qsort([H|T],F) = qsort([E : E in T, call(F,E,H)], F)
++ [H] ++
qsort([E : E in T, not call(F,E,H)],F).</lang>
Output:
<pre>l = [1,34,3,98,9,76,45,4]
s_perm1 = 998764543431
s_perm2 = 998764543431
s_sort_conc = 998764543431
s_extend = 998764543431
l = [54,546,548,60]
s_perm1 = 6054854654
s_perm2 = 6054854654
s_sort_conc = 6054854654
s_extend = 6054854654
l = [97,9,13,979]
s_perm1 = 99799713
s_perm2 = 99799713
s_sort_conc = 99799713
s_extend = 99799713
l = [9,1,95,17,5]
s_perm1 = 9955171
s_perm2 = 9955171
s_sort_conc = 9955171
s_extend = 9955171</pre>
Test a larger instance: 2000 random numbers between 1 and 100; about 5800 digits. The two permutation variants (s_perm1 and s_perm2) takes too long on larger N, say N > 9.
<lang Picat>go2 =>
garbage_collect(100_000_000),
_ = random2(),
N = 2000,
println(nums=N),
L = [random(1,1000) : _ in 1..N],
S = join([I.to_string : I in L],''),
println(str_len=S.len),
nl,
println("s_sort_conc:"),
time(s_sort_conc(L,_Num3)),
println("s_extend:"),
time(s_extend(L,_Num4)),
nl.</lang>
Sample run:
<pre>nums = 2000
str_len = 5805
s_sort_conc:
CPU time 0.54 seconds.
s_extend:
CPU time 0.526 seconds.</pre>
=={{header|PicoLisp}}==
| |||