this would require a recalculation of the @weights and $total after each pick in order to avoid getting the same pick repeatedly

Yes, but:

1. Recalculating the total is: $total -= $weights[ $pick ]; which is hardly onerous.
2. Recalculating @weights is just: $weights[ $pick ] = 0;

   If you set the weight of the previous pick to 0, it'll never get picked again.

So, to pick them all in a random order, you pick the first, subtract its weight from the total, set it weight to 0 and pick again. Repeat for N:

sub pickAll{
    my @weights = @_;
    my $total = sum @weights;
    my @order;
    for( 0 .. $#_ ) {
        my $pick = pick( \@weights, $total );
        push @order, $pick;
        $total -= $weights[ $pick ];
        $weights[ $pick ] = 0;
    }
    return @order;
}
[download]

Putting it all together you get:

#! perl -slw
use strict;
use List::Util qw[ sum ];

our $SHIPS ||= 10;
our $REPS ||= 1e5;

sub pick {
    my( $weights, $total ) = @_;
    my $rand = rand $total;
    ( $rand -= $weights->[ $_ ] ) < 0 
        and return $_ for 0 .. $#$weights;
}

sub pickAll{
    my @weights = @_;
    my $total = sum @weights;
    my @order;
    for( 0 .. $#_ ) {
        my $pick = pick( \@weights, $total );
        push @order, $pick;
        $total -= $weights[ $pick ];
        $weights[ $pick ] = 0;
    }
    return @order;
}

my @weights = map rand( 16 ), 1 .. $SHIPS;
print "$_ : $weights[ $_ ]" for 0 .. $#weights;

my $total = sum @weights;

print "\n";

print join ' ', pickAll( @weights ) for 1 .. $REPS;
[download]

I just spent a couple of hours trying to work out how to demonstrate that this results in a properly weighted distribution, but it's beyond me today. But by cherry picking a couple of runs, I think you can see it at work:

In this run you can see that ship 1 has a much lower weighting whilst the other three are very similar. With the result that the first ships 0,2 & 3 are pretty evenly distributed in the first 3 places, and ship 1 is (almost) always picked last:

C:\test>WeightedPick.pl -SHIPS=4 -REPS=30
0 : 14.4176797792315
1 : 1.80334489420056
2 : 14.493153475225
3 : 14.258566647768

3 2 0 1
3 0 2 1
0 3 2 1
0 3 1 2
0 3 2 1
0 2 3 1
3 2 0 1
0 2 3 1
3 0 2 1
1 0 3 2
3 2 0 1
3 0 2 1
0 3 2 1
3 0 2 1
3 0 2 1
0 2 3 1
3 1 2 0
2 3 0 1
2 0 3 1
3 2 0 1
0 3 2 1
2 3 0 1
3 0 2 1
3 2 0 1
2 3 0 1
2 3 1 0
3 0 2 1
0 2 1 3
3 2 0 1
0 2 3 1
[download]

In this run, ship 3 is weighted roughly twice ship 1 which is roughly twice ship 2; whilst ship 0 is almost not there. With the result that the first two picks are mostly 1s and 3s; the 3rd pick is mostly 2s and the last pick mostly 0s:

C:\test>WeightedPick.pl -SHIPS=4 -REPS=30
0 : 0.762649480253458
1 : 10.0145217105746
2 : 6.81761548668146
3 : 15.7317210100591

1 3 2 0
1 2 3 0
2 1 3 0
3 1 2 0
3 2 1 0
2 1 3 0
3 1 2 0
1 3 2 0
3 1 2 0
1 2 3 0
1 3 2 0
1 3 2 0
3 1 2 0
1 3 2 0
1 3 2 0
2 1 3 0
2 3 1 0
1 3 2 0
3 1 2 0
2 3 1 0
2 3 1 0
1 2 3 0
3 1 2 0
3 1 2 0
2 3 1 0
3 1 2 0
2 3 1 0
1 3 0 2
3 1 2 0
3 1 2 0
[download]

If any of the math gurus want to show me how to check the distributions arithmetically, I'm all ears :)

Also, I think the big-O rating is: O( 2n + n(n-1)/4 ). Can anyone verify that for me?

Nothing to add but a perl6 version that currently works under Rakudo

use v6;

our $SHIPS = 4;
our $REPS  = 30;

my @weights = list(1..$SHIPS).map: { 1+16.rand.int };
for @weights.kv -> $k, $v { say "$k: $v" }

my $total = [+] @weights;
say "Total Weights $total";

sub pick (@weights, $total) {
   my $rand = $total.rand.int;
   for @weights.kv -> $i, $w {
       $rand -= $w;
       return $i if $rand < 0;
   }
}

sub pickAll (@w,$t) {
   my @weights = @w.clone; my $total = $t.clone;  #a hack until "is co
+py" gets implemented
   my @order;
   for @weights {
        my $pick = pick(@weights, $total);
        @order.push($pick);
        $total -= @weights[$pick];
        @weights[$pick] = 0;
   }
   return @order;
 }

pickAll(@weights,$total).join.say for 1 .. $REPS;
[download]


___________
Eric Hodges

This is a case of a Drunkard's walk, and as such the deviation from expectation value is proportional to sqrt(N). With 30 steps, you have a 96% confidence interval of 37% deviation from expectation, 10^4 realizations will give you a 96% confidence interval of 2%. I wrote some code to lump results and stuck it on the end of BrowserUk's; for the results the first column should correspond closely to the weights vector. The following is for 10 ships and 10^5 reps

#! perl -slw
use strict;
use List::Util qw[ sum ];

our $SHIPS ||= 10;
our $REPS ||= 1e5;

sub pick {
    my( $weights, $total ) = @_;
    my $rand = rand $total;
    ( $rand -= $weights->[ $_ ] ) < 0 
        and return $_ for 0 .. $#$weights;
}

sub pickAll{
    my @weights = @_;
    my $total = sum @weights;
    my @order;
    for( 0 .. $#_ ) {
        my $pick = pick( \@weights, $total );
        push @order, $pick;
        $total -= $weights[ $pick ];
        $weights[ $pick ] = 0;
    }
    return @order;
}

my @weights = map rand( 16 ), 1 .. $SHIPS;
my $total = sum @weights;
$weights[$_] /= $total for 0 .. $SHIPS-1;

print "$_ : $weights[ $_ ]" for 0 .. $#weights;

print "\n";

my @results;
for (1 .. $SHIPS) {
    push @results, [0 x $SHIPS]; # $results[ship][pick location]
}
for (1 .. $REPS) {
    my @realization = pickAll( @weights );
    for (0 .. $SHIPS-1) {
        ++$results[$realization[$_]][$_];
    }
}
for (@results) {
    for (@{$_}) {
        $_ /= $REPS;
    }
}
print sprintf "%.4f " x $SHIPS, @{$_} for @results;

C:\test>WeightedPick.pl -SHIPS=10 -REPS=100000

0 : 0.156588763610903
1 : 0.0946606629807576
2 : 0.0327748134913928
3 : 0.100654289094377
4 : 0.162546174460996
5 : 0.135885704628311
6 : 0.135469229097757
7 : 0.0780801081629204
8 : 0.0401747990052874
9 : 0.0631654554672976


0.1574 0.1495 0.1394 0.1308 0.1174 0.1041 0.0857 0.0629 0.0386 0.0143 
0.0938 0.0970 0.1014 0.1043 0.1110 0.1138 0.1147 0.1123 0.0974 0.0543 
0.0330 0.0373 0.0398 0.0467 0.0533 0.0651 0.0830 0.1115 0.1781 0.3523 
0.0993 0.1032 0.1067 0.1089 0.1115 0.1134 0.1129 0.1085 0.0882 0.0474 
0.1632 0.1523 0.1434 0.1296 0.1176 0.1005 0.0845 0.0602 0.0359 0.0129 
0.1350 0.1332 0.1295 0.1261 0.1177 0.1107 0.0981 0.0784 0.0507 0.0205 
0.1364 0.1330 0.1297 0.1257 0.1176 0.1098 0.0952 0.0792 0.0517 0.0216 
0.0782 0.0822 0.0864 0.0927 0.1012 0.1078 0.1191 0.1279 0.1230 0.0815 
0.0408 0.0451 0.0507 0.0552 0.0635 0.0740 0.0922 0.1232 0.1863 0.2690 
0.0629 0.0672 0.0732 0.0800 0.0892 0.1007 0.1147 0.1360 0.1500 0.1262
[download]