artist has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks
How do I select a key from a hash randomly without converting to an array?. The important thing is that the randomness should take care of frequncy of the keys which is provided by value in the hash. 

$hash->{a} = 30;
$hash->{b} = 20;
$hash->{c} = 10;
my $string;
foreach (1..30){
my $element = randomKey($hash);
$string .= $element;
}

[download]
$string in the above case should contain approximately 15 'a', 10 'b' and '5' a.

I can always do : 

my @array;
foreach $key (keys %{$hash}){
  foreach $value($hash->{$key}){
  push @array,  $key;
 }
}

[download]
and then select random element from the @array; I am looking for the solution in which I don't need to build a big array

Thanks
Artist

Replies are listed 'Best First'.
Re: Random Hash Key according to key frequency
by jdporter (Paladin) on Dec 04, 2002 at 18:28 UTC 
      my @thresh;
  my $total = 0;
  for ( keys %hash )
  {
    $total += $hash{$_};
    push @thresh, [ $total, $_ ];
  }

  my $string;
  for ( 1 .. 30 )
  {
    my $r = rand $total;
    my $i = 0;
    while ( $r > $thresh[$i][0] ) { $i++; }
    $string .= $thresh[$i][1];
  }

    [download]

    jdporter
    ...porque es dificil estar guapo y blanco.

[reply]
[d/l]
      It is possible to do it without constructing the threshold array by stepping through the hash a second time. 
      my $total = 0;
foreach my $key (keys %hash) {
    $total += $hash->{$key};
}

my $r = int(rand($total));

my $sum = 0;
foreach my $key (keys %$hash) {
    $sum += $hash->{$key};
    if ($r < $sum) 
        return $key;
}

      [download]
      It might be possible to do only one pass through the hash using a technique like finding a random line from a file when the number of lines in the file isn't known.
[reply]
[d/l]
        It might be possible to do only one pass through the hash using a technique like finding a random line from a file when the number of lines in the file isn't known.

        What... like this :-)

        sub random_key {
    my $hash = shift;
    my $line = 0;
    my $match = undef;
    while (my ($key, $value) = each %$hash) {
        $match = $key if rand($line += $value) < $value;
    };
    return($match);
};

        [download]

        Update: removed unnecessary inner loop.

[reply]
[d/l]
[reply]
Re: Random Hash Key according to key frequency
by BrowserUk (Patriarch) on Dec 05, 2002 at 00:02 UTC

    A one-liner.

    Probably wouldn't win any prizes for efficiency, but scrunched up, it might come in handy in a golf-tournement someday. 

    my $choice = do {@_ = (); @_ = (@_, map{ ($_->[0]) x $_->[1] } [$a,$b]
+) while ($a,$b)= each %hash; $_[rand @_]};

    [download]

    And to prove it works, a one-line test suit. 

    perl -e"%h=(a=>200,b=>20,c=>2);$t{do{@_=();@_=(@_,map{($_->[0])x$_->[1
+]}[$a,$b]) while($a,$b)=each%h;$_[rand@_]}}++ for 1..1000;print%t;"

a901b86c13

    [download]

    Note: I added an unnecessary space to prevent PM from wrapping it at a less convenient place. It (just) fits on one line on my command line.

    Okay you lot, get your wings on the left, halos on the right. It's one size fits all, and "No!", you can't have a different color.
    Pick up your cloud down the end and "Yes" if you get allocated a grey one they are a bit damp under foot, but someone has to get them.
    Get used to the wings fast cos its an 8 hour day...unless the Govenor calls for a cyclone or hurricane, in which case 16 hour shifts are mandatory.
    Just be grateful that you arrived just as the tornado season finished. Them buggers are real work.

[reply]
[d/l]
[select]
Re: Random Hash Key according to key frequency
by traveler (Parson) on Dec 04, 2002 at 21:36 UTC
    While it takes parameters in a different form, I think you can use Randomize. If you check the module docs, it seems to do exactly what you want.

    HTH, --traveler

[reply]
[d/l]

Back to Seekers of Perl Wisdom