Skip to content

Sujet

RAPPELS :

  • cet examen est purement formatif, autrement dit, pas de note prise en compte ;
  • pour que ce soit utile pour toi, il faut jouer le jeu et donc respecter les consignes ;
  • et donc, la correction ne doit surtout pas être regardée avant la fin des 1h30 d'examen ;

Introduction

Dans ce premier examen BPI, nous allons développer un programme qui ne sert à pas grand chose. En effet, ce qu'on cherche à faire est déjà fourni en standard dans Python. Mais comme on est archi-motivé, on va le recoder par nous mêmes, comme ça, pour le fun.

En plus du fun, on a quand même deux autres bonnes raisons d'écrire un programme qui ne sert pas à grand chose :

  • évaluer nos propres compétences concernant les bases de la programmation impérative, et ça c'est déjà un bel objectif !

  • comprendre l'algorithme sous-jacent implémenté dans Python. Et comprendre, c'est bien non ?

Il faut déclencher ton chronomètre à partir de maintenant si tu décides de lire la suite. Tu vas avoir besoin d'1h30 de concentration, donc si tu n'as pas le temps, repasse plus tard.

Objectif ultime

Implémenter une fonction recupere_combinaisons(sequence, k) qui renvoie toutes les combinaisons de longueur k d'une séquence donnée. Lorsque l'on construit toutes les k-combinaisons d'une séquence, l'ordre des k éléments choisis ne compte pas : par exemple la combinaison 1,2,3 est la même que la combinaison 2,3,1. Une combinaison ne peut contenir qu'une seule fois chaque élément de la séquence donnée.

Consignes

  • faites bien attention aux éléments en gras dans le paragraphe "Objectif ultime" ci-dessus ;
  • le travail à effectuer se trouve dans les "docstring" et # TODO du squelette de programme Python disponible ici et affiché ci-dessous ;
  • il est recommandé d'implémenter les fonctions dans l'ordre dans lequel elles apparaissent dans le fichier, à l'exception du tout dernier #TODO qui doit être fait en premier ;
  • lire TOUT le fichier avant de coder ;
  • il faut respecter strictement les consignes, PENSER aux tests automatiques (les pauvres ...) ;
  • la durée de l'examen est 1h30 ;
  • internet n'est pas autorise ;
  • s'interroger sur la COMPLEXITÉ en calcul de chaque fonction ;
  • il est INTERDIT de rajouter des import ;
  • les méthodes split et strip de la classe str vous seront utiles ;
  • chose promise chose due, pylint sera lancé par les tests automatiques.

Squelette de code à compléter

#!/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
    # TODO
    ...

    # 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
    # TODO
    ...

    # affiche une ligne contenant EXACTEMENT la chaîne de caractère suivante :
    #   Résultats calculés par recupere_combinaisons_2("ABCD")
    # TODO
    ...

    # 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')
    # TODO
    ...

    # affiche une ligne vide
    # TODO
    ...

    # 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
    ...

    # 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)
    # TODO
    ...

    # affiche une ligne contenant EXACTEMENT la chaîne de caractère suivante :
    #   Resultats calculés par recupere_combinaisons([0, 1, 2, 3, 4], 3)
    # TODO
    ...

    # 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)
    # TODO
    ...

    # affiche une ligne vide
    # TODO
    ...

    # effectue l'appel recupere_parametre(x) avec x récupéré en tant que premier
    # argument de la ligne de commande.
    # TODO
    ...

    # 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
    # TODO
    ...

    # 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')
    # TODO
    ...

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
    """
    # TODO
    ...

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`.
    """
    # TODO
    ...

def renverse(sequence):
    """Renvoie une nouvelle séquence qui est la séquence donnée à l'envers."""
    # TODO
    ...

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`.
    """
    # TODO
    ...

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.
    """
    # TODO
    ...

# APPELER ICI la fonction teste() dans le cas ou le programme
# est invoqué comme programme principal.
# TODO
...

Cliquez ici pour révéler la correction.

Correction

Pour connaître ta note tu peux utiliser le programme de correction automatique fourni en suivant ces étapes:

  • télécharger le programme de correction automatique disponible ici et le placer dans le même répertoire que le programme combinaisons.py ;
  • télécharger le fichier input.txt disponible ici à côté de combinaisons.py et ./correction_auto.py ;
  • télécharger le fichier combinaisons_corrigee.py disponible ici toujours au même endroit ;
  • enfin, lancer la correction automatique avec ./correction_auto.py.

Le code de correction avec commentaires est également affiché ci-dessous :

#!/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()