from itertools import permutations
from math import factorial

#=======================HAMPTON-COURT==================
pointList = ['0','1','2','3','4','5','6','7','8','9','10','11','x']
linkList = [('1,0'),('1','11'),('2','1'),('2','3'),('2','4'),('3','2'),('4','2'),('5','2'),('6','5'),('6','7'),('7','5'),('7','6'),('8','6'),('8','7'),('9','8'),('9','10'),('10','9'),('11','1'),('x','9')]


#=======================TESTS==========================
# pointList = ['0','1','2','3']
# linkList = [('0','1'),('0','2'),('0','3')]

# pointList = ['0','1']
# linkList = [('0','1')]

def calculate_subgraphs():
    filteredPointList = []

    subgraphCount = 0
    for i in range(0,pointList.__len__()+1):

        for situation in permutations(pointList,i):
            if(sorted(situation) == list(situation)):
               # print('situation: ' + str(situation))

                filteredLinkList = []
                filteredLinkList = [link for link in linkList if link[0] in situation and link[1] in situation]
                filteredLinkListLocalLength = filteredLinkList.__len__()
                # print('filteredLinkListLocalLength: ' + str(filteredLinkListLocalLength) + ' situation: ' + str(situation))
                subgraphCount+= 2**filteredLinkListLocalLength
        print('i: ' + str(i) + ' subgraphCount: ' + str(subgraphCount))

    return subgraphCount



f= open('output.txt','w')

f.write('Answer for \n' +str(pointList)+'\n'+ str(linkList)+ '\nis: ' +str(calculate_subgraphs()))
f.close()