Perl Weekly Challenge number 206 has a task called "Array Pairings" to solve:
You are given an array of integers having even number of elements..
Write a script to find the maximum sum of the minimum of each pairs.
The solution (spoiler alert) is to sort the list and take a slice of every other element. In the Facebook Perl Programming group, Robbie Hatley asks if we can prove that this is the optimal solution. Here's a proof.
Start by sorting the list descending, so that we have
a >= b >= c >= d >= ... x[1] >= x[0]
The first element, a
, will be greater than anything it is paired with, so it will be eliminated from being in the sum. So what shall we pair with a
? There are two choices: we can pair it with b
, or we can pair it with something that is not b
.
Suppose that we pair it with b
. Then the resulting sum will be b + sum(x[i])
, where all the x[i]
are less than or equal to b. Let's call this S1
. The maximum value of S1
will be if all the list elements are equal to b
, so S1 <= b + mb
, where m
is the number of other pairs contributing to the sum.
Now suppose we take the other choice, a number less than (or equal to) b
from further down the sorted list; let's call it x[j]
. The resulting sum, let's call it S2
, will now have a maximum value of S2 <= x[j] + mb
.
S2
must be less than or equal to S1
, because x[j] <= b
. So, our best choice to maximize the sum is to pair a
with b
.
Having disposed of a
and b
, consider the next highest value, c
. The same reasoning applies: d
will be the best choice to pair with c
to maximize the sum. We can proceed down the whole list this way.
The Perl solution is a small function that exploits some language features:
sub arrayPairs($list)
{
my @oddIndex = map { $_ * 2 + 1 } 0 .. int( $#{$list} / 2 );
return sum( (sort { $b <=> $a } $list->@*)[@oddIndex] );
}
-
sub arrayPairs($list)
-- we are using function signatures from Perl 5.36.$list
is a reference to an array of numbers. -
$#{$list}
-- yields the last index of the list (an odd number because we are given that the list has an even number of elements and we index starting from 0). -
0 .. int($#{$list}/2)
-- the range operator generates a list of integers from 0 to half the size of$list
. -
map { $_ * 2 + 1 }
-- applies the code between the braces to each element of the range. This generates the list 1,3,5,... -
$list->@*
-- array postfix dereferencing (catchy name) yields the entire array from a reference. We could have used@$list
, but I've come to use the->
form consistently. -
sort { $b <=> $a }
-- sorts numerically in descending order. This is idiomatic in Perl, using the three-way comparison operator<=>
. The default sort is for strings. -
(sort ...)[]
-- The sort returns a sorted array. Instead of assigning to a temporary variable, we can index directly into the resulting array by enclosing it in parentheses like this. -
(sort ..)[@oddIndex]
-- Using an array as the index selects more than one value (a slice) from the sorted array. I used the list of odd numbers we generated on the previous line. I could have put that expression in-line within the square brackets, but let's concede something to readability. -
sum((sort..)[..])
-- Thesum
function comes from theList::Util
module
Top comments (0)