import itertools
from time import time

def rechercher_possibilites(contrainte, taille):
    liste = [i for i in range(1, taille+1)]
    possibilites = []
    for i in range(taille):
        possibilites.append(set())
    for ligne in itertools.permutations(liste):
        resultat = est_valide_gauche(contrainte, ligne)
        if resultat:
            #print(ligne)
            for i in range(taille):
                possibilites[i].add(ligne[i])
    #print(possibilites)
    return possibilites

def est_valide_gauche(contrainte, ligne):
    visu_gauche = 1
    maxi = ligne[0]
    for i in range(1,len(ligne)):
        if ligne[i] > maxi:
            visu_gauche += 1
            maxi = ligne[i]
    if visu_gauche != contrainte:
        return False
    return True

def recherche_globale(taille):
    resultat = []
    for visibilite in range(1, taille+1):
        resultat.append(rechercher_possibilites(visibilite, taille))
    return resultat

def generer_visibilite_ligne(visibilite, taille):
    resultat = []
    for indice in range(taille):
        resultat.append(generer_visibilite(visibilite, taille, indice))
    return resultat

def generer_visibilite_globale(taille):
    resultat = []
    for visibilite in range(1, taille+1):
        resultat.append(generer_visibilite_ligne(visibilite, taille))
    return resultat
    
def generer_visibilite(visibilite, taille, indice):
    if visibilite == 1:
        return generer_visibilite_1(taille, indice)
    if visibilite == 2:
        return generer_visibilite_2(taille, indice)
    if visibilite == taille:
        return generer_visibilite_taille(taille, indice)
    return generer_visibilite_intermediaire(visibilite, taille, indice)

def generer_visibilite_1(taille, indice):
    if indice == 0:
        resultat = set([taille])
    else:
        resultat = set([i for i in range(1, taille)])
    return resultat

def generer_visibilite_2(taille, indice):
    if indice == 0:
        resultat = set([i for i in range(1,taille)])
    elif indice == 1:
        resultat = set([i for i in range(1,taille-1)] + [taille])
    else:
        resultat = set([i for i in range(1, taille+1)])
    return resultat

def generer_visibilite_taille(taille, indice):
    resultat = set([indice+1])
    return resultat

def generer_visibilite_intermediaire(visibilite, taille, indice):
    if indice >= visibilite - 1:
        resultat = generer_tout(taille)
    else:
        resultat = set([i for i in range(1, taille-visibilite+2+indice)])
    return resultat
        
def generer_tout(taille):
    return set([i for i in range(1, taille+1)])

def compareTemps(taille):
      t1 = time()
      recherche_globale(taille)
      t2 = time()
      d_recherche = t2 - t1
      t1 = time()
      generer_visibilite_globale(taille)
      t2 = time()
      d_generation = t2 - t1
      print("temps recherche :", d_recherche, "temps calcul :", d_generation)