Largest int from concatenated ints

Largest int from concatenated ints is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Given a set of 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 number.

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}

Note: A solution could be to try all combinations and return the best. 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.

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

• Algorithms: What is the most efficient way to arrange the given numbers to form the biggest number?.
• Constructing the largest number possible by rearranging a list

C

<lang C>#include <stdio.h>

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

int diglen(int n) {

   int len = 1;
   while (n /= 10) ++len;
   return len;

}

int icsort(const void *px, const void *py) {

   int x = *(int *) px, y = *(int *) py;
   int lx = diglen(x), ly = diglen(y);
   int mx = 10, my = 10; /* magnitudes */

   while (--lx) mx *= 10;
   while (--ly) my *= 10;
   return (y * mx + x) - (x * my + y);

}

long maxcat(int sz, ...) {

   int i, len = 0, off = 0;
   int n, *ns = malloc(sz * sizeof(int));
   char *buf;
   long max;

   va_list va;
   va_start(va, sz);
   for (i = 0; i < sz; ++i) {
       n = va_arg(va, int);
       ns[i] = n;
       len += diglen(n);
   }
   va_end(va);

   buf = malloc(++len);
   qsort(ns, sz, sizeof(int), icsort);

   for (i = 0; i < sz; ++i)
       off += sprintf(buf + off, "%d", ns[i]);
   max = atol(buf);

   free(ns);
   free(buf);
   return max;

}

int main(void) {

   printf("%ld\n", maxcat(8, 1, 34, 3, 98, 9, 76, 45, 4));
   printf("%ld\n", maxcat(4, 54, 546, 548, 60));
   return 0;

}</lang>

Output:

998764543431
6054854654

Perl 6

<lang Perl 6>sub maxnum(@x) {

   [~] sort -> $x, $y { $x~$y <=> $y~$x }, @x

}

say maxnum .[] for [<1 34 3 98 9 76 45 4>], [<54 546 548 60>];</lang>

Output:

998764543431
6054854654

Python

Python: Sort on comparison of concatenated ints method

<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(int(y+x), int(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(int(y+x), int(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 maxnumx(x):

   maxlen = len(str(max(x)))
   return .join(sorted((str(n) for n in x), reverse=True,
                         key=lambda i: i*(maxlen // len(i) + 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 above.

Python: Try all permutations method

<lang python>from itertools import permutations def maxnumx(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.

Ruby

Translation of: Tcl

<lang Ruby>def icsort nums

 nums.sort { |x, y| "#{y}#{x}".to_i - "#{x}#{y}".to_i }

end

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

 puts "#{c}", icsort(c).join

end</lang>

Output:

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

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)