# @key_set and @val_set are my names for @A1 and @A2
# there is no need to shuffle them!

my %pairs;
my $size = 100;  # from the user
until (keys(%pairs) == $size) {
  my $key = $key_set[rand @key_set];
  my $val = $val_set[rand @val_set];
  $pairs{"$key-$val"} = 1;

  # or even just:
  # $pairs{$key_set[rand @key_set] . "-" . $val_set[rand @val_set]} = 1;
}

for (keys %pairs) {
  print "$_\n";
}