% filterOrder 1.9 1.8 2.9 2.8 3.9 3.8 4.9 4.8 30.1 20.2 10.3
1 .8, 1 .9, 2 .8, 2 .9, 3 .8, 3 .9, 30 .1, 10 .3, 4 .8, 4 .9, 20 .2,
0.002 19.00391 ( 0 1 2 3 4 5 6 7 8 9 10 )
0.100 12.88756 ( 0 1 2 7 4 8 3 10 5 6 9 ) 9
1 .8, 1 .9, 2 .8, 10 .3, 3 .8, 4 .8, 2 .9, 20 .2, 3 .9, 30 .1, 4 .9,
3.750 seconds
####
1 .8, 1 .9, 2 .8, 2 .9, 3 .8, 3 .9, 30 .1, 10 .3, 4 .8, 4 .9, 20 .2
| | | \+3 | \+3 \+3 /-3 /-3 \+1 /-3
| | | |
| | | /+3 | /+3 \-3 /+3 \-3 \-3 \-1
1 .8, 1 .9, 2 .8, 10 .3, 3 .8, 4 .8, 2 .9, 20 .2, 3 .9, 30 .1, 4 .9
##
##
#!/usr/bin/perl -w
use strict;
use Time::HiRes qw< time >;
$| = 1;
my( @Costs, @Trims );
for( @ARGV ) {
my( $cost, $trim ) = /^(\d+)(\.\d+)$/ or die "Invalid cost.trim: $_\n";
push @Costs, $cost;
push @Trims, $trim;
}
my $Start = time();
my @order = sort {
$Trims[$a]*$Costs[$a] <=> $Trims[$b]*$Costs[$b]
} 0..$#Costs;
@Trims = @Trims[@order];
@Costs = @Costs[@order];
print " $Costs[$_] $Trims[$_],"
for 0..$#Costs;
print $/;
my @Win;
cost( \@Costs, \@Trims );
print $/;
print " $Costs[$_] $Trims[$_],"
for @Win;
printf "\n%.3f seconds\n", time() - $Start;
sub NextPermuteNum(\@)
{
my( $vals )= @_;
my $last= $#{$vals};
return !1 if $last < 1;
while( 1 ) {
# Find last item not in reverse-sorted order:
my $i= $last-1;
$i-- while 0 <= $i && $vals->[$i+1] <= $vals->[$i];
# If complete reverse sort, we are done!
if( -1 == $i ) {
# Reset to starting/sorted order:
@$vals= reverse @$vals;
return !1;
}
# Re-sort the reversely-sorted tail of the list:
@{$vals}[$i+1..$last]= reverse @{$vals}[$i+1..$last]
if $vals->[$last] < $vals->[$i+1];
# Find next item that will make us "greater":
my $j= $i+1;
$j++
while $vals->[$j] <= $vals->[$i];
do {
# Swap:
@{$vals}[$i,$j]= @{$vals}[$j,$i];
# If "greater" item isn't strictly worse than try it:
return 1
if $Costs[$vals->[$i]] < $Costs[$vals->[$j]]
|| $Trims[$vals->[$i]] < $Trims[$vals->[$j]];
# Else, we picked a strictly worse one, so pick again
$j++;
} while( $j <= $last );
# Force us to move back to at least $i-1:
@{$vals}[$i..$last] = sort { $b <=> $a } @{$vals}[$i..$last];
}
}
sub cost {
my( $costs, $trims ) = @_;
my @order = 0 .. $#$costs;
my $best = 0;
my $max = 0;
do {
my $size = 1;
my $cost = 0;
my $skip = @order;
for my $i ( @order ) {
$skip--;
last
if $best && $best < $cost;
$cost += $size * $costs->[$i];
$size *= $trims->[$i];
}
if( ! $best || $cost <= $best ) {
printf "\r%.3f %.5f ( %s )",
time() - $Start, $cost, "@order";
print $/
if ! $best;
@Win = @order;
$best = $cost;
$max = 0;
} elsif( 1 < $skip ) {
if( $max < $skip ) {
printf "%4d\b\b\b\b", $skip;
$max = $skip;
}
@order[$#order-$skip+1..$#order] = sort { $b <=> $a }
@order[$#order-$skip+1..$#order];
}
} while( NextPermuteNum(@order) );
}