-----Original Message-----
From: Janek Schleicher [mailto:[EMAIL PROTECTED]]
Sent: 18 September 2002 18:32
To: [EMAIL PROTECTED]
Subject: RE: lots of numbers...
> You meant my $iterations = int( scalar @numbers / 3 );
> (However, the scalar cast isn't necessary)
>
> my $iterations = int(@numbers/3);
Thanks for the correction! I miss my old 'div' operator for integer
division from languages past 8-)
> Or shorter
> my @groups = map { [pop(@numbers), shift(@numbers)] } ( 1 ..
$iterations );
also nice.
> But could it be, we missed the simplest, but acceptable algorithm:
>
> my @number = sort {$a <=> $b} @ARGV;
>
> use List::Util qw/sum/;
> my @group;
> my $sum = sum @number; # @number is already sorted
> my $avg = 3 * $sum / @number; # wanted avg for each group
> while (@number >= 3) {
> my $diff_to_avg = $avg - sum (my ($min,$max) = (shift @number, pop
@number));
>
> my $i = 0; # index of the number nearest to the missing gap
for the wanted avg
> foreach (1..$#number) { # perhaps a binary search or smth else
will be quicker
> $i = $_ if abs($diff_to_avg-$number[$_]) <
abs($diff_to_avg-$number[$i]);
> }
>
> push @group, [$min, splice(@number, $i, 1), $max];
> }
>
> push @group, \@number if @number; # if there are some numbers left
>
> foreach (@group) {
> print join " ", @$_, "avg", (sum(@$_) / @$_);
> print "\n";
> }
mmm - looks like a more complex approach to me?
The point of the first approach was to create approximate groups using
the smallest and largest values in a quick first pass. The bulk of the
work is easily performed. The second and final pass using the sorted
partial groups and the sorted remaining values will always associate the
best available value with the right partial group.
I think this would also be easier to extend to groups of more than three
numbers - you just extend the initial approximation pass to group more
numbers from either end. It gets a little more interesting when the
desired number of elements in a group is even, as you cant just blindly
grab both ends.
Using a sort feels simpler than calculating a target average and
iterating through all remaining numbers to see which value will bring
the partial group closest to the desired target. Remember that @numbers
is already sorted. I would guess that the 'calc a target and search for
best fit' algorithm actually does more work as coded above, consider
that it creates one partial group, and then searches through all
remaining numbers for the best fit. It then creates a second partial
group, and searches through all remaining numbers for the best fit, etc
etc etc.
Nighty nite!
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
