If you don't care about the order of the results, you can use a Gray code (http://en.wikipedia.org/wiki/Gray_code): this has the advantage of only adding or removing a single element to get from one subset to the next.
def powerset(s): d = dict(zip( (1<<i for i in range(len(s))), (set([e]) for e in s) )) subset = set() yield subset for i in range(1, 1<<len(s)): subset = subset ^ d[i & -i] yield subset >>> list(powerset('abc')) [set([]), set(['a']), set(['a', 'b']), set(['b']), set(['c', 'b']), set(['a', 'c', 'b']), set(['a', 'c']), set(['c'])] If you're using the subsets as they appear and don't need to store them all at once, then it's significantly faster (on my machine) if you replace the line subset = subset ^ d[i & -i] with an in-place update: subset ^= d[i & -i]. Mark -- http://mail.python.org/mailman/listinfo/python-list