#!/usr/bin/env python3 """Un programme qui ne sert à pas grand chose.""" import sys def teste(): """Teste les fonctions : - `recupere_combinaisons_2` - `recupere_combinaisons` - `recupere_parametres` Ces trois fonctions testées seront écrites plus tard, mais c'est souvent une bonne chose de commencer par les tests, donc allons-y. En plus, écrire ce test vous obligera à réfléchir à l'algorithme général à appliquer pour générer les combinaisons, sur des séquences simples. Les spécifications sont données en commentaire dans le corps de la fonction. Merci de les respecter À LA LETTRE (pour les tests automatiques). """ # affiche une ligne contenant EXACTEMENT la chaîne de caractère suivante : # Résultats calculés dans ma tête pour la séquence "ABCD" et k=2 print('Résultats calculés dans ma tête pour la séquence "ABCD" et k=2') # affiche ces combinaisons calculées dans notre tête, avec une seule # combinaison par ligne, sous forme de chaine de caractères par exemple AC print("AB", "AC", "AD", "BC", "BD", "CD", sep="\n") # affiche une ligne contenant EXACTEMENT la chaîne de caractère suivante : # Résultats calculés par recupere_combinaisons_2("ABCD") print('Résultats calculés par recupere_combinaisons_2("ABCD")') # effectue l'appel à recupere_combinaisons_2('ABCD'), puis affiche les # combinaisons renvoyées par cette appel, avec une seule combinaison par # ligne. Une combinaison étant un tuple, on vous demande pour l'affichage # de passer directement ce tuple à la fonction print, c'est à dire de ne # faire aucun formatage. La combinaison AC sera donc affichée de la façon # suivante : ('A', 'C') print(*recupere_combinaisons_2('ABCD'), sep="\n") # affiche une ligne vide print() # affiche une ligne contenant EXACTEMENT la chaîne de caractère suivante : # Résultats calculés dans ma tête pour la séquence [0, 1, 2, 3, 4] et k=3 print("Résultats calculés dans ma tête pour la séquence [0, 1, 2, 3, 4] et k=3") # affiche ces combinaisons calculées dans notre tête, avec une seule # combinaison par ligne, sous forme de chaine de caractères (par exemple # 014) print("012", "013", "014", "023", "024", "034", "123", "124", "134", "234", sep="\n") # affiche une ligne contenant EXACTEMENT la chaîne de caractère suivante : # Resultats calculés par recupere_combinaisons([0, 1, 2, 3, 4], 3) print("Résultats calculés par recupere_combinaisons([0, 1, 2, 3, 4], 3)") # effectue l'appel à recupere_combinaisons([0, 1, 2, 3, 4], 3), puis affiche # les combinaisons renvoyées par cette appel, avec une seule combinaison par # ligne. Une combinaison étant un tuple, on vous demande pour l'affichage # de passer directement ce tuple à la fonction print, c'est à dire de ne # faire aucun formatage. La combinaison 014 sera donc affichée de la façon # suivante : (0, 1, 4) print(*recupere_combinaisons([0, 1, 2, 3, 4], 3), sep="\n") # affiche une ligne vide print() # effectue l'appel recupere_parametre(x) avec x récupéré en tant que premier # argument de la ligne de commande. sequence, k = recupere_parametres(sys.argv[1]) # affiche une ligne contenant EXACTEMENT la chaîne de caractère suivante : # Résultats calculés par recupere_combinaisons sur les paramètres dans le ficher print("Résultats calculés par recupere_combinaisons sur " "les paramètres dans le ficher") # effectue l'appel à recupere_combinaisons en utilisant les paramètres # renvoyés par l'appel à recupere_parametre(x), puis affiche les # combinaisons renvoyées par cette appel, avec une seule combinaison par # ligne. Une combinaison étant un tuple, on vous demande pour l'affichage # de passer directement ce tuple à la fonction print, c'est à dire de ne # faire aucun formatage. La combinaison AC sera donc affichée de la façon # suivante : ('A', 'C') print(*recupere_combinaisons(sequence, k), sep="\n") def recupere_parametres(filename): """Renvoie un tuple à deux entrées contenant la séquence et le paramètre k, DANS CET ORDRE lus à partir du fichier passé en paramètre. Spécifications PRÉCISES (pensons aux tests automatiques) sur le format du fichier : - la première ligne contient le nombre k - la seconde contient le nombre d'éléments dans le séquence qui suit, ce nombre est forcément un nombre pair et on le note nb_elems - nb_elems/2 lignes, contenant chacune deux chaînes de caractères séparées par une virgule """ input_file = open(filename, "r") k = -1 nb_elems = -1 elems = [] for line in input_file: # Nous sommes sur la première ligne # On ferait du next en VRAI python, # mais on l'a pas encore vu. if k == -1: k = int(line) # Nous sommes sur la deuxième ligne elif nb_elems == -1: nb_elems = int(line) # Nous sommes sur une ligne contenant 2 éléments else: splited_line = line.strip().split(",") elems.append(splited_line[0]) elems.append(splited_line[1]) return elems, k def recupere_combinaisons_2(sequence): """"Renvoie toutes les combinaisons de taille 2 de la séquence donnée. Spécifications PRÉCISES (pensons aux tests automatiques) : - les combinaisons renvoyées sont représentées par une `list` de `tuple`. """ combins = [] for i, elem_i in enumerate(sequence): for j in range(i+1, len(sequence)): combins.append((elem_i, sequence[j])) return combins def renverse(sequence): """Renvoie une nouvelle séquence qui est la séquence donnée à l'envers.""" reversed_sequence = [] for i in range(len(sequence) - 1, -1, -1): reversed_sequence.append(sequence[i]) return reversed_sequence def recupere_combinaisons(sequence, k): """"Renvoie toutes les combinaisons de taille k de la sequence donnée. Attention, cette fonction est difficile à implémenter. Il est vivement conseillé de réfléchir à votre algorithme sur le papier avant de se lancer dans le code. La fonction `renverse` sera normalement utilisée. Spécifications PRÉCISES (pensons aux tests automatiques) : - les combinaisons renvoyées sont représentées par une `list` de `tuple`. """ # Cette implémentation fonctionne sur les indices des éléments de la prochaine # combinaison à ajouter tel que : # - les indices des éléments de n'importe quelle combinaison soient # "strictement croissants entre eux" (par exemple on n'aura jamais 0 2 1) # - la suite des indices des combinaisons successives soit "strictement croissante". # Par exemple quand on choisit 3 parmi 5, la suite des indices sera la suivante : # - 0 1 2 # - 0 1 3 # - 0 1 4 # - 0 2 3 # - 0 2 4 # - 0 3 4 # - 1 2 3 # - 1 2 4 # - 1 3 4 # - 2 3 4 # list des combinaisons qui sera renvoyée combins = [] # Rien à faire si k > n nb_elems = len(sequence) if k > nb_elems: return combins # Le tableau `indices` de taille k, contient les indices dans séquence, # des k éléments composant la prochaine combinaison à ajouter. # On commence par renvoyer les k premiers éléments. indices = list(range(k)) combins.append(tuple(sequence[i] for i in indices)) # On va construire tous les autres tuples de k éléments while True: # On cherche l'indice i qu'il faut incrémenter # en partant du plus grand. found = False for i in renverse(range(k)): if indices[i] != i + nb_elems - k: found = True break # Si on a pas trouvé d'indice à incrémenter, # ça veut dire qu'on a fini if not found: break # Ici on va dire à pytlint, pour avoir 10/10 et donc pass # de malus sur notre note BPI : # "ÉCOUTE MOI MON PETIT, JE TE DIS QUE i EST DÉFINI !" # pylint: disable=undefined-loop-variable # On incrémente l'indice i trouvé indices[i] += 1 # On affecte tous les indices suivants i # à i+2, i+2, etc pour avoir notre suite croissante # sans répétition for j in range(i + 1, k): indices[j] = indices[j-1] + 1 # On renvoie le tuple associé à indices combins.append(tuple(sequence[i] for i in indices)) return combins def affiche_complex_recupere_combinaisons(): """Affiche la complexité en calcul de recupere_combinaisons. Spécifications PRÉCISES (pensons aux tests automatiques) : - l'affichage se fera en fonction de n, la taille de la séquence, et du paramètre k - utiliser UNIQUEMENT des caractères du pavé numérique de votre clavier, les lettres `n` et `k` et des caractères de ponctuation si besoin. """ print("n! / (k! * (n-k)!") # APPELER ICI la fonction teste() dans le cas ou le programme # est invoqué comme programme principal. if __name__ == "__main__": teste()