import itertools
import copy


def list_fb(n):
   """
   Gives the list of fb module for An as matrices. This should be used for small values of n.
   """
   fb = []
   lst = [[[1] + list(i)] for i in itertools.product([0, 1], repeat=n-1)]
   for j in range(n-1):
       lstpp = []
       for l in lst:
           lstp = []
           pos=[]
           for e in range(j+1):
              for i, val in enumerate(l[e]):
                 if val and i not in pos:
                       pos.append(i)
           if n-j-1 in pos:
                lstp.append([0]*n)
           for k in pos:
               if k<=n-j-2:
                  lstp.extend([[0]*k + [1] + list(i) + [0]*(j+1) for i in itertools.product([0,1],repeat = n-j-k-2)])
           for y in lstp:
               calc = list(l)
               calc.append(y)
               lstpp.append(calc)
           lst = list(lstpp)
   return(lst)


def indices(n):
   """
   sage: list(indices(3))
   [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]
   """
   for i in range(1, n + 1):
      for j in range(i, n + 1):
         yield (i, j)


def is_faithfully_balanced(liste,n):
    """
    verifie

    INPUT: liste de tuple de taille 2

    sage: is_faithfully_balanced([(1,2),(1,3),(2,3)])
    True
    sage: is_faithfully_balanced([(1,2),(2,2),(2,3)])
    False
    """
    # contient (1, n)
    if not (1, n) in liste:
        return False
    # cohooks virtuels non vides
    for i in range(1, n + 2):
       if not any((a, b) in liste for a, b in cohook(i, i - 1, n)):
          return False
    # cohook non vides
    for (i, j) in liste:
       if (i, j) != (1, n):
          if not any((a, b) in liste for a, b in cohook(i, j, n)):
             return False
    return True


def cohook(i, j, n):
   """
   sage: list(cohook(1,3,3))
   []
   sage: list(cohook(2,2,3))
   [(1, 2), (2, 3)]
   """
   for k in range(1, i):
      yield (k, j)
   for l in range(j + 1, n + 1):
      yield (i, l)


def generator_n(n):
   """
   sage: list(generator_n(2))
   [{(1, 2), (1, 1)}, {(1, 2), (2, 2)}]
   sage: list(generator_n(3))
   [{(1, 2), (1, 3), (1, 1)},
   {(1, 3), (1, 1), (3, 3)},
   {(1, 2), (1, 3), (2, 2)},
   {(1, 2), (1, 3), (2, 3)},
   {(1, 3), (2, 3), (2, 2)},
   {(1, 3), (2, 3), (3, 3)}]
   sage: len(list(generator_n(4)))
   24
   """
   indec = list(indices(n))
   for M in Subsets(indec, n):
      if is_faithfully_balanced(M,n):
         yield M
def generator_fb(n):
   """
   sage: list(generator_fb(2))
   [{(1, 2), (1, 1)}, {(1, 2), (2, 2)}, {(1, 2), (1, 1), (2, 2)}]
   sage: len(list(generator_fb(3)))
   21
   sage: len(list(generator_fb(3)))
   315
   """
   indec = list(indices(n))
   for M in Subsets(indec):
      if is_faithfully_balanced(M,n):
         yield M

def subset_to_matrix(S):
   """
   sage: subset_to_matrix([(1,2),(2,2)])
   [[1, 1], [0, 0]]
   sage: subset_to_matrix([(1,2),(1,1)])
   [[1, 0], [1, 0]]
   """
   n = len(S)
   M = [[0 for _ in range(n)] for _ in range(n)]
   for (i, j) in S:
      M[n - j][i - 1] = 1
   return M


def subcat(mat1, mat2):
    """
    Test if the category generated by the matrix mat1 is a subcategory
    of the one generated by mat2
    """
    return all(mat2i[j] for mat1i, mat2i in zip(mat1, mat2)
               for j, x in enumerate(mat1i) if x)


def incl(a, b):
    """
    Auxiliary function.
    """
    return subcat(a[2], b[2]) and subcat(b[1], a[1])


def cogen(m):
    mc = list(m)
    n = len(m)
    for i in range(n):
        c = [m[x][i] for x in range(n)]
        posg = [j for j, x in enumerate(m[i]) if x]
        posc = [j for j, x in enumerate(c) if x]
        if posc:
                e=posc[0]
                for j in range(e,n-i):
                        mc[j][i]=1
    return(mc)


def gen(m):
    mg = list(m)
    n = len(m)
    for i in range(n):
        c = [m[x][i] for x in range(n)]
        posg = [j for j,x in enumerate(m[i]) if x]
        posc = [j for j,x in enumerate(c) if x]
        if posg:
                e=posg[0]
                for j in range(e,n-i):
                        mg[i][j]=1
    return(mg)


def intersect(mc, mg):
    n = len(mc)
    return [[mc[j][i] and mg[j][i] for i in range(n)] for j in range(n)]


def catunion(mc, mg):
    n = len(mc)
    return [[mc[j][i] or mg[j][i] for i in range(n)] for j in range(n)]


def fbn(n):
    l = [subset_to_matrix(S) for S in generator_n(n)]
    return(l)



def gen_cogen_poset(n):
   """
   Construct the poset of fb modules with n summands for relation M < N if cogen(M) in cogen(N) and gen(N) in gen(M)

   sage: P = gen_cogen_poset(5)
   Finite lattice containing 120 elements
   """
   l = [subset_to_matrix(S) for S in generator_n(n)]
   nf = len(l)
   gen_cogen = []
   for m in l:
       mg = copy.deepcopy(m)
       mc = copy.deepcopy(m)
       for i in range(n):
          c = [m[x][i] for x in range(n)]
          posg = [j for j, x in enumerate(m[i]) if x]
          posc = [j for j, x in enumerate(c) if x]
          if posg:
              e=posg[0]
              for j in range(e,n-i):
                 mg[i][j]=1
          if posc:
              e=posc[0]
              for j in range(e,n-i):
                 mc[j][i]=1
       gen_cogen.append([m, mg, mc])
   adj = [(ix, iy) for ix, x in enumerate(gen_cogen)
          for iy, y in enumerate(gen_cogen) if incl(y, x)]
   return LatticePoset([range(nf), adj])