"""__author__ = DENDI SUHUBDY"""

from exemplaires import *

def product(tuple1, tuple2):
    result = tuple(tuple2[tuple1[i] - 1] for i in range(len(tuple1)))
    return result

def inverse(tuple_to_inverse):
    inverse_result = [0] * len(tuple_to_inverse)
    for i in range(len(tuple_to_inverse)):
        inverse_result[tuple_to_inverse[i]-1] = i + 1
    return inverse_result

def sift(p, T):
    # input : p (permutation to sift) and T (table)
    # output : permutation q if new permutation inserted, otherwise None
    m = len(p)
    IDENTITY =tuple(range(1, m+1))
    C = 0
    while p!= IDENTITY:
        i = min(x for x in range(m) if p[x] != x+1)
        j = p[i]-1
        if T[i][j] == IDENTITY:
            T[i][j] = p
            return p, C
        else:
            p = product(p, inverse(T[i][j]))
            C += 1
    return None, None

def intelligent_permute(r, permutations, k):
    """ Does r belong to the group generated by the set permutations?"""
    #raise Error if invalid permutations
    m = len(r)
    IDENTITY = tuple(range(1, m+1))
    T = [[IDENTITY] * m for _ in range(m)] # creates a mXm table T containing IDENTITY
    C = [[0] * m for _ in range(m)] # creates a mXm table T containing count
    to_sift = [(p) for p in permutations]
    # maintains set of table entries as a set
    entries = set()
    count_list =[]
    while len(to_sift) > 0:
        p = to_sift.pop()
        q, l = sift(p, T)
        if l:
            count_list.append(l)
        #print(T)
        if q is not None:
            entries.add(q)
            # the product q*q is considered since we added q to entries
            to_sift.extend([(product(q,p)) for p in entries])
            to_sift.extend([(product(p,q)) for p in entries])
    # Genere r? / Generates r?
    count = sum(count_list)
    print(count)
    if (count <= k):
        return False
    result = sift(r, T)
    return result[0] is None


def perm2(k, p, p1, p2):
    if len(p) != len(set(p)):
        return "Error data is not in permutation"
    s = set([p1, p2])
    result = intelligent_permute(p, s, k)
    return result

def main():
    print("result of perm2(k1, p1, p11, p21) is ")
    result1 = perm2(k1, p1, p11, p21)
    print(result1)

    print("result of perm2(k2, p2, p12, p22) is ")
    result2 = perm2(k2, p2, p12, p22)
    print(result2)

    print("result of perm2(k3, p3, p13, p23) is ")
    result3 = perm2(k3, p3, p13, p23)
    print(result3)

    print("result of perm2(k4, p4, p14, p24) is ")
    result4 = perm2(k4, p4, p14, p24)
    print(result4)

    print("result of perm2(k5, p5, p15, p25) is ")
    result5 = perm2(k5, p5, p15, p25)
    print(result5)

    print("result of perm2(k6, p6, p16, p26) is ")
    result6 = perm2(k6, p6, p16, p26)
    print(result6)

    print("result of perm2(k7, p7, p17, p27) is ")
    result7 = perm2(k7, p7, p17, p27)
    print(result7)

if __name__=="__main__":
    main()

"""
    (dev3) ┌─────── suhubdyd@leto52 [~/courses/winter2018]
    └─ λ python devoir1.py
    result of perm2(k1, p1, p11, p21) is
    True
    result of perm2(k2, p2, p12, p22) is
    False
    result of perm2(k3, p3, p13, p23) is
    Error data is not in permutation
    result of perm2(k4, p4, p14, p24) is
    True
    result of perm2(k5, p5, p15, p25) is
    True
    result of perm2(k6, p6, p16, p26) is
    True
    result of perm2(k7, p7, p17, p27) is
    False
"""
