all the ways to fit some pegs into given holes
I recommend against using single letter variable names, in particular your use of p and h. 
I think the code is clearer if you use peg and hole. 
Your code is going to break if you have multiple holes or pegs of the same size.
You'd be better off using tuples instead of frozensets. You don't appear to be using the set features.


In order to have better code/algorithm you need to look at the problem differently. Right now you are trying to find peg/hole combinations. Instead, you should try to figure out where each peg fits. 

You have the pegs: 2, 4, 7

Your goal is to select three of the holes: 1, 3, 4, 6, 9 which fit the pegs.

itertools.permutations(holes, 3)


will produce an iterator over all possible choices of 3 holes from the list. Something like:

1 3 4
1 3 6
1 3 9
1 4 3
...


We interpret each value as an assignment of holes to pegs. So 1,3,4 means (2, 1), (4, 3), (7,4). Of course not all such assignments are valid. So we filter out the invalid ones (i.e. where the pegs don't fit). 

As an added bonus, itertools.permutations generates its values in sorted order. Because we only filter the results, the resulting function will also produce its values in sorted order. This removes the neccesity of doing the sorting yourself.

Here is my implementation:

import itertools

def check_fits(pegs, holes):
    for peg, hole in zip(pegs, holes):
        if peg &gt; hole:
            return False
    return True

def fit(pegs, holes):
    assert len(pegs) &lt;= len(holes)
    for selected_holes in itertools.permutations(holes, len(pegs)):
        if check_fits(pegs, selected_holes):
            yield zip(pegs, selected_holes)

pegs = [2, 4, 7]
holes = [1, 3, 4, 6, 9]

for item in fit(pegs, holes):
    print item


itertools.permutations will generate many invalid assignment of pegs to holes. For example, in the example above, it will generate a significant number of assignment which attempt to fit a peg of size 2 into a hole of size 1. A simple recursive function could avoid spending time on so many bad assignments. However, itertools.permutation is written in C, and so probably still has a speed advantage over such a recursive algorithm.