############# TD d'informatique de BCPST2B du 28 septembre 2026 ###############
################# Séries, équivalent et régression linéaire ###################

import numpy as np
import random as rd
import matplotlib.pyplot as plt

## Exercice 1 : vérification d'un équivalent
# On rappelle la méthode pour calculer une somme en informatique :
# (initialement) s=0; for k in range(...) : s = s+...
# que l'on peut écrire avec l'instruction np.sum([liste en compréhension])

# On rappelle la méthode des moindres carrés (régression linéaire) pour évaluer
# A et B tels que un~A*vn+B : A=cov(Lu,Lv)/var(Lv) et B=moy(Lu)-A*moy(Lv)

# Q1a : Vérifier que Sn~beta*n^A équivaut à ln(Sn)-(A*ln(n)+ln(beta)) ->0
# Q1b : écrire une fonction python renvoyant, en fonction de a et N
#      la liste [S1,S2,...,SN] où Sn=somme{k=1 à n} des k^a
#      la liste des ln(k) où k décrit [[1,n]]

def exo1b(a,n) :
    s,Ls = 0,[]
    for k in range(1,n+1) :
        s += k**a
        Ls.append(s)
    return [np.log(s) for s in Ls],[np.log(k) for k in range(1,n+1)]

# Q1c : écrire une fonction moy calculant la moyenne d'une liste et une fonction
#   var calculant la variance (moyenne des carrés - carré de la moyenne) et une
#   fonction cov calculant la covariance de deux listes L1,L2 (moyenne des
#   produits L1[k]*L2[k]-produit des moyennes)

def moy(L) :
    return np.sum(L)/len(L)

def var(L) :
    L2 = [x**2 for x in L]
    return moy(L2)-moy(L)**2

def cov(L1,L2) :
    Lp = [L1[k]*L2[k] for k in range(len(L1))]
    return moy(Lp)-moy(L1)*moy(L2)

# Q1d : effectuer une régression linéaire sur les listes des Sk et ln(k) et
#   retrouver l'équivalence obtenue en cours par comparaison somme vs intégrale.

def verif(a,n) :
    Ls,Ln = exo1b(a,n)
    A = cov(Ls,Ln)/var(Ln)
    B = moy(Ls)-A*moy(Ln)
    # en cours on a trouvé A=a+1 et beta=1/(a+1)
    return A,np.exp(B)

# Q1e : tester la fonction verif avec a=2 et n qui vous semble pertinent.


## Exercice 2 : Dénombrement
# En informatique, on peut dénombrer des objets en les fabriquant exactement ou
# bien en fabriquant des "candidats" à tester pour sélectionner les vrais objets.

# Pour cela on a souvent recours à la fabrication de listes, y compris pour
# compter des combinaisons, en considérant qu'il faut bien se mettre d'accord
# sur une façon de les écrire (on adopte souvent l'odrer lexicographique).

# On peut d'abord penser à imbriquer des boucles pour parcourir des listes de
# longueur 2 ou 3 : par exemple, pour parcourir les listes [x0,x1,x2] :
# for x0... for x1... for x2...

# Le procédé s'épuise vite et, pour parcourir ou fabriquer des listes plus
# longues, on adopte un parcours d'arbre où on garde une pile (stock en cours)
# de listes en cours de fabrication et on explique comment choisir un élément
# de la pile et comment le prolonger d'un terme. Ensuite, on le replace dans la
# pile sauf s'il est terminé, auquel cas on le compte, ou pas.

# Exemple 1 :
# Q2a : écrire une fonction testant tous les triplets [a,b,c] d'entiers positifs
#    et comptant combien sont croissants de somme égale à N (en fonctiuon de N).
def exo2a(N) :
    # remarquons que les listes gagnantes sont constituées d'entiers <=N.
    compteur = 0
    for a in range(N) :
        for b in range(N) :
            for c in range(N) :
                if a<=b<=c and a+b+c==N :
                    compteur += 1
    return compteur

# on peut proposer une variante qui stocke les listes gagnantes :
def exo2abis(N) :
    # remarquons que les listes gagnantes sont constituées d'entiers <=N.
    Lgagn = []
    for a in range(N) :
        for b in range(N) :
            for c in range(N) :
                if a<=b<=c and a+b+c==N :
                    Lgagn.append( [a,b,c] )
    return len(Lgagn),Lgagn


## Exercice 3 : Parcours
# L'objectif est de parcourir "tous les cas possibles" afin de les compter
# ou de compter, parmi eux, les cas dits "favorables"

 # Exemple 1 : parcourir toutes les permutations d'une liste L sans répétition
 #      Le principe consiste à construire les permutations au fur et à mesure
 #      en prolongeant à chaque fois "un peu" un déjà existante jusqu'à ce
 #      qu'on en ait achevé que l'on compte (avec un compteur).
 #      Pour cela, on stocke les permutations en cours de fabrication dans une
 #      "pile"; à chaque tour, on en "dépile" une, à partir de laquelle on en
 #      fabrique de nouvelles prolongées que l'on "repile".
 #
 # Le programme suivant est donné en guise d'illustration.

def toutes_permut(L) : # on suppose L sans répétiton non vide
    N = len(L)
    compteur = 0 # on va ici compter toutes les permutations possibles
    pile = [ [x] for x in L ] # Q1 : que contient ici la pile ?
    while pile != [] : # Q2 : quelle est la condition d'arrêt ?
        l = pile.pop(-1)  # Q3 : quel élément de la pile consulte-t-on ?
        # Q4 : pourquoi utilise-t-on .pop() ?
        if len(l)==N :
            compteur += 1
        else :
            reste = [x for x in L if x not in l]
            for x in reste :
                pile.append( l+[x] )
    # Q5 : êtes-vous sûr que la boucle while s'arrête un jour ?
    return compteur

# Q3a : transformer le programme pour compter, lorsque L désigne une liste sans
#      répétition, toutes les listes de p éléments de L (p-arrangements de L)

def tous_p_arrgmts(L,p) :
    # on suppose L sans répétiton non vide et 1<=p<=len(L)
    compteur = 0
    pile = [ [x] for x in L ]
    while pile != [] :
        l = pile.pop(-1)
        if len(l)==p :
            compteur += 1
        else :
            reste = [x for x in L if x not in l]
            for x in reste :
                pile.append( l+[x] )
    return compteur

# Q3b : lorsque L est une liste non vide, sans répétiton, d'entiers,
#      compter tous les p-arrangements de L qui sont croissants

def tous_p_arrgmts_croiss(L,p) :
    # on suppose L sans répétiton non vide et 1<=p<=len(L)
    compteur = 0
    pile = [ [x] for x in L ]
    while pile != [] :
        l = pile.pop(-1)
        k = l[-1]
        if len(l)==p :
            compteur += 1
        else :
            reste = [x for x in L if x not in l and x>k]
            for x in reste :
                pile.append( l+[x] )
    return compteur

## Exercice 1bis : Voir le parcours
# Au lieu de compter on va ici afficher et proposer une variante :
# remplacer la ligne 25 par : l = pile.pop(0)
def affiche_toutes_permut(L) : # on suppose L sans répétiton non vide
    N = len(L)
    pile = [ [x] for x in L ]
    while pile != [] :
        l = pile.pop(-1)
        if len(l)==N :
            print(l)
        else :
            reste = [x for x in L if x not in l]
            for x in reste :
                pile.append( l+[x] )

def affiche_toutes_permut_variante(L) :
    N = len(L)
    pile = [ [x] for x in L ]
    while pile != [] :
        l = pile.pop(0)
        if len(l)==N :
            print(l)
        else :
            reste = [x for x in L if x not in l]
            for x in reste :
                pile.append( l+[x] )

# Q3c : tester les deux variantes et expliquer les deux résultats obtenus