|
The normal iterative approach: def power_set(inp_set):
. B E8 K1 c9 d2 l/ L& I result = [[]]! o6 n* _! H( x3 g% Z' c5 }
l/ ?9 u" }$ q! p for ele in inp_set:
, C0 x; K0 q0 O( n/ P8 C newSubSets = [subset + [ele] for subset in result] # this step is responsible for combining each element to every other element in the already existing power set
# a1 T4 a! @; u result.extend(newSubSets)0 B, K. j1 q9 f; G, _
% J% t; g9 X5 W return result
The most famous bit manipulation technique def power_set3(inp_set):: @6 W( h) a- e M
pwr_set_size = 2 ** len(inp_set)
% J5 N! s3 h; q+ U pwr_set = [[]]" B! {( @! D" {
/ k/ }4 I3 }$ {
for i in range(pwr_set_size):, D: @" [6 h. Q, l; \/ d: W
new_set = []
# |$ X' W: D# D; Q4 Q; A for j in range(len(inp_set)):
& `; o: b# C( U- i1 q8 Y. R if i & 1 << j : # this is to check if the jth bit is set or not8 [3 D; a" z7 L; I6 A4 i' E7 T
new_set.extend([inp_set[j]])* {/ @: ~8 {: u% o9 [. Q% A
4 r% V4 l8 j5 }* y0 V; Q pwr_set.append(new_set)+ s( Q( W( a: L6 Z/ Y4 j
4 z! B7 v# n( o2 S9 u0 U( u0 [) K6 ?
return pwr_set
There could be a recursive definition which is a little tricky: def power_set2(inp_set, new_set):
3 i/ v5 t6 s7 L7 \" d/ D: X: a if inp_set == []:
0 ]- Z6 P) L3 \/ t return [new_set]
7 P) l1 g% k! j* o; Z( S. u else:
3 G0 l1 B0 r; A result = []) P" b% w/ s' n( n
for ele in power_set2(inp_set[1:],new_set + [inp_set[0]]): # generate all subsets which has the first element$ u' O" }* a' H% N. E
result.append(ele)
9 z6 X! o7 L8 {- S0 M w( F9 h$ H+ E. j8 n- Y$ K5 K- Q6 X a
for ele in power_set2(inp_set[1:], new_set): #generate all the subsets which does not contain the first element2 U1 E! I" y" P1 d% `2 O
result.append(ele)2 f- T; f7 e3 V4 P* E
7 L% f" [+ o/ E3 L- H+ l4 P
return result
| 
楼主: woaini
发表于 2-4-2017 05:12 PM
