Python: Powerset Of A Given Set With Generators
Solution 1:
The fastest way is by using itertools, especially chain and combinations:
>>>from itertools import chain, combinations>>>i = set([1, 2, 3])>>>for z in chain.from_iterable(combinations(i, r) for r inrange(len(i)+1)):
print z
()
(1,)
(2,)
(3,)
(1, 2)
(1, 3)
(2, 3)
(1, 2, 3)
>>>
If you need a generator just use yield and turn tuples into sets:
def powerset_generator(i):
for subset in chain.from_iterable(combinations(i, r) for r in range(len(i)+1)):
yield set(subset)
and then simply:
>>> for i in powerset_generator(i):
print i
set([])
set([1])
set([2])
set([3])
set([1, 2])
set([1, 3])
set([2, 3])
set([1, 2, 3])
>>>
Solution 2:
From the recipes section of the itertools documentation:
def powerset(iterable):
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
Solution 3:
I know this is way too old, but I was looking for an answer to the same problem and after a couple hours of non-successful web searching, I came up with my own solution. This is the code:
defcombinations(iterable, r):
# combinations('ABCDE', 3) --> ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE
pool = tuple(iterable) # allows a string to be transformed to a tuple
n = len(pool)
if r > n: # If we don't have enough items to combine, return Nonereturn
indices = range(r) # Make a set of the indices with length (r)yield [pool[i] for i in indices] Yield first list of indices [0 to (r-1)]
whileTrue:
for i inreversed(range(r)): # Check from right to left if the index is at its# max value. If everyone is maxed out, then finishif indices[i] != i + n - r: # indices[2] != 2 + 5 - 3break# 2 != 4 (Y) then break and avoid the returnelse:
return
indices[i] += 1# indices[2] = 2 + 1 = 3for j inrange(i + 1, r): # for j in [] # Do nothing in this case
indices[j] = indices[j - 1] + 1# If necessary, reset indices to the right of# indices[i] to the minimum value possible.# This depends on the current indices[i]yield [pool[i] for i in indices] # [0, 1, 3]defall_subsets(test):
out = []
for i in xrange(len(test)):
out += [[test[i]]]
for i in xrange(2, len(test) + 1):
out += [x for x in combinations(test, i)]
return out
I took the combinations sample code from itertools doc itertools.combinations and modified it to yield lists instead of tuples. I made annotations when I was trying to figure out how it worked (in order to modify it later), so I'll let them there, just in case someone finds them helpful. Finally, I made all_substes function to find every subset from lengths 1 to r (not including the empty list, so if you need it there just start out as out = [[]]
Post a Comment for "Python: Powerset Of A Given Set With Generators"