Pythonのジェネレータによる、べき集合列挙の高速化
前回の問3.5「真に平等な分割」を力技で解くためのべき集合列挙を、
ジェネレータを用いて再帰的にやってみました。
def main(): #〜〜〜中略〜〜〜 for s in powerset_generator(numbers_to_divide): if sum(s) == sum1 and square_sum(s) == sum2 and cube_sum(s) == sum3: print(s) end = datetime.now() print("Time: " + str(end - start)) #与えられた集合(配列)のべき集合の要素を順に返すジェネレータ def powerset_generator(provided_set): if len(provided_set) > 0: for c in powerset_generator(provided_set[1:]): yield [provided_set[0]] + c yield c else: yield []
結果は下記の通り。マスキング変数を用いた手続的な方法よりも7倍以上高速でした。
[*************]
[*************]
Time: 0:00:00.105000