Largest int from concatenated ints

From Rosetta Code
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:

Ada

The algorithmic idea is to apply a twisted comparison function:

<lang Ada>function Order(Left, Right: Natural) return Boolean is 

     ( (Img(Left) & Img(Right)) > (Img(Right) & Img(Left)) );</lang>

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:

<lang Ada>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;</lang>

AWK

Works only with gawk 4.0 <lang awk> 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) } </lang>

Output:
998764543431
6054854654

C

<lang C>#include <stdio.h>

  1. include <stdlib.h>
  2. include <string.h>

int catcmp(const void *a, const void *b) { char ab[32], ba[32]; sprintf(ab, "%d%d", *(const int*)a, *(const int*)b); sprintf(ba, "%d%d", *(const int*)b, *(const 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; }</lang>

Output:
998764543431
6054854654

C++

<lang cpp>#include <iostream>

  1. include <sstream>
  2. include <algorithm>
  3. include <vector>
  4. 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 ;

}</lang>

Output:
The largest concatenated int is 998764543431 !
And here it is 6054854654 !

Clojure

<lang 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]]))</lang>

Output:
<pre>(998764543431 6054854654)

D

The three algorithms. Uses the second module from the Permutations Task. <lang d>import std.stdio, std.algorithm, std.conv, std.array, permutations2;

auto maxCat1(in int[] arr) { 

   return arr.to!(string[]).permutations.map!join.reduce!max;

}

auto maxCat2(in int[] arr) { 

   return arr.to!(string[]).sort!q{b ~ a < a ~ b}.join;

}

auto maxCat3(in int[] arr) { 

   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;

}</lang>

Output:
[["998764543431", "6054854654"], ["998764543431", "6054854654"], ["998764543431", "6054854654"]]

Haskell

Compare repeated string method

<lang Haskell>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</lang>
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: <lang haskell>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]]</lang>

Sort on comparison of concatenated ints method

<lang Haskell>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</lang>
Output as above.

Try all permutations method

<lang Haskell>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</lang>
Output as above.

J

Solution: <lang j>maxlen=: [: >./ #&> maxnum=: (0 ". ;)@(\: maxlen $&> ])@(8!:0)</lang> Usage: <lang j> maxnum&> 1 34 3 98 9 76 45 4 ; 54 546 548 60 998764543431 6054854654</lang>

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. <lang java5>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));
   }

}</lang> Output: 

998764543431
6054854654

OCaml

<lang ocaml>let myCompare a b = compare (b ^ a) (a ^ b) let icsort nums = String.concat "" (List.sort myCompare (List.map string_of_int nums))</lang>

testing
# icsort [1;34;3;98;9;76;45;4];;  
- : string = "998764543431"
# icsort [54;546;548;60];;
- : string = "6054854654"

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.

<lang parigp>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])</lang> Output: 

%1 = 998764543431
%2 = 6054854654

Perl

<lang 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";</lang>

Output:
998764543431
6054854654

Perl 6

<lang perl6>sub maxnum(@x) { 

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

}

say maxnum <1 34 3 98 9 76 45 4>; say maxnum <54 546 548 60>;</lang>

Output:
998764543431
6054854654

PHP

<lang 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";</lang>

Output:
998764543431
6054854654

Python

Python: Sort on comparison of concatenated ints method

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

<lang python>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)))</lang>
Output:
Numbers: (1, 34, 3, 98, 9, 76, 45, 4)
  Largest integer:    998764543431
Numbers: (54, 546, 548, 60)
  Largest integer:      6054854654

Python: Compare repeated string method

<lang python>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)))</lang>
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+

<lang python>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)))</lang>
Output as first Python example, above.

Python: Try all permutations method

<lang python>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)))</lang>
Output as above.

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

<lang rexx>/*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=strip(delword(z, index, 1))    /*remove the  "maximum" from list*/
     $=$ || big                       /*append the  "maximum"  number. */
     end      /*while*/

 say right($,30)   ' max for: '   @.j /*show the "max" integer and list*/
 end          /*j*/
                                      /*stick a fork in it, we're done.*/</lang>

output 

                  998764543431  max for:  {1, 34, 3, 98, 9, 76, 45, 4}
                    6054854654  max for:  {54, 546, 548, 60}

Ruby

Sort on comparison of concatenated ints method

Translation of: Tcl

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

Output:
[54, 546, 548, 60]
6054854654
[1, 34, 3, 98, 9, 76, 45, 4]
998764543431

Compare repeated string method

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

Output as above.

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

Output as above.

Run BASIC

<lang runbasic>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</lang>Output

Max Num 1, 34, 3, 98, 9, 76, 45, 4 = 998764543431
Max Num 54,546,548,60 = 6054854654

Scala

Works with: Scala version 2.9.1

<lang Scala>object LIFCI extends App { 

 List(List(1, 34, 3, 98, 9, 76, 45, 4), List(54, 546, 548, 60)).map{l=>l.permutations.toList
   .map{l=>(l.map{_.toString}:\"")(_+_).toLong}.sorted.last}.foreach{println}

}</lang> Output: 

998764543431
6054854654

Tcl

<lang tcl>proc intcatsort {nums} { 

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

}</lang> Demonstrating: <lang tcl>foreach collection { 

   {1 34 3 98 9 76 45 4}
   {54 546 548 60}

} { 

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

}</lang>

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)

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. <lang Vim>%s/\(.\+\)/\1\1/ | sort! | %s/\(.\+\)\1\n/\1/</lang>

Demonstration

<lang Bash>$ paste -s nums 1 34 3 98 9 76 45 4 $ vim -S icsort.vim nums 998764543431</lang>

Retrieved from "https://rosettacode.org/wiki/Largest_int_from_concatenated_ints?oldid=228924"