#!/usr/bin/perl

#
# Secretary Problem Simulation
# - With n secretaries, we interview m of them.
# - After preliminary interviews, we take the next best secretary from the
#   ones we haven't interviewed.
# - What are the odds that when we take the next best secretary it will be
#   the best of the entire group?
#

print "Number of secretaries to be interviewed? "; $n = <STDIN>; chomp($n);
print "Interviews before selections begin? "; $m = <STDIN>; chomp($m);

$t = 10000;		# Trials - takes about one second per 10000 trials


# Initialize $secretary array
for ($j = 1; $j <= $n; $j++) {
  $secretary[$j] = $j;
}

for($i = 0; $i < $t; $i++) {
  # Shuffle routine - exchange n secretary with random secretary, then
  #   the n-1 secretary, then the n-2, etc, until the second secretary.
  # Shuffling the first secretary with itself isn't necessary (which is
  #    why $j > 1, not $j >= 1).
  for($j = $n; $j > 1; $j--) {
    $s = int(rand($j)) + 1;
    $d = $secretary[$s];
    $secretary[$s] = $secretary[$j];
    $secretary[$j] = $d;
  }
  $best = 0;
  # Find the best secretary from the first m candidates
  for($j = 1; $j <= $m; $j++) {
    if($secretary[$j] > $best) {
      $best = $secretary[$j];
    }
  }

  # Start looking through the rest of the secretaries until I either have
  # found a better secretary (denoted as $secretary[$l]) or I've gone
  # through all the secretaries ($l > $n).  If I go through all the
  # secretaries, then $secretary[$l] = $secretary[$n+1] = 0, which is less
  # than all the secretaries.
  $l = $m + 1;
  until(($l > $n) or ($secretary[$l] > $best)) {
    $l++;
  }
  if(($secretary[$l] == $n)) {	# If I'm currently looking at the best
    $c++;                    	#   then increase my counter
  }
}

$p = $c / $t;
print "Odds of getting best secretary: $p\n";
