Largest int from concatenated ints

From Rosetta Code
Jump to: navigation, search
Task
Largest int from concatenated ints
You are encouraged to solve this task according to the task description, using any language you may know.

Given a set of positive integers, the task is to write a function to order the integers in such a way that the concatenation of the numbers forms the largest possible integer and return this integer.

Use the following two sets of integers as tests and show your program output here.

  • {1, 34, 3, 98, 9, 76, 45, 4}
  • {54, 546, 548, 60}
Possible algorithms
  1. A solution could be found by trying all combinations and return the best.
  2. Another way to solve this is to note that in the best arrangement, for any two adjacent original integers X and Y, the concatenation X followed by Y will be numerically greater than or equal to the concatenation Y followed by X.
  3. Yet another way to solve this is to pad ints to the same size by repeating the digits then sort using these repeated ints as a sort key.

Cf:

Contents

[edit] Ada

The algorithmic idea is to apply a twisted comparison function:

function Order(Left, Right: Natural) return Boolean is
( (Img(Left) & Img(Right)) > (Img(Right) & Img(Left)) );

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:

with Ada.Text_IO, Ada.Containers.Generic_Array_Sort;
 
procedure Largest_Int_From_List is
 
function Img(N: Natural) return String is
S: String := Integer'Image(N);
begin
return S(S'First+1 .. S'Last); -- First character is ' '
end Img;
 
function Order(Left, Right: Natural) return Boolean is
( (Img(Left) & Img(Right)) > (Img(Right) & Img(Left)) );
 
type Arr_T is array(Positive range <>) of Natural;
 
procedure Sort is new Ada.Containers.Generic_Array_Sort
(Positive, Natural, Arr_T, Order);
 
procedure Print_Sorted(A: Arr_T) is
B: Arr_T := A;
begin
Sort(B);
for Number of B loop
Ada.Text_IO.Put(Img(Number));
end loop;
Ada.Text_IO.New_Line;
end Print_Sorted;
 
begin
Print_Sorted((1, 34, 3, 98, 9, 76, 45, 4));
Print_Sorted((54, 546, 548, 60));
end Largest_Int_From_List;

[edit] AutoHotkey

LargestConcatenatedInts(var){
StringReplace, var, A_LoopField,%A_Space%,, all
Sort, var, D`, fConcSort
StringReplace, var, var, `,,, all
return var
}
 
ConcSort(a, b){
m := a . b , n := b . a
return m < n ? 1 : m > n ? -1 : 0
}
Examples:
d =
(
1, 34, 3, 98, 9, 76, 45, 4
54, 546, 548, 60
4 , 45, 54, 5
)
loop, parse, d, `n
MsgBox % LargestConcatenatedInts(A_LoopField)
Output:
998764543431
6054854654
554454

[edit] AWK

Works only with gawk 4.0

 
function cmp(i1, v1, i2, v2, u1, u2) {
u1 = v1""v2;
u2 = v2""v1;
return (u2 - u1)
}
function largest_int_from_concatenated_ints(X) {
PROCINFO["sorted_in"]="cmp";
u="";
for (i in X) u=u""X[i];
return u
}
 
BEGIN {
split("1 34 3 98 9 76 45 4",X);
print largest_int_from_concatenated_ints(X)
 
split("54 546 548 60",X);
print largest_int_from_concatenated_ints(X)
}
 
Output:
998764543431
6054854654

[edit] BBC BASIC

      DIM Nums%(10)
Nums%()=1,34,3,98,9,76,45,4
PRINT FNlargestint(8)
Nums%()=54,546,548,60
PRINT FNlargestint(4)
END
 
DEF FNlargestint(len%)
LOCAL i%,l$,a$,b$,sorted%
REPEAT
sorted%=TRUE
FOR i%=0 TO len%-2
a$=STR$Nums%(i%)
b$=STR$Nums%(i%+1)
IF a$+b$<b$+a$ SWAP Nums%(i%),Nums%(i%+1):sorted%=FALSE
NEXT
UNTIL sorted%
FOR i%=0 TO len%-1
l$+=STR$Nums%(i%)
NEXT
=l$
Output:
998764543431
6054854654

[edit] Bracmat

( ( maxnum
= A Z F C
.  !arg:#
|  !arg
 :  %@?F
 ?
( #%@?C
& ( str$(!F !C)+-1*str$(!C !F):~<0
| !C:?F
)
& ~
)
 ?
| !arg:?A !F ?Z&!F maxnum$(!A !Z)
)
& out$(str$(maxnum$(1 34 3 98 9 76 45 4)))
& out$(str$(maxnum$(54 546 548 60)))
);
Output:
998764543431
6054854654

[edit] C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int catcmp(const void *a, const void *b)
{
char ab[32], ba[32];
sprintf(ab, "%d%d", *(int*)a, *(int*)b);
sprintf(ba, "%d%d", *(int*)b, *(int*)a);
return strcmp(ba, ab);
}
 
void maxcat(int *a, int len)
{
int i;
qsort(a, len, sizeof(int), catcmp);
for (i = 0; i < len; i++)
printf("%d", a[i]);
putchar('\n');
}
 
int main(void)
{
int x[] = {1, 34, 3, 98, 9, 76, 45, 4};
int y[] = {54, 546, 548, 60};
 
maxcat(x, sizeof(x)/sizeof(x[0]));
maxcat(y, sizeof(y)/sizeof(y[0]));
 
return 0;
}
Output:
998764543431
6054854654

[edit] C++

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <string>
 
std::string findLargestConcat ( std::vector< int > & mynumbers ) {
std::vector<std::string> concatnumbers ;
std::sort ( mynumbers.begin( ) , mynumbers.end( ) ) ;
do {
std::ostringstream numberstream ;
for ( int i : mynumbers )
numberstream << i ;
concatnumbers.push_back( numberstream.str( ) ) ;
} while ( std::next_permutation( mynumbers.begin( ) ,
mynumbers.end( ) )) ;
return *( std::max_element( concatnumbers.begin( ) ,
concatnumbers.end( ) ) ) ;
}
 
int main( ) {
std::vector<int> mynumbers = { 98, 76 , 45 , 34, 9 , 4 , 3 , 1 } ;
std::vector<int> othernumbers = { 54 , 546 , 548 , 60 } ;
std::cout << "The largest concatenated int is " <<
findLargestConcat( mynumbers ) << " !\n" ;
std::cout << "And here it is " << findLargestConcat( othernumbers )
<< " !\n" ;
return 0 ;
}
Output:
The largest concatenated int is 998764543431 !
And here it is 6054854654 !

[edit] C#

using System;
using System.Collections.Generic;
using System.Linq;
 
class Program
{
static void Main(string[] args)
{
var source1 = new int[] { 1, 34, 3, 98, 9, 76, 45, 4 };
var source2 = new int[] { 54, 546, 548, 60 };
 
var largest1 = LargestPossibleSequence(source1);
var largest2 = LargestPossibleSequence(source2);
 
Console.WriteLine("The largest possible integer from set 1 is: {0}", largest1);
Console.WriteLine("The largest possible integer from set 2 is: {0}", largest2);
}
 
static long LargestPossibleSequence(int[] ints)
{
return long.Parse(string.Join("", ints.OrderBy(i => i, new IntConcatenationComparer()).Reverse()));
}
}
 
class IntConcatenationComparer : IComparer<int>
{
public int Compare(int x, int y)
{
var xy = int.Parse(x.ToString() + y.ToString());
var yx = int.Parse(y.ToString() + x.ToString());
 
return xy - yx;
}
}
 
Output:
The largest possible integer from set 1 is: 998764543431
The largest possible integer from set 2 is: 6054854654

[edit] Clojure

(defn maxcat [coll]
(read-string
(apply str
(sort (fn [x y]
(apply compare
(map read-string [(str y x) (str x y)])))
coll))))
 
(prn (map maxcat [[1 34 3 98 9 76 45 4] [54 546 548 60]]))
Output:
<pre>(998764543431 6054854654)

[edit] D

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

import std.stdio, std.algorithm, std.conv, std.array, permutations2;
 
auto maxCat1(in int[] arr) pure @safe {
return arr.to!(string[]).permutations.map!join.reduce!max;
}
 
auto maxCat2(in int[] arr) pure nothrow @safe {
return arr.to!(string[]).sort!q{b ~ a < a ~ b}.join;
}
 
auto maxCat3(in int[] arr) /*pure nothrow @safe*/ {
immutable maxL = arr.reduce!max.text.length;
return arr.to!(string[])
.schwartzSort!(s => s.replicate(maxL/s.length + 1), "a > b")
.join;
}
 
void main() {
const lists = [[1, 34, 3, 98, 9, 76, 45, 4], [54, 546, 548, 60]];
[&maxCat1, &maxCat2, &maxCat3].map!(cat => lists.map!cat).writeln;
}
Output:
[["998764543431", "6054854654"], ["998764543431", "6054854654"], ["998764543431", "6054854654"]]

[edit] Erlang

 
-module( largest_int_from_concatenated ).
 
-export( [ints/1, task/0] ).
 
ints( Ints ) ->
Int_strings = [erlang:integer_to_list(X) || X <- Ints],
Pad_ints = [{X ++ X, X} || X <- Int_strings],
erlang:list_to_integer( lists:append([Int || {_Pad, Int} <- lists:reverse(lists:sort(Pad_ints))]) ).
 
task() ->
[io:fwrite("Largest ~p from ~p~n", [ints(X), X]) || X <- [[1, 34, 3, 98, 9, 76, 45, 4], [54, 546, 548, 60]]].
 
Output:
8> largest_int_from_concatenated:task().
Largest 998764543431 from [1,34,3,98,9,76,45,4]
Largest 6054854654 from [54,546,548,60]

[edit] Go

// Variation of method 3.  Repeat digits to at least the size of the longest,
// then sort as strings.
package main
 
import (
"fmt"
"math/big"
"sort"
"strconv"
"strings"
)
 
type c struct {
i int
s, rs string
}
 
type cc []*c
 
func (c cc) Len() int { return len(c) }
func (c cc) Less(i, j int) bool { return c[j].rs < c[i].rs }
func (c cc) Swap(i, j int) { c[i], c[j] = c[j], c[i] }
 
// Function required by task. Takes a list of integers, returns big int.
func li(is ...int) *big.Int {
ps := make(cc, len(is))
ss := make([]c, len(is))
ml := 0
for j, i := range is {
p := &ss[j]
ps[j] = p
p.i = i
p.s = strconv.Itoa(i)
if len(p.s) > ml {
ml = len(p.s)
}
}
for _, p := range ps {
p.rs = strings.Repeat(p.s, (ml+len(p.s)-1)/len(p.s))
}
sort.Sort(ps)
s := make([]string, len(ps))
for i, p := range ps {
s[i] = p.s
}
b, _ := new(big.Int).SetString(strings.Join(s, ""), 10)
return b
}
 
func main() {
fmt.Println(li(1, 34, 3, 98, 9, 76, 45, 4))
fmt.Println(li(54, 546, 548, 60))
}
Output:
998764543431
6054854654

[edit] Groovy

def largestInt = { c -> c.sort { v2, v1 -> "$v1$v2" <=> "$v2$v1" }.join('') as BigInteger }

Testing:

assert largestInt([1, 34, 3, 98, 9, 76, 45, 4]) == 998764543431
assert largestInt([54, 546, 548, 60]) == 6054854654

[edit] Haskell

[edit] Compare repeated string method

import Data.List (sortBy)
import Data.Ord (comparing)
 
main = print (map maxcat [[1,34,3,98,9,76,45,4], [54,546,548,60]] :: [Integer])
where
sorted xs = let pad x = concat $ replicate (maxLen `div` length x + 1) x
maxLen = maximum $ map length xs
in sortBy (flip $ comparing pad) xs
 
maxcat = read . concat . sorted . map show
Output:
[998764543431,6054854654]

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.List (sortBy)
import Data.Ord (comparing)
import Data.Ratio ((%))
 
nines = iterate ((+9).(*10)) 9
 
maxcat = foldl (\a (n,d)->a * (1 + d) + n) 0 .
sortBy (flip $ comparing $ uncurry (%)) .
map (\a->(a, head $ dropWhile (<a) nines))
 
main = mapM_ (print.maxcat) [[1,34,3,98,9,76,45,4], [54,546,548,60]]

[edit] Sort on comparison of concatenated ints method

import Data.List (sortBy)
 
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))
maxcat = read . concat . sorted . map show
Output as above.

[edit] Try all permutations method

import Data.List (sort, permutations)
 
main = print (map maxcat [[1,34,3,98,9,76,45,4], [54,546,548,60]] :: [Integer])
where maxcat = read . last . sort . map (concat . map show) . permutations
Output as above.

[edit] Icon and Unicon

This solution only works in Unicon as it uses a Heap class to do the heavy lifting.

import Collections    # For the Heap (dense priority queue) class
 
procedure main(a)
write(lici(a))
end
 
procedure lici(a)
every (result := "") ||:= Heap(a,,cmp).gen()
return result
end
 
procedure cmp(a,b)
return (a||b) > (b||a)
end

Sample runs:

->lici 1 34 3 98 9 76 45 4
998764543431
->lici 54 546 548 60
6054854654
->

[edit] J

Solution:

maxlen=: [: >./ #&>
maxnum=: (0 ". ;)@(\: maxlen $&> ])@(8!:0)

Usage:

   maxnum&> 1 34 3 98 9 76 45 4 ; 54 546 548 60
998764543431 6054854654

[edit] Java

Works with: Java version 1.5+

This example sets up a comparator to order the numbers using Collections.sort as described in method #3 (padding and reverse sorting). It was also necessary to make a join method to meet the output requirements.

import java.util.*;
 
public class IntConcat {
 
private static Comparator<Integer> sorter = new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2){
String o1s = o1.toString();
String o2s = o2.toString();
 
if(o1s.length() == o2s.length()){
return o2s.compareTo(o1s);
}
 
int mlen = Math.max(o1s.length(), o2s.length());
while(o1s.length() < mlen * 2) o1s += o1s;
while(o2s.length() < mlen * 2) o2s += o2s;
 
return o2s.compareTo(o1s);
}
};
 
public static String join(List<?> things){
String output = "";
for(Object obj:things){
output += obj;
}
return output;
}
 
public static void main(String[] args){
List<Integer> ints1 = new ArrayList<Integer>(Arrays.asList(1, 34, 3, 98, 9, 76, 45, 4));
 
Collections.sort(ints1, sorter);
System.out.println(join(ints1));
 
List<Integer> ints2 = new ArrayList<Integer>(Arrays.asList(54, 546, 548, 60));
 
Collections.sort(ints2, sorter);
System.out.println(join(ints2));
}
}
Works with: Java version 1.8+
import java.util.Comparator;
import java.util.stream.Collectors;
import java.util.stream.Stream;
 
public interface IntConcat {
public static Comparator<Integer> SORTER = (o1, o2) -> {
String o1s = o1.toString();
String o2s = o2.toString();
 
if (o1s.length() == o2s.length()) {
return o2s.compareTo(o1s);
}
 
int mlen = Math.max(o1s.length(), o2s.length());
while (o1s.length() < mlen * 2) {
o1s += o1s;
}
while (o2s.length() < mlen * 2) {
o2s += o2s;
}
 
return o2s.compareTo(o1s);
};
 
public static void main(String[] args) {
Stream<Integer> ints1 = Stream.of(
1, 34, 3, 98, 9, 76, 45, 4
);
 
System.out.println(ints1
.parallel()
.sorted(SORTER)
.map(String::valueOf)
.collect(Collectors.joining())
);
 
Stream<Integer> ints2 = Stream.of(
54, 546, 548, 60
);
 
System.out.println(ints2
.parallel()
.sorted(SORTER)
.map(String::valueOf)
.collect(Collectors.joining())
);
}
}
Output:
998764543431
6054854654

[edit] jq

Works with: jq version 1.4

[edit] Padding

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

def largest_int:
 
def pad(n): . + (n - length) * .[length-1:];
 
map(tostring)
| (map(length) | max) as $max
| map([., pad($max)])
| sort_by( .[1] )
| map( .[0] ) | reverse | join("") ;
 
# Examples:
([1, 34, 3, 98, 9, 76, 45, 4],
[54, 546, 548, 60]) | largest_int
 
Output:
$ /usr/local/bin/jq -n -M -r -f Largest_int_from_concatenated_ints.jq
998764543431
6054854654

[edit] Custom Sort

The following uses quicksort/1:

def largest_int:
map(tostring)
| quicksort( .[0] + .[1] < .[1] + .[0] )
| reverse | join("") ;

[edit] Lua

Translation of: Python
function icsort(numbers)
table.sort(numbers,function(x,y) return (x..y) > (y..x) end)
return numbers
end
 
for _,numbers in pairs({{1, 34, 3, 98, 9, 76, 45, 4}, {54, 546, 548, 60}}) do
print(('Numbers: {%s}\n Largest integer: %s'):format(
table.concat(numbers,","),table.concat(icsort(numbers))
))
end
Output:
Numbers: {1,34,3,98,9,76,45,4}
  Largest integer: 998764543431
Numbers: {54,546,548,60}
  Largest integer: 6054854654

[edit] Mathematica

makeLargestInt[list_] := Module[{sortedlist},
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}]
makeLargestInt[{54, 546, 548, 60}]
Output:
998764543431
6054854654


[edit] NetRexx

/* NetRexx */
options replace format comments java crossref symbols nobinary
 
runSample(arg)
return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method largestInt(il) public static
ri = ''
wa = ''
-- put the list into an indexed string
wa[0] = il.words
loop ww = 1 to wa[0]
wa[ww] = il.word(ww)
end ww
 
-- order the list
loop wx = 1 to wa[0] - 1
loop wy = wx + 1 to wa[0]
xx = wa[wx]
yy = wa[wy]
xy = xx || yy
yx = yy || xx
if xy < yx then do
-- swap xx and yy
wa[wx] = yy
wa[wy] = xx
end
end wy
end wx
 
-- rebuild list from indexed string
loop ww = 1 to wa[0]
ri = ri wa[ww]
end ww
return ri.space(0) -- concatenate the list elements into a single numeric
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method runSample(arg) private static
ints = [ -
'1 34 3 98 9 76 45 4', -
'54 546 548 60' -
]
loop il over ints
say largestInt(il).right(20) ':' il.space(1, ',')
end il
return
 
Output:
        998764543431 : 1,34,3,98,9,76,45,4
          6054854654 : 54,546,548,60

[edit] Nimrod

import algorithm, sequtils, strutils, future
 
proc maxNum(x: seq[int]): string =
var c = x.mapIt(string, $it)
c.sort((x, y) => cmp(y&x, x&y))
c.join()
 
echo maxNum(@[1, 34, 3, 98, 9, 76, 45, 4])
echo maxNum(@[54, 546, 548, 60])
Output:
998764543431
6054854654

[edit] OCaml

let myCompare a b = compare (b ^ a) (a ^ b)
let icsort nums = String.concat "" (List.sort myCompare (List.map string_of_int nums))
testing
# icsort [1;34;3;98;9;76;45;4];;  
- : string = "998764543431"
# icsort [54;546;548;60];;
- : string = "6054854654"

[edit] Pascal

tested with freepascal.Used a more extreme example 3.

[edit] algorithm 3

const
base = 10;
MaxDigitCnt = 11;
source1 : array[0..7] of integer = (1, 34, 3, 98, 9, 76, 45, 4);
source2 : array[0..3] of integer = (54,546,548,60);
source3 : array[0..3] of integer = (60, 54,545454546,0);
 
type
tdata = record
datOrg,
datMod : LongWord;
datStrOrg : string[MaxDigitCnt];
end;
tArrData = array of tData;
 
procedure DigitCount(var n: tdata);
begin
with n do
//InttoStr is very fast
str(datOrg,datStrOrg);
 
end;
 
procedure InsertData(var n: tdata;data:LongWord);
begin
n.datOrg := data;
DigitCount(n);
end;
 
function FindMaxLen(const ArrData:tArrData): LongWord;
var
cnt : longInt;
res,t : LongWord;
begin
res := 0;// 1 is minimum
for cnt := High(ArrData) downto Low(ArrData) do
begin
t := length(ArrData[cnt].datStrOrg);
IF res < t then
res := t;
end;
FindMaxLen := res;
end;
 
procedure ExtendCount(var ArrData:tArrData;newLen: integer);
var
cnt,
i,k : integer;
begin
For cnt := High(ArrData) downto Low(ArrData) do
with ArrData[cnt] do
begin
datMod := datOrg;
i := newlen-length(datStrOrg);
k := 1;
while i > 0 do
begin
datMod := datMod *Base+Ord(datStrOrg[k])-Ord('0');
inc(k);
IF k >length(datStrOrg) then
k := 1;
dec(i);
end;
end;
end;
 
procedure SortArrData(var ArrData:tArrData);
var
i,
j,idx : integer;
tmpData : tData;
begin
For i := High(ArrData) downto Low(ArrData)+1 do
begin
idx := i;
j := i-1;
For j := j downto Low(ArrData) do
IF ArrData[idx].datMod < ArrData[j].datMod then
idx := j;
IF idx <> i then
begin
tmpData := ArrData[idx];
ArrData[idx]:= ArrData[i];
ArrData[i] := tmpData;
end;
end;
end;
 
procedure ArrDataOutput(const ArrData:tArrData);
var
i,l : integer;
s : string;
begin
{ the easy way
For i := High(ArrData) downto Low(ArrData) do
write(ArrData[i].datStrOrg);
writeln;
*}

l := 0;
For i := High(ArrData) downto Low(ArrData) do
inc(l,length(ArrData[i].datStrOrg));
setlength(s,l);
l:= 1;
For i := High(ArrData) downto Low(ArrData) do
with ArrData[i] do
begin
move(datStrOrg[1],s[l],length(datStrOrg));
inc(l,length(datStrOrg));
end;
writeln(s);
end;
 
procedure HighestInt(var ArrData:tArrData);
begin
ExtendCount(ArrData,FindMaxLen(ArrData));
SortArrData(ArrData);
ArrDataOutput(ArrData);
end;
 
var
i : integer;
tmpData : tArrData;
begin
// Source1
setlength(tmpData,length(source1));
For i := low(tmpData) to high(tmpData) do
InsertData(tmpData[i],source1[i]);
HighestInt(tmpData);
// Source2
setlength(tmpData,length(source2));
For i := low(tmpData) to high(tmpData) do
InsertData(tmpData[i],source2[i]);
HighestInt(tmpData);
// Source3
setlength(tmpData,length(source3));
For i := low(tmpData) to high(tmpData) do
InsertData(tmpData[i],source3[i]);
HighestInt(tmpData);
end.
Output:
998764543431
6054854654
60545454546540

[edit] inspired bei Haskell

generate the repetition by dividing /(10^CountDigits-1) http://rosettacode.org/wiki/Largest_int_from_concatenated_ints#Compare_repeated_string_method

const
base = 10;
MaxDigitCnt = 11;
source1 : array[0..7] of LongInt = (10 , 34, 3, 98, 9, 76, 45, 4);
source2 : array[0..3] of LongInt = (54,546,548,60);
source3 : array[0..3] of LongInt = (0,2121212122,21,60);
 
type
tdata = record
datMod : double;
datOrg : LongInt;
//InttoStr is very fast and the string is always needed
datStrOrg : string[MaxDigitCnt];
end;
tArrData = array of tData;
 
procedure InsertData(var n: tdata;data:LongWord);
begin
with n do
begin
datOrg := data;
str(datOrg,datStrOrg);
end;
end;
 
function FindMaxLen(const ArrData:tArrData): LongWord;
var
cnt : longInt;
res,t : LongWord;
begin
res := 0;// 1 is minimum
for cnt := High(ArrData) downto Low(ArrData) do
begin
t := length(ArrData[cnt].datStrOrg);
IF res < t then
res := t;
end;
FindMaxLen := res;
end;
 
procedure ExtendData(var ArrData:tArrData;newLen: integer);
var
cnt,
i : integer;
begin
For cnt := High(ArrData) downto Low(ArrData) do
with ArrData[cnt] do
begin
//generating 10^length(datStrOrg)
datMod := 1;
i := length(datStrOrg);
// i always >= 1
repeat
datMod := base*datMod;
dec(i);
until i <= 0;
// 1/(datMod-1.0) = 1/(9...9)
datMod := datOrg/(datMod-1.0)+datOrg;
i := newlen-length(datStrOrg);
For i := i downto 1 do
datMod := datMod*Base;
end;
end;
 
procedure SortArrData(var ArrData:tArrData);
//selection sort
var
i,
j,idx : integer;
tmpData : tData;
begin
For i := High(ArrData) downto Low(ArrData)+1 do
begin
idx := i;
j := i-1;
//select max
For j := j downto Low(ArrData) do
IF ArrData[idx].datMod < ArrData[j].datMod then
idx := j;
//finally swap
IF idx <> i then
begin
tmpData := ArrData[idx];
ArrData[idx]:= ArrData[i];
ArrData[i] := tmpData;
end;
end;
end;
 
procedure ArrDataOutput(const ArrData:tArrData);
var
i : integer;
begin
{ the easy way}
For i := High(ArrData) downto Low(ArrData) do
write(ArrData[i].datStrOrg);
writeln;
end;
 
procedure HighestInt(var ArrData:tArrData);
begin
ExtendData(ArrData,FindMaxLen(ArrData));
SortArrData(ArrData);
ArrDataOutput(ArrData);
end;
 
var
i : integer;
tmpData : tArrData;
begin
// Source1
setlength(tmpData,length(source1));
For i := low(tmpData) to high(tmpData) do
InsertData(tmpData[i],source1[i]);
HighestInt(tmpData);
// Source2
setlength(tmpData,length(source2));
For i := low(tmpData) to high(tmpData) do
InsertData(tmpData[i],source2[i]);
HighestInt(tmpData);
// Source3
setlength(tmpData,length(source3));
For i := low(tmpData) to high(tmpData) do
InsertData(tmpData[i],source3[i]);
HighestInt(tmpData);
end.
Output:
9987645434310
6054854654
602121212122210>

[edit] PARI/GP

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

large(v)=eval(concat(apply(n->Str(n),vecsort(v,(x,y)->eval(Str(y,x,"-",x,y))))));
large([1, 34, 3, 98, 9, 76, 45, 4])
large([54, 546, 548, 60])
Output:
%1 = 998764543431
%2 = 6054854654

[edit] Perl

sub maxnum {
join '', sort { "$b$a" cmp "$a$b" } @_
}
 
print maxnum(1, 34, 3, 98, 9, 76, 45, 4), "\n";
print maxnum(54, 546, 548, 60), "\n";
Output:
998764543431
6054854654

[edit] Perl 6

sub maxnum(@x) {
[~] @x.sort: -> $a, $b { $b ~ $a leg $a ~ $b }
}
 
say maxnum <1 34 3 98 9 76 45 4>;
say maxnum <54 546 548 60>;
Output:
998764543431
6054854654

[edit] PHP

function maxnum($nums) {
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";
echo maxnum(array(54, 546, 548, 60)), "\n";
Output:
998764543431
6054854654

[edit] PicoLisp

Here are solutions for all three algorithms.

The third solution actually avoids padding the numbers, by converting them into circular lists and comparing these. As a drawback, however, this works only for unique lists (as the comparison of identical numbers would not terminate), so a better solution might involve additional checks.

(load "@lib/simul.l")  # For 'permute'

[edit] Algorithm 1

(for L '((1 34 3 98 9 76 45 4) (54 546 548 60))
(prinl (maxi format (permute L))) )

[edit] Algorithm 2

(for L '((1 34 3 98 9 76 45 4) (54 546 548 60))
(prinl
(sort L
'((A B)
(>
(format (pack A B))
(format (pack B A)) ) ) ) ) )

[edit] Algorithm 3

(for L '((1 34 3 98 9 76 45 4) (54 546 548 60))
(prinl
(flip
(by '((N) (apply circ (chop N))) sort L) ) ) )
Output:
in all three cases:
998764543431
6054854654

[edit] PL/I

 
/* Largest catenation of integers 16 October 2013 */
/* Sort using method 2, comparing pairs of adjacent integers. */
 
Largest: procedure options (main);
declare s(*) char (20) varying controlled, n fixed binary;
get (n);
allocate s(n);
get list (s);
s = trim(s);
put skip edit (s) (a, x(1));
put skip list ('Largest integer=', Largest_integer());
 
largest_integer: procedure () returns (char(100) varying);
declare sorted bit (1);
declare (true value ('1'b), false value ('0'b)) bit (1);
declare i fixed binary;
declare temp character(20) varying;
 
do until (sorted);
sorted = true;
do i = 1 to n-1;
if char(s(i)) || char(s(i+1)) < char(s(i+1)) || char(s(i)) then
do;
temp = s(i); s(i) = s(i+1); s(i+1) = temp; sorted = false;
end;
end;
end;
return (string(s));
end largest_integer;
end Largest;
 
54 546 548 60
Largest integer=        6054854654 

1 34 3 98 9 76 45 4
Largest integer=        998764543431 

[edit] Prolog

Works with SWI-Prolog 6.5.3.

[edit] All permutations method

largest_int_v1(In, Out) :-
maplist(name, In, LC),
aggregate(max(V), get_int(LC, V), Out).
 
 
get_int(LC, V) :-
permutation(LC, P),
append(P, LV),
name(V, LV).
 
Output:
 ?- largest_int_v1([1, 34, 3, 98, 9, 76, 45, 4], Out).
Out = 998764543431.

 ?- largest_int_v1([54, 546, 548, 60], Out).
Out = 6054854654.

[edit] Method 2

largest_int_v2(In, Out) :-
maplist(name, In, LC),
predsort(my_sort,LC, LCS),
append(LCS, LC1),
name(Out, LC1).
 
 
my_sort(R, L1, L2) :-
append(L1, L2, V1), name(I1, V1),
append(L2, L1, V2), name(I2, V2),
( I1 < I2, R = >; I1 = I2, R = '='; R = <).
 
 
 
% particular case 95 958
my_sort(>, [H1], [H1, H2 | _]) :-
H1 > H2.
 
my_sort(<, [H1], [H1, H2 | _]) :-
H1 < H2.
 
my_sort(R, [H1], [H1, H1 | T]) :-
my_sort(R, [H1], [H1 | T]).
 
 
 
% particular case 958 95
my_sort(>, [H1, H2 | _], [H1]) :-
H1 > H2.
 
my_sort(<, [H1, H2 | _], [H1]) :-
H1 < H2.
 
my_sort(R, [H1, H1 | T], [H1]) :-
my_sort(R, [H1 | T], [H1]) .
 
Output:
 ?- largest_int_v2([1, 34, 3, 98, 9, 76, 45, 4], Out).
Out = 998764543431 .

 ?- largest_int_v2([54, 546, 548, 60], Out).
Out = 5486054654 .

[edit] Python

[edit] Python: Sort on comparison of concatenated ints method

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

try:
cmp # Python 2 OK or NameError in Python 3
def maxnum(x):
return ''.join(sorted((str(n) for n in x),
cmp=lambda x,y:cmp(y+x, x+y)))
except NameError:
# Python 3
from functools import cmp_to_key
def cmp(x, y):
return -1 if x<y else ( 0 if x==y else 1)
def maxnum(x):
return ''.join(sorted((str(n) for n in x),
key=cmp_to_key(lambda x,y:cmp(y+x, x+y))))
 
for numbers in [(1, 34, 3, 98, 9, 76, 45, 4), (54, 546, 548, 60):
print('Numbers: %r\n Largest integer: %15s' % (numbers, maxnum(numbers)))
Output:
Numbers: (1, 34, 3, 98, 9, 76, 45, 4)
  Largest integer:    998764543431
Numbers: (54, 546, 548, 60)
  Largest integer:      6054854654

[edit] Python: Compare repeated string method

def maxnum(x):
maxlen = len(str(max(x)))
return ''.join(sorted((str(v) for v in x), reverse=True,
key=lambda i: i*(maxlen * 2 // len(i))))
 
for numbers in [(212, 21221), (1, 34, 3, 98, 9, 76, 45, 4), (54, 546, 548, 60)]:
print('Numbers: %r' % (numbers, maxnum(numbers)))
Output:
Numbers: (212, 21221)
  Largest integer:        21221221
Numbers: (1, 34, 3, 98, 9, 76, 45, 4)
  Largest integer:    998764543431
Numbers: (54, 546, 548, 60)
  Largest integer:      6054854654
Works with: Python version 2.6+
from fractions import Fraction
from math import log10
 
def maxnum(x):
return ''.join(str(n) for n in sorted(x, reverse=True,
key=lambda i: Fraction(i, 10**(int(log10(i))+1)-1)))
 
for numbers in [(1, 34, 3, 98, 9, 76, 45, 4), (54, 546, 548, 60)]:
print('Numbers: %r\n Largest integer: %15s' % (numbers, maxnum(numbers)))
Output as first Python example, above.

[edit] Python: Try all permutations method

from itertools import permutations
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)]:
print('Numbers: %r\n Largest integer: %15s' % (numbers, maxnum(numbers)))
Output as above.

[edit] Racket

 
#lang racket
(define (largest-int ns)
(string->number (apply ~a (sort ns (λ(x y) (string>? (~a x y) (~a y x)))))))
(map largest-int '((1 34 3 98 9 76 45 4) (54 546 548 60)))
;; -> '(998764543431 6054854654)
 

[edit] REXX

The algorithm used is based on exact comparisons (left to right) with right digit fill of the left digit.   This allows the integers to be of any size.

This REXX example doesn't do any error checking/verifying that:

  • the numbers are in fact, numbers
  • the numbers are positive integers   (however, zeroes will work correctly)
  • the integer numbers are well formed
  • the lists are well formed
  • the list isn't null
/*REXX pgm constructs largest integer  from a list  using concatenation.*/
@. = /*used to signify end-of-lists. */
@.1 = '{1, 34, 3, 98, 9, 76, 45, 4}'
@.2 = '{54, 546, 548, 60}'
/* [↓] process all the lists. */
do j=1 while @.j\==''; $= /*keep truckin' until exausted. */
z=space(translate(@.j, , '])},{([')) /*perform some scrubbing on list.*/
 
do while z\=='' /*examine each number in the list*/
big=word(z,1); index=1 /*assume first number is biggest.*/
 
do k=2 to words(z); x=word(z,k) /*get an integer.*/
L=max(length(big), length(x)) /*get max length.*/
if left(x,L,left(x,1)) <<= left(big,L,left(big,1)) then iterate
big=x; index=k /*we found a new biggie (& index)*/
end /*k*/
 
z=space(delword(z, index, 1)) /*remove the "maximum" from list*/
$=$ || big /*append the "maximum" number. */
end /*while z¬==''*/
 
say right($,30) ' max for: ' @.j /*show the "max" integer and list*/
end /*j*/
/*stick a fork in it, we're done.*/
Output:
                  998764543431  max for:  {1, 34, 3, 98, 9, 76, 45, 4}
                    6054854654  max for:  {54, 546, 548, 60}

[edit] Ruby

[edit] Sort on comparison of concatenated ints method

Translation of: Tcl
def icsort nums
nums.sort { |x, y| "#{y}#{x}" <=> "#{x}#{y}" }
end
 
[[54, 546, 548, 60], [1, 34, 3, 98, 9, 76, 45, 4]].each do |c|
p c # prints nicer in Ruby 1.8
puts icsort(c).join
end
Output:
[54, 546, 548, 60]
6054854654
[1, 34, 3, 98, 9, 76, 45, 4]
998764543431

[edit] Compare repeated string method

def icsort nums
maxlen = nums.max.to_s.length
nums.map{ |x| x.to_s }.sort_by { |x| x * (maxlen * 2 / x.length) }.reverse
end
 
[[54, 546, 548, 60], [1, 34, 3, 98, 9, 76, 45, 4]].each do |c|
p c # prints nicer in Ruby 1.8
puts icsort(c).join
end
Output as above.
require 'rational' #Only needed in Ruby < 1.9
 
def icsort nums
nums.sort_by { |i| Rational(i, 10**(Math.log10(i).to_i+1)-1) }.reverse
end
 
[[54, 546, 548, 60], [1, 34, 3, 98, 9, 76, 45, 4]].each do |c|
p c # prints nicer in Ruby 1.8
puts icsort(c).join
end
Output as above.

[edit] Run BASIC

a1$ = "1, 34, 3, 98, 9, 76, 45, 4"
a2$ = "54,546,548,60"
 
print "Max Num ";a1$;" = ";maxNum$(a1$)
print "Max Num ";a2$;" = ";maxNum$(a2$)
 
function maxNum$(a1$)
while word$(a1$,i+1,",") <> ""
i = i + 1
a$(i) = trim$(word$(a1$,i,","))
wend
 
s = 1
while s = 1
s = 0
for j = 1 to i -1
if a$(j)+a$(j+1) < a$(j+1)+a$(j) then
h$ = a$(j)
a$(j) = a$(j+1)
a$(j+1) = h$
s = 1
end if
next j
wend
 
for j = 1 to i
maxNum$ = maxNum$ ; a$(j)
next j
end function
Output:
Max Num 1, 34, 3, 98, 9, 76, 45, 4 = 998764543431
Max Num 54,546,548,60 = 6054854654

[edit] Scala

Library: Scala
object LIFCI extends App {
 
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)))
}
Output:
998764543431
6054854654

[edit] Tcl

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

Demonstrating:

foreach collection {
{1 34 3 98 9 76 45 4}
{54 546 548 60}
} {
set sorted [intcatsort $collection]
puts "\[$collection\] => \[$sorted\] (concatenated: [join $sorted ""])"
}
Output:
[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)

[edit] 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.

%s/\(.\+\)/\1\1/ | sort! | %s/\(.\+\)\1\n/\1/
Demonstration
$ paste -s nums
1 34 3 98 9 76 45 4
$ vim -S icsort.vim nums
998764543431

[edit] zkl

fcn bigCI(ns){
ns.apply("toString").sort(fcn(a,b){ (a+b)>(b+a) }).concat();
}
bigCI(T(1, 34, 3, 98, 9, 76, 45, 4)).println();
bigCI(T(54, 546, 548, 60)).println();
Output:
998764543431
6054854654
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox