first of all I have to say that I have the impression that you are trying to reinvent a wheel from graph theory.

Your structure looks for me like a weighted bipartite graph, and you are trying to find a subgraph.

Did you check CPAN for related modules?

> (like python's map of tuples: (x,y) => z)

don't know enough about Python, but this can easily be simulated in Perl with old-style multidim hashes and grepping with a split on the keys.

  DB<116> $index{"A","a"}=1
 => 1

  DB<117> $index{"A","b"}=2
 => 2

  DB<118> $index{"B","a"}=3
 => 3

  DB<119> $index{"B","b"}=4
 => 4

  DB<120> grep { my ($k1,$k2) = split /$;/,$_; $k1 eq "A" } keys %inde
+x 
 => ("A\34a", "A\34b")

  DB<121> %set1=(A=>1)
 => ("A", 1)

  DB<122> %set2=(a=>1)
 => ("a", 2)

  DB<124> grep { my ($k1,$k2) = split /$;/,$_; $set1{$k1} and $set2{$k
+2} } keys %index  
 => "A\34a"
[download]

This brute force search might be elegantš, but for sure not as efficient as looping thru your hierarchical structure.

1) especially when delegating the split to a function called by grep

grep &splitted(\%set1,\%set2) , keys %index

update

added missing keys