Largest int from concatenated ints: Difference between revisions

{{trans|Python}}

V maxlen = String(max(x)).len

R sorted((x.map(v -> String(v))), key' i -> i * (@maxlen * 2 I/ i.len), reverse' 1B).join(‘’)

L(numbers) [[212, 21221], [1, 34, 3, 98, 9, 76, 45, 4], [54, 546, 548, 60]]

{{out}}

The algorithmic idea is to apply a twisted comparison function:

This function converts the parameters Left and Right to strings and returns True if (Left before Right)

exceeds (Right before Left). It needs Ada 2012 -- the code for older versions of Ada would be more verbose.

The rest is straightforward: Run your favourite sorting subprogram that allows to use the function "Order" instead of standard comparison operators ("<" or ">" or so) and print the results:

procedure Largest_Int_From_List is

Print_Sorted((1, 34, 3, 98, 9, 76, 45, 4));

Print_Sorted((54, 546, 548, 60));

=={{header|Aime}}==

{

index x;

largest(54, 546, 548, 60);

0;

works for input up to 999999999.

{{Out}}

=={{header|ALGOL 68}}==

Using method 2 - first sorting into first digit order and then comparing concatenated pairs.

# returns the integer value of s #

OP TOINT = ( STRING s)INT:

print( ( newline ) )

{{out}}

<pre>

=={{header|Arturo}}==

max map permutate arr 's [

to :integer join map s => [to :string]

loop [[1 34 3 98 9 76 45 4] [54 546 548 60]] 'a ->

=={{header|AutoHotkey}}==

StringReplace, var, A_LoopField,%A_Space%,, all

Sort, var, D`, fConcSort

m := a . b , n := b . a

return m < n ? 1 : m > n ? -1 : 0

(

1, 34, 3, 98, 9, 76, 45, 4

)

loop, parse, d, `n

{{out}}

<pre>998764543431

=={{header|AWK}}==

{{works with|gawk|4.0}}

function cmp(i1, v1, i2, v2, u1, u2) {

u1 = v1""v2;

print largest_int_from_concatenated_ints(X)

}

{{out}}

<pre>998764543431

=={{header|BBC BASIC}}==

Nums%()=1,34,3,98,9,76,45,4

PRINT FNlargestint(8)

l$+=STR$Nums%(i%)

NEXT

{{out}}

<pre>998764543431

=={{header|Bracmat}}==

= A Z F C

. !arg:#

& out$(str$(maxnum$(1 34 3 98 9 76 45 4)))

& out$(str$(maxnum$(54 546 548 60)))

{{out}}

<pre>998764543431

=={{header|C}}==

#include <stdlib.h>

#include <string.h>

return 0;

{{out}}

=={{header|C sharp|C#}}==

using System.Collections.Generic;

using System.Linq;

}

}

{{out}}

=={{header|C++}}==

#include <sstream>

#include <algorithm>

<< " !\n" ;

return 0 ;

{{out}}

{{trans|Kotlin}}

{{works with|Ceylon|1.3.3}}

function comparator(Integer x, Integer y) {

value test2 = {54, 546, 548, 60};

print(biggestConcatenation(test2));

=={{header|Clojure}}==

(read-string

(apply str

coll))))

{{out}}

=== Sort by two-by-two comparison of largest concatenated result ===

(defun int-concat (ints)

(read-from-string (format nil "~{~a~}" ints)))

(defun make-largest-int (ints)

(int-concat (sort ints #'by-biggest-result)))

{{out}}

=== Variation around the sort with padded most significant digit ===

;; Sort criteria is by most significant digit with least digits used as a tie

;; breaker

#'largest-msd-with-less-digits)))

{{out}}

=={{header|D}}==

The three algorithms. Uses the second module from the Permutations Task.

auto maxCat1(in int[] arr) pure @safe {

const lists = [[1, 34, 3, 98, 9, 76, 45, 4], [54, 546, 548, 60]];

[&maxCat1, &maxCat2, &maxCat3].map!(cat => lists.map!cat).writeln;

{{out}}

<pre>[["998764543431", "6054854654"], ["998764543431", "6054854654"], ["998764543431", "6054854654"]]</pre>

=={{header|Elixir}}==

def largest_int(list) do

sorted = Enum.sort(list, fn x,y -> "#{x}#{y}" >= "#{y}#{x}" end)

IO.inspect RC.largest_int [1, 34, 3, 98, 9, 76, 45, 4]

{{out}}

=={{header|Erlang}}==

-module( largest_int_from_concatenated ).

task() ->

[io:fwrite("Largest ~p from ~p~n", [ints(X), X]) || X <- [[1, 34, 3, 98, 9, 76, 45, 4], [54, 546, 548, 60]]].

{{out}}

<pre>

=={{header|F_Sharp|F#}}==

// Form largest integer which is a permutation from a list of integers. Nigel Galloway: March 21st., 2018

let fN g = List.map (string) g |> List.sortWith(fun n g->if n+g<g+n then 1 else -1) |> System.String.Concat

{{out}}

<pre>

=={{header|Factor}}==

Using algorithm 3:

IN: rosetta-code.largest-int

reverse concat print ;

{{out}}

<pre>

Or alternatively, a translation of F#.

{{trans|F#}}

: fn ( seq -- str )

{{out}}

<pre>

The sorting of the text array was to be by the notorious BubbleSort, taking advantage of the fact that each pass delivers the maximum value of the unsorted portion to its final position: the output could thereby be produced as the sort worked. Rather than mess about with early termination (no element being swapped) or attention to the bounds within which swapping took place, attention concentrated upon the comparison. Because of the left-alignment of the texts, a simple comparison seemed sufficient until I thought of unequal text lengths and then the following example. Suppose there are two numbers, 5, and one of 54, 55, or 56 as the other. Via normal comparisons, the 5 would always be first (because short texts are considered expanded with trailing spaces when compared against longer texts, and a space precedes every digit) however the biggest ordering is 5 54 for the first case but 56 5 for the last. This possibility is not exemplified in the specified trial sets. So, a more complex comparison is required. One could of course write a suitable function and consider the issue there but instead the comparison forms the compound text in the same manner as the result will be, in the two ways AB and BA, and looks to see which yields the bigger sequence. This need only be done for unequal length text pairs.

INTEGER A,B,T

T = B

END DO !Thus, the numbers are aligned left in the text field.

CALL BIGUP(T1,10)

Output: the Fortran compiler ignores spaces when reading fortran source, so, hard-core fortranners should have no difficulty doing likewise for the output...

<pre>

=={{header|FreeBASIC}}==

function catint( a as string, b as string ) as uinteger

sort_and_print(set1())

{{out}}

<pre>998764543431

=={{header|Frink}}==

f = {|p| parseInt[join["",p]] }

for s = a

{{out}}

<pre>

=={{header|Gambas}}==

'''[https://gambas-playground.proko.eu/?gist=4169e7641f29ff0ae1dd202b459e60ce Click this link to run this code]'''

Public Sub Main()

Print Val(sList.Join("")) 'Join all items in sList together and print

Output:

<pre>

=={{header|Go}}==

// then sort as strings.

package main

fmt.Println(li(1, 34, 3, 98, 9, 76, 45, 4))

fmt.Println(li(54, 546, 548, 60))

{{out}}

<pre>

=={{header|Groovy}}==

Testing:

=={{header|Haskell}}==

===Compare repeated string method===

import Data.Ord (comparing)

in sortBy (flip $ comparing pad) xs

{{out}}

Since repeating numerical string "1234" is the same as taking all the digits of 1234/9999 after the decimal point, the following does essentially the same as above:

import Data.Ord (comparing)

import Data.Ratio ((%))

map (\a->(a, head $ dropWhile (<a) nines))

===Sort on comparison of concatenated ints method===

main = print (map maxcat [[1,34,3,98,9,76,45,4], [54,546,548,60]] :: [Integer])

where sorted = sortBy (\a b -> compare (b++a) (a++b))

;Output as above.

===Try all permutations method===

main :: IO ()

(maxcat <$> [[1, 34, 3, 98, 9, 76, 45, 4], [54, 546, 548, 60]] :: [Integer])

where

;Output as above.

lifting.

procedure main(a)

procedure cmp(a,b)

return (a||b) > (b||a)

Sample runs:

Here we use the "pad the integers to the same size by repeating the digits then sort using these repeated integers as a sort key" approach:

'''Solution:'''

'''Usage:'''

=={{header|Java}}==

This example sets up a comparator to order the numbers using <code>Collections.sort</code> as described in method #3 (padding and reverse sorting).

It was also necessary to make a join method to meet the output requirements.

public class IntConcat {

System.out.println(join(ints2));

}

{{works with|Java|1.8+}}

import java.util.stream.Collectors;

import java.util.stream.Stream;

);

}

{{out}}

<pre>998764543431

===ES5===

'use strict';

})();

{{Out}}

===ES6===

// test & output

[1, 34, 3, 98, 9, 76, 45, 4],

[54, 546, 548, 60]

=={{header|jq}}==

==== Padding ====

''For jq versions greater than 1.4, it may be necessary to change "sort_by" to "sort".''

def pad(n): . + (n - length) * .[length-1:];

([1, 34, 3, 98, 9, 76, 45, 4],

[54, 546, 548, 60]) | largest_int

{{Out}}

$ /usr/local/bin/jq -n -M -r -f Largest_int_from_concatenated_ints.jq

====Custom Sort====

The following uses [[Sort_using_a_custom_comparator#jq| quicksort/1]]:

map(tostring)

| quicksort( .[0] + .[1] < .[1] + .[0] )

=={{header|Julia}}==

Perhaps algorithm 3 is more efficient, but algorithm 2 is decent and very easy to implement in Julia. So this solution uses algorithm 2.

b = sort(string.(arr); lt=(x, y) -> x * y < y * x, rev=true) |> join

return try parse(Int, b) catch parse(BigInt, b) end

for arr in tests

println("Max concatenating in $arr:\n -> ", maxconcat(arr))

{{out}}

=={{header|Kotlin}}==

{{trans|C#}}

fun main(args: Array<String>) {

println("%s -> %s".format(array.contentToString(), findLargestSequence(array)))

}

{{Out}}

<pre>

{{trans|Python}}

table.sort(numbers,function(x,y) return (x..y) > (y..x) end)

return numbers

table.concat(numbers,","),table.concat(icsort(numbers))

))

{{out}}

<pre>Numbers: {1,34,3,98,9,76,45,4}

=={{header|Mathematica}}/{{header|Wolfram Language}}==

sortedlist = Sort[list, Order[ToString[#1] <> ToString[#2], ToString[#2] <> ToString[#1]] < 0 &];

Map[ToString, sortedlist] // StringJoin // FromDigits

(* testing with two examples *)

makeLargestInt[{1, 34, 3, 98, 9, 76, 45, 4}]

{{out}}

<pre>998764543431

=={{header|min}}==

{{works with|min|0.19.6}}

('string map (over over swap s+ 's+ dip <) sort "" join int) :fn

(1 34 3 98 9 76 45 4) fn puts!

{{out}}

<pre>

=={{header|NetRexx}}==

options replace format comments java crossref symbols nobinary

end il

return

{{out}}

<pre>

=={{header|Nim}}==

proc maxNum(x: seq[int]): string =

echo maxNum(@[1, 34, 3, 98, 9, 76, 45, 4])

{{out}}

=={{header|OCaml}}==

;testing

=={{header|Oforth}}==

{{out}}

Sorts then joins. Most of the noise comes from converting a vector of integers into a concatenated integer: <code>eval(concat(apply(n->Str(n),v)))</code>. Note that the short form <code>eval(concat(apply(Str,v)))</code> is not valid here because <code>Str</code> is variadic.

large([1, 34, 3, 98, 9, 76, 45, 4])

{{out}}

<pre>%1 = 998764543431

tested with freepascal.Used a more extreme example 3.

===algorithm 3===

base = 10;

MaxDigitCnt = 11;

InsertData(tmpData[i],source3[i]);

HighestInt(tmpData);

{{out}}

<pre>998764543431

http://rosettacode.org/wiki/Largest_int_from_concatenated_ints#Compare_repeated_string_method

base = 10;

MaxDigitCnt = 11;

InsertData(tmpData[i],source3[i]);

HighestInt(tmpData);

{{out}}

<pre>9987645434310

=={{header|Perl}}==

join '', sort { "$b$a" cmp "$a$b" } @_

}

print maxnum(1, 34, 3, 98, 9, 76, 45, 4), "\n";

{{out}}

<pre>998764543431

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">catcmp</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">method2</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">34</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">98</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">76</span><span style="color: #0000FF;">,</span><span style="color: #000000;">45</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">})</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">method2</span><span style="color: #0000FF;">({</span><span style="color: #000000;">54</span><span style="color: #0000FF;">,</span><span style="color: #000000;">546</span><span style="color: #0000FF;">,</span><span style="color: #000000;">548</span><span style="color: #0000FF;">,</span><span style="color: #000000;">60</span><span style="color: #0000FF;">})</span>

{{out}}

<pre>

=={{header|PHP}}==

usort($nums, function ($x, $y) { return strcmp("$y$x", "$x$y"); });

return implode('', $nums);

echo maxnum(array(1, 34, 3, 98, 9, 76, 45, 4)), "\n";

{{out}}

<pre>998764543431

===permutation/2===

permutation(L,P),

===Using permutations/1===

Perms = permutations(L),

===Sort on concatenated numbers===

Num = [to_string(I) : I in qsort(L,f3)].join('').to_integer().

qsort([H|T],F) = qsort([E : E in T, call(F,E,H)], F)

++ [H] ++

===Extend each element to the largest length===

LS = [I.to_string() : I in L],

MaxLen = 2*max([I.length : I in LS]),

% sort function for s_extend/2

===Test===

go =>

s_extend(L,Num4),

println(s_extent=Num4),

{{out}}

===Testing larger instance===

Test a larger instance: 2000 random numbers between 1 and 100; about 5800 digits. The two permutation variants (<code>s_perm1</code> and <code>s_perm2</code>) takes too long on larger N, say N > 9.

garbage_collect(100_000_000),

_ = random2(),

time(s_extend(L,_Num4)),

{{out}}

unique lists (as the comparison of identical numbers would not terminate), so a

better solution might involve additional checks.

===Algorithm 1===

===Algorithm 2===

(prinl

(sort L

(>

(format (pack A B))

===Algorithm 3===

(prinl

(flip

{{out}} in all three cases:

<pre>998764543431

=={{header|PL/I}}==

/* Largest catenation of integers 16 October 2013 */

/* Sort using method 2, comparing pairs of adjacent integers. */

end largest_integer;

end Largest;

<pre>

54 546 548 60

{{works with|PowerShell|2}}

Using algorithm 3

{

# Get the length of the largest integer

return $Integer

Get-LargestConcatenation 54, 546, 548, 60

{{out}}

<pre>998764543431

Works with SWI-Prolog 6.5.3.

===All permutations method===

maplist(name, In, LC),

aggregate(max(V), get_int(LC, V), Out).

append(P, LV),

name(V, LV).

{{out}}

<pre> ?- largest_int_v1([1, 34, 3, 98, 9, 76, 45, 4], Out).

===Method 2===

maplist(name, In, LC),

predsort(my_sort,LC, LCS),

my_sort(R, [H1, H1 | T], [H1]) :-

my_sort(R, [H1 | T], [H1]) .

{{out}}

This also shows one of the few times where cmp= is better than key= on sorted()

cmp # Python 2 OK or NameError in Python 3

def maxnum(x):

for numbers in [(1, 34, 3, 98, 9, 76, 45, 4), (54, 546, 548, 60)]:

{{out}}

===Python: Compare repeated string method===

maxlen = len(str(max(x)))

return ''.join(sorted((str(v) for v in x), reverse=True,

for numbers in [(212, 21221), (1, 34, 3, 98, 9, 76, 45, 4), (54, 546, 548, 60)]:

{{out}}

{{works with|Python|2.6+}}

from math import log10

for numbers in [(1, 34, 3, 98, 9, 76, 45, 4), (54, 546, 548, 60)]:

;Output as first Python example, above.

===Python: Try all permutations method===

def maxnum(x):

return max(int(''.join(n) for n in permutations(str(i) for i in x)))

for numbers in [(1, 34, 3, 98, 9, 76, 45, 4), (54, 546, 548, 60)]:

;Output as above.

===With a string of space separated sequences of digits===

[ 2dup swap join

dip join $< ]

$ '1 34 3 98 9 76 45 4' nest$ largest-int echo$ cr

{{out}}

<pre>

===With a nest of numbers===

[ 2dup conc unrot swap conc < ] is conc> ( n n --> b )

[ 54 546 548 60 ] ]

{{out}}

=={{header|R}}==

#recursive function for computing all permutations

Largest_int_from_concat_ints(c(1, 34, 3, 98, 9, 76, 45, 4))

Largest_int_from_concat_ints(c(93, 4, 89, 21, 73))

{{out}}

=={{header|Racket}}==

#lang racket

(define (largest-int ns)

(map largest-int '((1 34 3 98 9 76 45 4) (54 546 548 60)))

;; -> '(998764543431 6054854654)

=={{header|Raku}}==

(formerly Perl 6)

[~] @x.sort: -> $a, $b { $b ~ $a leg $a ~ $b }

}

say maxnum <1 34 3 98 9 76 45 4>;

{{out}}

<pre>998764543431

6054854654</pre>

=={{header|Red}}==

foreach seq [[1 34 3 98 9 76 45 4] [54 546 548 60]] [

print rejoin sort/compare seq function [a b] [ (rejoin [a b]) > rejoin [b a] ]

]

{{out}}

<pre>

The absolute value is used for negative numbers. &nbsp; No sorting of the numbers is required for the 1^st two examples.

===simple integers===

@.=.; @.1 = 1 34 3 98 9 76 45 4 /*the 1st integer list to be used. */

@.2 = 54 546 548 60 /* " 2nd " " " " " */

/*──────────────────────────────────────────────────────────────────────────────────────*/

norm: arg i; #= word(z, i); er= '***error***'; if left(#, 1)=="-" then #= substr(#, 2)

{{out|output|text=&nbsp; when using the default (internal) integer lists:}}

<pre>

This REXX version can handle any sized integer &nbsp; (most REXXes can handle up to around eight million decimal

<br>digits, &nbsp; but displaying the result would be problematic for results wider than the display area).

@.=.; @.1 = 1 34 3 98 9 76 45 4 /*the 1st integer list to be used. */

@.2 = 54 546 548 60 /* " 2nd " " " " " */

end

if datatype(#, 'W') then return # / 1

{{out|output|text=&nbsp; when using the default (internal) integer lists:}}

===Alternate Version===

Inspired by the previous versions.

l.=''; l.1 = '1 34 3 98 9 76 45 4' /*the 1st integer list to be used. */

l.2 = '54 546 548 60' /* " 2nd " " " " " */

result=result||big /*append " " " ---? $. */

end /*while z*/ /* [?] process all integers in a list.*/

{{out}}

<pre>1 34 3 98 9 76 45 4 -> 998764543431

===Version 4===

{{trans|NetRexx}}

l.=''; l.1 = '1 34 3 98 9 76 45 4' /*the 1st integer list to be used. */

l.2 = '54 546 548 60' /* " 2nd " " " " " */

list=list w.ww

End

{{out}}

<pre>1 34 3 98 9 76 45 4 -> 998764543431

=={{header|Ring}}==

nums=[1,34,3,98,9,76,45,4]

see largestInt(8) + nl

next

return l

Output:

<pre>

{{trans|Tcl}}

nums.sort { |x, y| "#{y}#{x}" <=> "#{x}#{y}" }

end

p c # prints nicer in Ruby 1.8

puts icsort(c).join

{{out}}

===Compare repeated string method===

maxlen = nums.max.to_s.length

nums.map{ |x| x.to_s }.sort_by { |x| x * (maxlen * 2 / x.length) }.reverse

p c # prints nicer in Ruby 1.8

puts icsort(c).join

;Output as above.

def icsort nums

p c # prints nicer in Ruby 1.8

puts icsort(c).join

;Output as above.

=={{header|Run BASIC}}==

a2$ = "54,546,548,60"

maxNum$ = maxNum$ ; a$(j)

next j

{{out}}

<pre>Max Num 1, 34, 3, 98, 9, 76, 45, 4 = 998764543431

=={{header|Rust}}==

a.sort_by(|x, y| {

let xy = format!("{}{}", x, y);

maxcat(&mut [1, 34, 3, 98, 9, 76, 45, 4]);

maxcat(&mut [54, 546, 548, 60]);

{{out}}

<pre>998764543431

=={{header|S-lang}}==

{

a = string(a);

print("max of series 1 is " + maxcat([1, 34, 3, 98, 9, 76, 45, 4]));

print("max of series 2 is " + maxcat([54, 546, 548, 60]));

{{out}}

<pre>"max of series 1 is 998764543431"

=={{header|Scala}}==

{{libheader|Scala}}

def lifci(list: List[Long]) = list.permutations.map(_.mkString).max

println(lifci(List(1, 34, 3, 98, 9, 76, 45, 4)))

println(lifci(List(54, 546, 548, 60)))

{{out}}

=={{header|Scheme}}==

(define (my-compare a b) (string>? (cat a b) (cat b a)))

(map (lambda (xs) (string->number (apply cat (sort xs my-compare))))

{{output}}

<pre>

=={{header|Sidef}}==

{{trans|Ruby}}

nums.sort {|x,y| "#{y}#{x}" <=> "#{x}#{y}" };

}

[[54, 546, 548, 60], [1, 34, 3, 98, 9, 76, 45, 4]].each { |c|

say maxnum(c).join.to_num;

{{out}}

<pre>

Version 1) sort by padded print strings:

{{works with|Smalltalk/X}}

(54 546 548 60)

(1 34 3 98 9 76 45 4)

collect:#printString) asStringWith:''.

Stdout printCR: resultString.

Version 2) alternative: sort by concatenated pair's strings:

(54 546 548 60)

(1 34 3 98 9 76 45 4)

collect:#printString) asStringWith:''.

Stdout printCR: resultString.

Note &sup1; replace "e'{a}{b}'" by "(a printString,b printString)" in dialects, which do not support embedded expression strings.

Version 3) no need to collect the resultString; simply print the sorted list (ok, if printing is all we want):

(54 546 548 60)

(1 34 3 98 9 76 45 4)

do:[:eachNr | eachNr printOn:Stdout].

Stdout cr.

Version 4) no need to generate any intermediate strings; the following will do as well:

(54 546 548 60)

(1 34 3 98 9 76 45 4)

(ints copy sortByApplying:[:i | i log10 fractionPart]) reverseDo:#print.

Stdout cr.

{{out}}

<pre>6054854654

=={{header|Tcl}}==

lsort -command {apply {{x y} {expr {"$y$x" - "$x$y"}}}} $nums

Demonstrating:

{1 34 3 98 9 76 45 4}

{54 546 548 60}

set sorted [intcatsort $collection]

puts "\[$collection\] => \[$sorted\] (concatenated: [join $sorted ""])"

{{out}}

<pre>

=={{header|VBScript}}==

{{trans|BBC BASIC}}

Function largestint(list)

nums = Split(list,",")

WScript.StdOut.Write largestint(WScript.Arguments(0))

WScript.StdOut.WriteLine

{{Out}}

=={{header|Vim Script}}==

This solution is intended to be run as an Ex command within a buffer containing the integers to be processed, one per line.

;Demonstration

1 34 3 98 9 76 45 4

$ vim -S icsort.vim nums

=={{header|Wren}}==

{{trans|Kotlin}}

{{libheader|Wren-sort}}

var cmp = Fn.new { |x, y|

for (a in arrays) {

System.print("%(a) -> %(findLargestSequence.call(a))")

{{out}}

=={{header|zkl}}==

ns.apply("toString").sort(fcn(a,b){ (a+b)>(b+a) }).concat();

{{out}}

<pre>