Suppose you have a list of the diameters of some circular holes, and a list of the diameters of some cylindrical pegs. Now the problem is finding all the ways you can fit the pegs in the holes, where the order in which you put them in doesn't matter, and it's OK to put a peg in a hole that's too large.
I've written the code below to solve the problem, and it works as intended. The innermost tuples of the answer matches a peg to a hole, i.e. (4, 7) means put d4 peg in d7 hole, and these tuples make up a set that represents one way of putting all the pegs in.
I'm not completely happy with the solution. It's not... snappy enough, and it feels overly complicated. Is there a smarter way to go about it?
def fit(pegs, holes): for h in holes: for p in pegs: if p <= h: pegs_left = [x for x in pegs if x != p] if pegs_left: free_holes = [x for x in holes if x != h] for rest in fit(pegs_left, free_holes): yield frozenset(((p, h),)) | rest else: yield frozenset(((p, h),)) def fitted(pegs, holes): return sorted(sorted(x) for x in set(fit(pegs, holes))) pegs = [2, 4, 7] holes = [1, 3, 4, 6, 9] print fitted(pegs, holes) # [[(2, 3), (4, 4), (7, 9)], # [(2, 3), (4, 6), (7, 9)], # [(2, 4), (4, 6), (7, 9)], # [(2, 6), (4, 4), (7, 9)]]