Task — Largest number

You are given a list of positive integers, @ints. Write a script to arrange all the elements in the given list such that they form the largest number and return it.

Examples

Example 1
Input: @ints = (20, 3)
Output: 320

Example 2
Input: @ints = (3, 30, 34, 5, 9)
Output: 9534330

Analysis

For at least 90% of randomly selected @ints the answer is simply

join('', reverse(sort(@ints)))

which is very fast even for a large number of @ints.

However, just occasionally, that doesn't work, and example 2 above is one such case, where 3, 34, 30 reverse sorts as 34, 30, 3, but 34303 is smaller than 34330, which is the correct answer.

The condition where the reverse sort doesn't work is where two consecutive numbers A and B in the reverse swap meet the condition that B sorts lexicographically after A. For example if A = 80 and B = 8, A sorts after B but 880 is numerically greater than 808.

My solution therefore first reverse sorts @ints, and then works backwards along the sorted array, comparing consecutive pairs of numbers and swapping them if they meet the 'doesn't work' condition stated above.

Just in case my logic is faulty I have included a check by generating all the permutations of @ints and finding the largest, and you can see from my examples that my algorithm works, and it is of course increasingly faster than generating the permutations if the size of @ints is larger than about 8.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-12-23
use utf8;     # Week 301 - task 1 - Largest number
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Algorithm::Combinatorics 'permutations';

largest_number(3, 30, 34, 5, 9);

# generate random sets with varying lengths of numbers
my (@ints, $j, $n, $k);
for $j (0 .. 10) {
    @ints = ();
    for $k (0 .. 7) {
        $n = int(rand(7));
        push @ints, int(rand(10 ** $n));
    }
    largest_number(@ints);
}

sub largest_number {
    
    my (@ints, $iter, $largest, $number, $perm, 
        $j, $park, $len_a, $len_b, $largest2);
    
    # initialise
    @ints = @_;
    say qq[\nInput:  \@ints = (] . join(', ', @ints) . ')';
    
    $iter = permutations(\@ints);
    $largest = 0;
    
    # find largest by permutations
    while ($perm = $iter->next) {
        $number = join('', @$perm);
        $largest = $number if $number gt $largest;
    }
    
    # find largest by swaps (much faster!)
    @ints = reverse sort @ints;

    for ($j = $#ints - 1; $j >= 0; $j --) {
        next unless ($ints[$j + 1] . $ints[$j]) gt ($ints[$j] . $ints[$j + 1]);
        
        # swap two of @ints
        $park = $ints[$j];
        $ints[$j] = $ints[$j + 1];
        $ints[$j + 1] = $park;  
    }

    $largest2 = join('', @ints);
    my $f = $largest eq $largest2 ? '' : 'mismatch!';
    
    say qq[Output: by perms $largest];
    say qq[        by swaps $largest2 $f];
}

Output

Input:  @ints = (3, 30, 34, 5, 9)
Output: by perms 9534330
        by swaps 9534330

Input:  @ints = (9411, 0, 66587, 2, 2384, 6394, 6689, 
     771)
Output: by perms 94117716689665876394238420
        by swaps 94117716689665876394238420

Input:  @ints = (0, 51050, 142158, 65, 9710, 3, 71, 1)
Output: by perms 9710716551050314215810
        by swaps 9710716551050314215810

Input:  @ints = (94, 3878, 77703, 0, 489, 2255, 605535, 
     66702)
Output: by perms 947770366702605535489387822550
        by swaps 947770366702605535489387822550

Input:  @ints = (8, 7, 60, 319, 0, 0, 8, 2716)
Output: by perms 88760319271600
        by swaps 88760319271600

Input:  @ints = (3939, 0, 83, 165422, 105, 4934, 6406, 
     84)
Output: by perms 84836406493439391654221050
        by swaps 84836406493439391654221050

Input:  @ints = (109595, 9, 130, 861992, 47988, 97755, 
     175580, 60)
Output: by perms 9977558619926047988175580130109595
        by swaps 9977558619926047988175580130109595

Input:  @ints = (4, 852945, 884407, 0, 95508, 0, 825849, 
     77744)
Output: by perms 9550888440785294582584977744400
        by swaps 9550888440785294582584977744400

Input:  @ints = (68632, 3, 21, 575309, 35, 60006, 243961, 
     0)
Output: by perms 6863260006575309353243961210
        by swaps 6863260006575309353243961210

Input:  @ints = (8, 934867, 42678, 946982, 1, 4, 0, 0)
Output: by perms 9469829348678442678100
        by swaps 9469829348678442678100

Input:  @ints = (5664, 155, 282826, 3, 713866, 442, 0, 
     944210)
Output: by perms 944210713866566444232828261550
        by swaps 944210713866566444232828261550

Input:  @ints = (95418, 5, 0, 30772, 327714, 8790, 5, 
     159)
Output: by perms 95418879055327714307721590
        by swaps 95418879055327714307721590