from fractions import Fraction
CACHE = {}
def generate_split(lst):
for i in range(1, 2**len(lst)-1):
left = []
right = []
j = 0
for k in range(len(lst)):
if i%2:
left.append(lst[j])
else:
right.append(lst[j])
i //= 2
j += 1
yield tuple(sorted(left)), tuple(sorted(right))
def product(set1, set2):
ret = set()
for n1 in set1:
for n2 in set2:
ret.update({n1+n2, n1-n2, n2-n1, -n1-n2, n1*n2})
if n1:
ret.add(n2/n1)
if n2:
ret.add(n1/n2)
return ret
def get_results(lst):
lst = [Fraction(el) for el in lst]
if len(lst) < 1:
return set()
if len(lst) == 1:
return set(lst)
lst = tuple(sorted(lst))
if lst in CACHE:
return CACHE[lst]
ret = set()
for l, r in generate_split(lst):
ret.update(product(get_results(l), get_results(r)))
CACHE[lst] = ret
return ret
if __name__ == '__main__':
s = get_results([1, 8, 9, 0, 6, 0])
print({str(el) for el in s})
print(len(s))
print(100 in s)
