Add powerset_of_sets() #820
Description
The existing powerset() recipe yields tuples. If actual sets are needed, the obvious extension map(set, powerset(iterable)), does not perform well because the __hash__() method is called n * 2**(n-1) times.
A better approach is to create sets of size 1 and them merge them as needed with set.union which reuses the hash values cached in the input sets.
def powerset_of_sets(iterable):
"Return sets of a powerset calling hash() only once per element."
# powerset_of_sets([1,2,3]) --> set() {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}
sets = list(map(set, zip(iterable)))
for r in range(len(sets) + 1):
yield from starmap(set().union, combinations(sets, r))
Demonstration:
from fractions import Fraction
class F(Fraction):
def __hash__(self):
"Print a dot every time hash is called"
print('.', end='')
return super().__hash__()
>>> _ = list(map(set, powerset(map(F, range(5)))))
................................................................................
>>> _ = list(map(set, powerset_of_sets(map(F, range(5)))))
.....