from itertools import combinations
from collections import defaultdict
def solution(relation):
columns = list(range(len(relation[0])))
memoization = defaultdict(bool)
for i in range(1,len(columns)+1):
for column_combi in list(combinations(columns,i)):
memoization[column_combi] = True
for k, v in memoization.items():
if k!=column_combi and v is True:
if not (set(k) - set(column_combi)):
memoization[column_combi] = False
check_set = set()
for one_rel in relation:
check_tuple = tuple(one_rel[i] for i in range(len(one_rel)) if i in column_combi)
check_set.add(check_tuple)
if len(relation) != len(check_set):
memoization[column_combi] = False
return list(memoization.values()).count(True)