OK, I've simplified the code; now it's easier to explain. Here it is:

my @ss =
  map sort_inner( [ keys %{ $_->[ 0 ] } ] ),
  sort { $a->[ 1 ] <=> $b->[ 1 ] }
  map [ $HoHoA{ $_ }, substr( $_, 3 ) ],
  keys %HoHoA;


for my $i ( 0..$#ss-1 ) {
  my $si = $ss[ $i ];
  for my $j ( $i+1..$#ss ) {
    my $sj = $ss[ $j ];

    for my $ki ( @$si ) {
      for my $kj ( @$sj ) {
        print "$ki - $kj\n";
      }
    }

  }
}

sub sort_inner {
  return [
          map $_->[ 0 ],
          sort { $a->[ 1 ] <=> $b->[ 1 ] || $a->[ 2 ] <=> $b->[ 2 ] }
          map [ $_, /\d+/g ],
          @{ $_[ 0 ] }
         ]
}
[download]

Basically the problem entails to solving two subproblems:

1. iterate over all (unordered) pairs of distinct sets of keys;
2. for any pair of sets of keys, generate all possible ordered pairs of members of these sets such that the first member of the pair comes from one set and the second member of the pair comes from the other set.

OK, the inner couple of loops take care of the second subproblem:

    for my $ki ( @$si ) {
      for my $kj ( @$sj ) {
        print "$ki - $kj\n";
      }
    }
[download]

Here @$si and @$sj represent two (suitably sorted) lists of inner keys, and the loops ensure that we get all possible ordered pairs with the first element from @$si and the second one from @$sj.

The other loop handles the first subproblem:

for my $i ( 0..$#ss-1 ) {
  my $si = $ss[ $i ];
  for my $j ( $i+1..$#ss ) {
    my $sj = $ss[ $j ];

    # ...

  }
}
[download]

This runs over all pairs of (sorted) lists ( $ss[ $i ], $ss[ $j ] ) such that 0 ≤ $i < $j < @ss.

The remaining problem is to sort the sets of keys so that the looping above produces the output in the desired order. Two different levels of sorting are required: for each inner hash of %HoHoA the keys need to be sorted to produce a set of sorted keys; and these sets of sorted keys must be stored in the right order in the array @ss. The code does this with a pair of nested Schwartzian transforms. The inner one encapsulated in the function sort_inner, which sorts the elements of the input array according to the two numbers contained in each key. These two numbers are extracted via the regular expression /\d+/g evaluated in a list context. The actual sort function is

{ $a->[ 1 ] <=> $b->[ 1 ] || $a->[ 2 ] <=> $b->[ 2 ] }
[download]

which sorts array refs numerically according to their second elements, or, in case of ties, their third elements (the first element is the typical ST payload).

The outer ST is

my @ss =
  map sort_inner( [ keys %{ $HoHoA{ $_->[ 0 ] } } ] ),
  sort { $a->[ 1 ] <=> $b->[ 1 ] }
  map [ $_, substr( $_, 3 ) ],
  keys %HoHoA;
[download]

The keys are sorted numerically on the substring obtained by removing the first 3 characters (i.e. the word "set"). (I could have just as well used the same /\d+/g construct as before.) The only non-standard aspect of this ST is that the last step, instead of simply extracting the payload with $_->[ 0 ] as before, it does one further transformation on it (more about this in a minute). It is equivalent to the more usual looking ST

my @tmp =
  map $_->[ 0 ],
  sort { $a->[ 1 ] <=> $b->[ 1 ] }
  map [ $_, substr( $_, 3 ) ],
  keys %HoHoA;
[download]

followed by one more map map:

my @ss = map sort_inner( [ keys %{ $HoHoA{ $_ } } ] ), @tmp;
[download]

I'v just collapsed these two steps to eliminate the intermediate @tmp array.

The transformation given by the expression

sort_inner( [ keys %{ $HoHoA{ $k } } ] )
[download]

returns an array ref the keys of the inner hash corresponding to $HoHoA{ $k }, but sorted by sort_inner.

In the end, @ss is just an AoA. Or rather, it is a SAoSA: a sorted array of sorted arrays.