If you're dealing with a massive N (like billions that can't be allocated effectively) and small K, here's a quick algorithm:

  my %remap;
  my @result;
  while ($K--) {
    my $x= int rand $N--;
    push @result, $remap{$x} // $x;
    $remap{$x}= $N;
  }
[download]