
# a helper function to join (merge) a set of itemsets 
# or in other words, find all combinations for a set of sets
def mergeSet(myset, z):
    
    outList = [] 
    for i in myset:
        for j in myset:
            if (len((i).union(j)) == z):
                outList.append(i.union(j))
    return set(outList)
    


# A list to contain support count for all levels
# for example c[0] contains all 1-itemset and their support count
# c[1] contains all 2-itemset and their support count
# c[2] contains all 3-itemset and their support count, and so on
c = []


# A list that contains all frequent itemsets for all levels
# for example l[0] contains all frequent 1-itemset
# l[1] contains all frequent 2-itemset
# l[2] contains all frequent 3-itemset, and so on
l = []


# read the dataset 
datafile = open('sample_data.txt', 'r')

# store each line (transaction) in the dataset as a list item
df_lines = datafile.readlines()

# total number of transactions
n_transactions = len(df_lines)

# close the file
datafile.close()

##To be commented out after testing
#df_lines = df_lines[0:200]
#n_transactions = len(df_lines)

len_total = 0

# a function to generate frequent itemset and store them in the list "l"
# takes three arguments:
# df_lines: the list containing all transactions (each transaction as a list item)
# N : maximum number of itemset elements, for example if N = 2, we generate frequent 1-itemset, and 2-itemset
# minsup: minimum support (in percentage). For example, if minsup = 0.3, then minimum support is 0.3%

def ModifiedApriori(df_lines, N, minsup):

    minsup = minsup / 100

    # a set to contain distinct 1-itemset from transactions
    unique_items = set()

    # a dictionary to hold each distinct 1-itemset and corresponding 
    # support count

    c.append(dict())

    print("Generating 1-itemset candidates...")

    # Here, we iterate over each transaction (full pass) to find the support count 
    # for each 1-itemset 
    for i in range(len(df_lines)):
        for itemset in (df_lines[i].split()):
            if (frozenset({itemset}) in c[0]):
                c[0][frozenset({itemset})] += 1
            else:
                c[0][frozenset({itemset})] = 1

    print("number of 1-itemset candidates: " , len(c[0]))

    l.append([])

    print("Generating frequent 1-itemsets...")
    for k in c[0]:
        # From the candidates, select the ones with at least minimum support
        if c[0][k] / n_transactions >= minsup:
            l[0].append(k)

    print("number of frequent 1-itemsets: ", len(l[0]))

    
    for i in range(1,N):
        print("Generating",i+1,"-itemset candidates...")      

        # Here, we join the set of frequent itemsets from the previous step 
        # to generate the candidate itemsets for this step
        # output (c_i) is a list of sets

        c_i = mergeSet(l[i-1], i+1)
        print("Number of C",i+1," candidates:", len(c_i))
        
        print("Finding the support count for",i+1,"-itemset candidates...")
        c.append(dict())

        # Another full pass to find the support count for each candidate itemset
        # in c_i
        for itemset in c_i:
            for tx in df_lines:
                if (itemset.issubset(set(tx.split()))):
                    if (frozenset(itemset) in c[i]):
                        c[i][frozenset(itemset)] += 1 
                    else:
                        c[i][frozenset(itemset)] = 1


        print("Number of C",i+1," candidates with support count > 0 :", len(c[i]))

        #find frequent i+1-itemsets
        print("Generating frequent", i+1,"-itemsets...")
        l.append([])
        
        # Prune the candidates according to the minimum support to generate L_k
        for k in c[i]:
            if (c[i][k] / n_transactions >= minsup):
                l[i].append(k)

        print("Number of frequent", (i+1), "-itemset: ", len(l[i]))



# This function generates rules using the globally-avaialable sturctures "l" and "c" generated by
# ModifiedApriori function
# This function takes one argument:
#   K : number of rules to be printed (top K rules according to confidence measure)
def RuleGeneration(K):
    
    # Find the value of N 
    N = len(l)
    
    # Prepare an empty dictionary to store rules
    # rules will be stored as follows:
    # { (lhs, rhs) : confidence }
    # where lhs is the left hand side of the rule,
    # rhs is the right hand side of the rule
    # confidence is the value for confidence for this rule
    # for example: if we have the following rule:
    #   {'SNA17715'}, {'ELE26917'} --> {'GRO99222'} with a confidence of 0.6
    # it will be stored as follows:
    # ( frozenset({'SNA17715', 'ELE26917'}), frozenset({'GRO99222'}) ) : 0.6
    rules = {}
    for itemset in l[N-1]:
        # We need to fetch the itemset support count
        # all support counts are in "c" but we need to idnetify the level
        # the support for the rule is always in the last level [N-1]
        # then we can index into c[N-1] using the key "itemset"
        itemset_sup_count = c[N-1][itemset]

        # We need to generate all possible non-empty subsets of this itemset
        # first start with 1-itemset subsets 
        subsets = [frozenset({x}) for x in itemset]
        subsets = set(subsets)

        allsubsets = []
        # Generate all combinations of non-empty subsets starting from the 1-itemset
        # We call the mergeSet function as many times as we have items in the original itemset
        # then, we add the generated list of subset and append it to "allsubsets"
        # Then, we recursivly call mergeSet on the output subset of the previous call and so on
        for i in range(1, len(itemset)):
            s = mergeSet(subsets, i)
            for y in s:
                allsubsets.append(y)
            subsets = s 

        # Now, we have all possible non-empty subsets of this rule (itemset) stored in "allsubsets"
        # We generate all possible rules by iterating over each item in allsubsets and use it as the 
        # left hand side for the rule, then the right handside will be the original itemset - {item}
        # then we find the confidence for this generated rule using the equation f_11/f_1+
        # where f11 is the original itemset support count (already stored in itemset_sup_count)
        # we get f_1+ which is the item support count by finding the level of c at which the item support
        # count is stored, and then do the calculation and store the confidence alongside with the rule in 
        # the dictionary rules
        for it in allsubsets:
            it_level = len(it) - 1
            it_sup_count = c[it_level][it]
            rule_confidence = itemset_sup_count / it_sup_count
            rules[(it, itemset.difference(it))] = rule_confidence
    
    # sort rules in reverse order based on the confidence 
    sorted_rules = {k:v for k,v in sorted(rules.items(), key= lambda entry: entry[1], reverse=True)}
    
    # print top K rules (with highest confidence)
    print("Top", K, "Rules and their corresponding confidence ")
    for rule in list(sorted_rules.keys())[0:K]:
        confidence = sorted_rules[rule]
        
        (x,y) = rule

        # Just making it in a friendly form for printing
        readable_lhs = str(x).replace("frozenset(","").replace("',", "'},").replace(" '", " {'").replace(")", " -->")
        readable_rhs = str(y).replace("frozenset(","").replace("',", "'},").replace(" '", " {'").replace(")", "")
        print(readable_lhs, readable_rhs, confidence)
    
    print("Total number of rules generated:",len(rules))
        

ModifiedApriori(df_lines, 3, 0.3)
RuleGeneration(5)
