Traversing a set of hashes

I am trying to do something with hashes that I have not before.

While I am sure it can be done, I can't think of a good way to do it.

Given the following hash:

my %h = (
'first' => {
f0 => 'f_zero',
f1 => 'f_one',
},
'second' => {
s0 => 's_zero',
s1 => 's_one',
}
);

.... print all possible combinations

Easy enough using 2 nested loops.
Four combinations would be printed.

Extend the hash to this:

my %h = (
'first' => {
f0 => 'f_zero',
f1 => 'f_one',
},
'second' => {
s0 => 's_zero',
s1 => 's_one',
}
'third' => {
t0 => 't_zero',
t1 => 't_one',
}
);

This now requires 3 nested loops to get all possible combinations.

The problem is that the number of hashes nested in the %h hash
will not be known until runtime, so hardcoded loops won't work too
well.

Any tips on how to go about this?

TIA

Jared

Re: Traversing a set of hashes

On Nov 20, 4:58 pm, jkstill wrote:
>
> Given the following hash:
>
> my %h = (
> 'first' => {
> f0 => 'f_zero',
> f1 => 'f_one',
> },
> 'second' => {
> s0 => 's_zero',
> s1 => 's_one',
> }
> );
>
> ... print all possible combinations
>
> Easy enough using 2 nested loops.
> Four combinations would be printed.
>
> Extend the hash to this:
>
> my %h = (
> 'first' => {
> f0 => 'f_zero',
> f1 => 'f_one',
> },
> 'second' => {
> s0 => 's_zero',
> s1 => 's_one',
> },
> 'third' => {
> t0 => 't_zero',
> t1 => 't_one',
> }
> );
>
> This now requires 3 nested loops to get all possible combinations.


I don't agree. Both definitions of %h show it to be a hash of
hashes, meaning it will only need an inner loop nested inside an outer
loop (what I'd call one nested loop).

The following code (using only two while() loops) will print out
the contents of %h no matter how many hash entries it contains:

while (my ($key, $value) = each(%h))
{
print "In '$key':\n";
while (my ($key, $value) = each(%$value))
{
print " $key => $value\n";
}
}

Running this code on the hash with three elements will give this
output:

In 'first':
f0 => f_zero
f1 => f_one
In 'second':
s1 => s_one
s0 => s_zero
In 'third':
t0 => t_zero
t1 => t_one

This is what you want, isn't it?

Incidentally, you can easily print out a hash, no matter how many
elements it has or how deep it is, by using the standard Data::Dumper
module. Just use the following in your code:

use Data::Dumper;
print Dumper \%h;

And voila'! You'll see the entire contents of the %h hash.

I hope this helps, Jared.

-- Jean-Luc

Re: Traversing a set of hashes

On Tue, 20 Nov 2007 15:58:39 -0800 (PST) jkstill wrote:

j> I am trying to do something with hashes that I have not before.
j> While I am sure it can be done, I can't think of a good way to do it.
....
j> The problem is that the number of hashes nested in the %h hash
j> will not be known until runtime, so hardcoded loops won't work too
j> well.

Try the CPAN Data::Match module. It's very good for this kind of data
extraction, though it might be too advanced if you are not comfortable
with Perl data structures yet.

Ted

Re: Traversing a set of hashes

Quoth jkstill :
> I am trying to do something with hashes that I have not before.
>
> While I am sure it can be done, I can't think of a good way to do it.
>
> Given the following hash:
>
> my %h = (
> 'first' => {
> f0 => 'f_zero',
> f1 => 'f_one',
> },
> 'second' => {
> s0 => 's_zero',
> s1 => 's_one',
> }
> );
>
> ... print all possible combinations

It's not clear what you mean here by 'combinations'. I'm assuming you
mean 'combinations of values', so the result would be [[f_zero, s_zero],
[f_zero, s_one], [f_one, s_zero], [f_one, s_one]].

> Easy enough using 2 nested loops.
> Four combinations would be printed.

So you do mean what I said... the first thing to realize is that your
data structure should be arrays, not hashes:

[ ['f_zero', 'f_one'], ['s_zero', 's_one'] ]

since you don't make use of the keys.

> Extend the hash to this:
>

>
> This now requires 3 nested loops to get all possible combinations.
>
> The problem is that the number of hashes nested in the %h hash
> will not be known until runtime, so hardcoded loops won't work too
> well.
>
> Any tips on how to go about this?

The first thing that come to (my) mind is recursion, but of course you
can do it with loops as well. You only need three nested loops to handle
any number of cases.

#!/usr/bin/perl -l

use warnings;
use strict;

my %h = (
first => {
f1 => 'f1',
f2 => 'f2',
},
second => {
s1 => 's1',
s2 => 's2',
},
third => {
t1 => 't1',
t2 => 't2',
},
fourth => {
41 => '41',
42 => '42',
43 => '43',
},
);

$, = ',';

print "recurse:";

sub find_combs;

print @$_ for find_combs values %h;

sub find_combs {
my $entry = shift;

my @values = sort values %$entry;
@_ or return map [$_], @values;

my @recurse = find_combs @_;
my @rv;

for my $v (@values) {
push @rv, map [$v, @$_], @recurse;
}

return @rv;
}

print "reduce:";

use List::Util qw/reduce/;

my @lol = map [sort values %$_], sort values %h;
my $first = shift @lol;

our ($a, $b); # silence warnings

print @$_ for @{
reduce { # one...
[
map { # two...
my $tmp = $_;
map [$tmp, @$_], @$a; # three loops
} @$b
]
} [map [$_], @$first], @lol # (this map doesn't count ;) )
};

__END__

Ben

Re: Traversing a set of hashes

On Nov 20, 5:14 pm, "jl_p...@hotmail.com" wrote:
>
> This is what you want, isn't it?

Well, no, not actually.

All possible combinations of the three.
That would be 8 combinations of values each from each of the 3 nested
hashes.

I should have explained more clearly.

Thanks for the reply.

Re: Traversing a set of hashes

Quoth Ben Morrow :
>
> use List::Util qw/reduce/;
>
> my @lol = map [sort values %$_], sort values %h;
> my $first = shift @lol;
>
> our ($a, $b); # silence warnings
>
> print @$_ for @{
> reduce { # one...
> [
> map { # two...
> my $tmp = $_;
> map [$tmp, @$_], @$a; # three loops
> } @$b
> ]
> } [map [$_], @$first], @lol # (this map doesn't count ;) )
> };

Duh, I don't need to special-case the first item, just start with the
appropriate identity. Then it becomes a one-liner (always nice):

print @$_ for @{
reduce {
[
map {
my $tmp = $_;
map [$tmp, @$_], @$a;
} @$b
]
} [ [] ], map [sort values %$_], sort values %h
};

Ben

Re: Traversing a set of hashes

On Nov 20, 5:32 pm, Ben Morrow wrote:
>>
> So you do mean what I said... the first thing to realize is that your
> data structure should be arrays, not hashes:
>
> [ ['f_zero', 'f_one'], ['s_zero', 's_one'] ]
>
> since you don't make use of the keys.

This is just a prototype used to understand how to build something
else.
I need the hashes. :)

>
> The first thing that come to (my) mind is recursion, but of course you
> can do it with loops as well. You only need three nested loops to handle
> any number of cases.
>
>
Excellent! This does exactly what I need.

I'll play with it so I can understand how it works.

Jared