Generating list's subsets

03 December 2013

Once a month a “how to generate all subsets in python” question appers on stackoverflow.

The OP (“Original poster”) of the question apparently found an itertools based implementation.

But what he really looked for is an algorithm to create all the subsets.

There are fewer solutions on stackoverflow that implements the naive alogrithm in python.

Unfortuntally I couldn’t find the awesome and elegant original post, but I rewrote it somehow and post it here.

The naive implementation:

def naiveSubsetGen(s):
	subsets = [[]]
	for i in s:
		subsets = subsets + [[i] + j for j in subsets]
	return subsets

The itertools solution:

from itertools import combinations

def itertoolsSubsetGen(s):
	return [[]] + [list(j) for i in range(len(s)) for j in combinations(s, i+1)]

I benchmarked both of them:

itertoolTestStr=\
"""
for i in xrange(5,25,5):
	itertoolsSubsetGen(range(i+1))
"""

naiveTestStr=\
"""
for i in xrange(5,25,5):
	naiveSubsetGen(range(i+1))
"""

setupItertool = """from __main__ import itertoolsSubsetGen"""
setupNaive = "from __main__ import naiveSubsetGen"
if __name__=='__main__':
	import timeit
	print "naive time:", timeit.timeit(naiveTestStr, setup=setupNaive, number=4)
	print "itertools time:",timeit.timeit(itertoolTestStr, setup=setupItertool, number=4)

Results:

naive time: 8.25990605354
itertools time: 12.5649080276

Generating list's subsets - Python

Results: