Jeff Aa wrote at Wed, 18 Sep 2002 18:56:52 +0200:
> Your analysis is interesting. I am no mathemagician either, but it
> occurs to me that it would be easy to code your analysis more
> efficiently than using the sum rank, something like this: (not
> debuggered)
>
> use strict;
>
> # Note that this array must be sorted ascending
> my @numbers = (1,4,9,16,25,36,49,64,81);
>
> # How many groups will we create?
> # What do we do if there are not exactly three numbers
> # per group??
> my $iterations = integer (scalar @numbers / 3);
You meant my $iterations = int( scalar @numbers / 3 );
(However, the scalar cast isn't necessary)
my $iterations = int(@numbers/3);
> my @groups;
> foreach my $i ( 1..$iterations ) {
> my @group;
> # put the smallest and biggest value into groups
> push @group, pop( @numbers ), shift( @numbers );
> push @groups, \@group;
> }
Or shorter
my @groups = map { [pop(@numbers), shift(@numbers)] } ( 1 .. $iterations );
>
> # Now we have to decide which group can best use the
> # remaining numbers. Process the groups from biggest
> # to smallest, adding the smallest available value
> foreach my $group ( sort { $b[0]+$b[1] <=> $a[0]+$a[1] } @groups ) {
^^^^^
Well, should be perhaps better
$b->[0]+$b->[1] <=> $a->[0]+$a->[1]
and in future perhaps a Schwartzian Transformation will increase the speed.
> push @$group, pop @numbers;
> }
>
> # @groups now is an array of balanced tuplets! hoorah.
Well, that works with my example.
And in fact it works much better than my rank sum algorithm,
wich is wrong (I tried it now with the n^3 numbers,
and it's a real danger).
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";
}
Greetings,
Janek
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
