Algorithmique

def tsp_chemin(distance, depart=0):
    """
    Résout le problème du voyageur de commerce (TSP) en utilisant une programmation dynamique basée sur les masques binaires.

    Cette fonction calcule, pour chaque sous-ensemble de villes et pour chaque ville terminale, le coût minimal pour parcourir l'ensemble des villes spécifié par le masque et terminer dans cette ville.
    Elle permet également de reconstruire le chemin optimal en stockant, pour chaque état, la ville précédente.

    Paramètres
    ----------
    distance : list[list[float]]
        Matrice des distances entre les villes, où distance[i][j] représente la distance allant de la ville i à la ville j.
    depart : int, optionnel
        Indice de la ville de départ (par défaut 0).

    Retourne
    --------
    tuple
        Un tuple (dp, parent) contenant :
          - dp : list[list[float]]
            Tableau à deux dimensions de taille (2^n x n) où dp[masque][j] est le coût minimum pour visiter
            l'ensemble de villes indiqué par le masque (représenté en binaire) et terminer à la ville j.
          - parent : list[list[int]]
            Tableau à deux dimensions de taille (2^n x n) permettant de reconstruire le chemin optimal.
            Pour chaque état (masque, j), parent[masque][j] stocke l'indice de la ville qui précède j dans le chemin optimal.

    Description
    -----------
    L'algorithme initialise une table dp avec des valeurs infinies, sauf pour l'état correspondant au départ.
    Il parcourt ensuite tous les masques possibles (correspondant aux 2^n sous-ensembles de villes) et, pour chaque ville déjà visitée, il tente de mettre à jour le coût minimal pour atteindre chaque ville non encore visitée.
    La structure parent est utilisée pour enregistrer les transitions effectuées, ce qui permet ultérieurement
    de reconstruire le chemin optimal.

    Exemple d'utilisation
    ---------------------
    >>> distance = [
    ...     [0, 10, 15, 20],
    ...     [10, 0, 35, 25],
    ...     [15, 35, 0, 30],
    ...     [20, 25, 30, 0]
    ... ]
    >>> dp, parent = tsp_chemin(distance, depart=0)
    """
    n = len(distance)
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)] 
    parent = [[-1] * n for _ in range(1 << n)]
    
    dp[1 << depart][depart] = 0
    for masque in range(1 << n):  # 2^n possibilités (chaque ville est visitée ou non visitée)
        for i in range(n):
            if masque & (1 << i):  # si la ville i est visitée
                for j in range(n):
                    if not (masque & (1 << j)):  # si la ville j n'est pas encore visitée
                        nv_masque = masque | (1 << j)
                        if dp[nv_masque][j] > dp[masque][i] + distance[i][j]:
                            dp[nv_masque][j] = dp[masque][i] + distance[i][j]
                            parent[nv_masque][j] = i
    return dp, parent

def reconstr_chemin(parent, masque, dernier):
    chemin = []
    while dernier != -1:
        chemin.append(dernier)
        temp = parent[masque][dernier]
        masque = masque & ~(1 << dernier)
        dernier = temp
    chemin.reverse()
    return chemin

dp, parent = tsp(distance, depart=0)
masque_final = (1 << len(distance)) - 1

for i in range(len(distance)):
    coût_total = dp[masque_final][i] + distance[i][0] 
    if coût_total < coût_min:
        coût_min = coût_total
        chemin_min = reconstr_chemin(parent, masque_final, i)
        chemin_min.append(0)  # Fermer le cycle

def Hanoi(n, depart, cible, inter):
    if n == 1:
      deplacement(depart,cible)
    else :
      Hanoi(n-1,depart,inter,cible)
      Hanoi(1,depart,cible,inter)
      Hanoi(n-1,inter,cible,depart)

Hanoi(6, 0, 2,1)

from random import randint

def partition(L, g, d):
    p = L[g]
    i = g+1
    for j in range(g+1,d+1):
        if L[j] < p:
            permute(L,i,j)
            i += 1
    permute(L,g,i-1)
    return i-1

def tri_rapide_gd(L, g, d):
    if g < d: 
        pivot = randint(g,d)
        permute(L,pivot,g)
        pivot = partition(L, g, d)
        tri_rapide(L, g, pivot-1)
        tri_rapide(L, pivot+1, d)
    return L

def tri_rapide(L):
    g = 0
    d = len(L)-1
    tri_rapide_gd(L, g, d)

def partition(L):
    p = 0         # pivot (chapeau noir)
    i = len(L)-1  # chapeau rouge
    while i != p:
      if (L[p]-L[i])*(p-i) < 0:
        L[p],L[i] = L[i],L[p]
        p,i = i,p
      i -= (i-p)//abs(i-p)
    return p
    
def tri_rapide(L):
    if len(L) <= 1:
      return L
    else:
      p = partition(L)
      L[:p] = tri_rapide(L[:p])
      L[p+1:] = tri_rapide(L[p+1:])
      return L

def triRapide(elements):
    if len(elements) <= 1:
        return elements
    else: 
        pivot = elements[0]
        plusPetit = triRapide([e for e in elements[1:] if e <= pivot])
        plusGrand = triRapide([e for e in elements[1:] if e > pivot])
        return plusPetit + [pivot] + plusGrand

from collections import deque
# deque est une file à double extrémités (double-ended queue) avec la primitive popleft() pour retirer à gauche comme une file et pop() pour retirer à droite comme une pile.

def BFS(G,depart):
    """
    graphe G(S,A) représenté par une liste d'adjacence implémentée par un dictionnaire et depart un sommet de S
    """
    file = deque()
    file.append(depart)
    Vus = {s : False for s in G}
    Sommets = []
    while file: # tant que la file n'est pas vide
        sommet = file.popleft() # méthode de la classe deque permettant de défiler
        if not Vus[sommet]:
            file += G[sommet]
            Vus[sommet] = True
            Sommets.append(sommet) 
    return Sommets

def DFS(G,depart):
    pile = deque()
    pile.append(depart)
    Vus = {s : False for s in G}
    Sommets = []
    while pile:
        sommet = pile.pop()
        if not Vus[sommet]:
            pile += G[sommet]
            Vus[sommet] = True
            Sommets.append(sommet) 
    return Sommets

def DFS(G,depart,Vus,Sommets=[]):
    Sommets.append(depart)
    Vus[depart] = True
    for sommet in G[depart]:
        if not Vus[sommet]:
            DFS(G,sommet,Vus,Sommets)
    return Sommets

import heapq

def Dijkstra(G, depart):
    """
    Calcule les plus courts chemins dans un graphe pondéré à partir d'un sommet de départ.

    Paramètres :
      - G : dict, représentation du graphe où les clés sont les sommets et les valeurs sont des dictionnaires {voisin: poids}.
      - depart : le sommet de départ.

    Retourne :
      - predecesseurs : dict, permettant de reconstruire les plus courts chemins.
      - distances : dict, distances minimales depuis le sommet de départ.
    """
    if depart not in G:
        raise ValueError("Le sommet de départ n'est pas présent dans le graphe")

    distances = {sommet: float('infinity') for sommet in G}
    predecesseurs = {sommet: None for sommet in G}
    distances[depart] = 0

    tas = [(0, depart)]
    while tas:
        distance_actuelle, sommet_actuel = heapq.heappop(tas)
        # On ignore l'entrée obsolète si un meilleur chemin a été trouvé
        if distance_actuelle > distances[sommet_actuel]:
            continue

        for voisin, poids in G[sommet_actuel].items():
            nouvelle_distance = distance_actuelle + poids
            if nouvelle_distance < distances[voisin]:
                distances[voisin] = nouvelle_distance
                predecesseurs[voisin] = sommet_actuel
                heapq.heappush(tas, (nouvelle_distance, voisin))
    return predecesseurs, distances