Largest int from concatenated ints: Difference between revisions

*   [http://stackoverflow.com/questions/14532105/constructing-the-largest-number-possible-by-rearranging-a-list/14539943#14539943 Constructing the largest number possible by rearranging a list]

<br><br>

 

=={{header|Ada}}==

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>

6054854654

</pre>

 

=={{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}}

<pre>998764543431

6054854654</pre>

 

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

using System.Collections.Generic;

using System.Linq;

}

}

 

{{out}}

<pre>The largest possible integer from set 1 is: 998764543431

The largest possible integer from set 2 is: 6054854654</pre>

 

=={{header|Ceylon}}==

{{trans|Kotlin}}

return yx <=> xy;

}

value test1 = {1, 34, 3, 98, 9, 76, 45, 4};

 

=={{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>

6054854654

</pre>

 

=={{header|Fortran}}==

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}}==

 

 

 

 

 

 

 

{{out}}

 

=={{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 =

print

(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:

 

=={{header|J}}==

'''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

6054854654</pre>

=={{header|JavaScript}}==

 

===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.

 

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

end

for arr in tests

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

 

{{out}}

=={{header|Kotlin}}==

{{trans|C#}}

 

fun main(args: Array<String>) {

 

fun findLargestSequence(array: IntArray): String {

}

 

{{Out}}

 

=={{header|Lua}}==

 

{{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}

Largest integer: 6054854654</pre>

 

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

6054854654</pre>

 

 

 

=={{header|NetRexx}}==

options replace format comments java crossref symbols nobinary

 

end il

return

{{out}}

<pre>

 

=={{header|Nim}}==

 

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

c.sort((x, y) => cmp(y&x, x&y))

c.join()

 

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

{{out}}

<pre>998764543431

 

=={{header|OCaml}}==

 

;testing

=={{header|Oforth}}==

 

 

{{out}}

[998764543431, 6054854654]

</pre>

 

=={{header|Pascal}}==

tested with freepascal.Used a more extreme example 3.

===algorithm 3===

base = 10;

MaxDigitCnt = 11;

var

i,l : integer;

begin

{ the easy way

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

6054854654

602121212122210></pre>

 

=={{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}}==

{{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

6054854654</pre>

 

=={{header|PicoLisp}}==

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):

key=cmp_to_key(lambda x,y:cmp(y+x, x+y))))

 

 

{{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.

 

=={{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|REXX}}==

The algorithm used is based on exact comparisons (left to right) &nbsp; with &nbsp; ''right digit fill'' &nbsp; of the &nbsp; ''left digit''.

<br>verify that the numbers are indeed integers &nbsp; (and it also normalizes the integers).

 

===simple integers===

w=0 /* [↓] process all the integer lists.*/

w=max(w, length(z) ); $= /*obtain maximum width to align output.*/

if left(#, L, left(#, 1) ) <<= left(big, L, left(big, 1) ) then iterate

end /*k*/ /* [↑] find max concatenated integer. */

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

say 'largest concatenatated integer from ' left( space(@.j), w) " is ─────► " $

end /*j*/ /* [↑] process each list of integers. */

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

{{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).

w=max(w, length(z) ); $= /*obtain maximum width to align output.*/

if left(#, L, left(#, 1) ) <<= left(big, L, left(big, 1) ) then iterate

end /*k*/ /* [↑] find max concatenated integer. */

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

say 'largest concatenatated integer from ' left( space(@.j), w) " is " $

exit /*stick a fork in it, we're all done. */

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

if pos('E',#)>0 then do; parse var # mant "E" pow /*Has exponent? Expand*/

numeric digits pow + length(mand) /*expand digs, adjust#*/

end

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

largest concatenatated integer from 1 34 3 98 9 76 45 4 is 998764543431

largest concatenatated integer from 54 546 548 60 is 6054854654

===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>

998764543431

6054854654

</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>

998764543431

</pre>

 

=={{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>

[1 34 3 98 9 76 45 4] => [9 98 76 45 4 34 3 1] (concatenated: 998764543431)

[54 546 548 60] => [60 548 546 54] (concatenated: 6054854654)

</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|zkl}}==

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

{{out}}

<pre>