With the brand new Python 2.6, you have a standard solution with the itertools module that returns the Cartesian product of iterables :
import itertools
print list(itertools.product([1,2,3], [4,5,6]))
[(1, 4), (1, 5), (1, 6),
(2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6)]
You can provide a "repeat" argument to perform the product with an iterable and itself:
print list(itertools.product([1,2], repeat=3))
[(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]
You can also tweak something with combinations as well :
print list(itertools.combinations('123', 2))
[('1', '2'), ('1', '3'), ('2', '3')]
And if order matters, there are permutations :
print list(itertools.permutations([1,2,3,4], 2))
[(1, 2), (1, 3), (1, 4),
(2, 1), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 4),
(4, 1), (4, 2), (4, 3)]
Of course all that cool stuff don't exactly do the same thing, but you can use them in a way or another to solve you problem.
Just remember that you can convert a tuple or a list to a set and vice versa using list(), tuple() and set().