Exercices sur les recherches de sous-séquences – Solutions possibles

Ce qui suit donne quelques solutions possibles aux exercices portant sur la recherche de sous-séquences. Vous aurez peut-être même trouvé mieux, qui sait?

Analyse préalable

Avant d'aborder une série d'exercices, mieux vaut réfléchir un peu à ce qui nous est proposé. Je vous invite à relire brièvement les consignes qui vous ont été données lors de la séance S04.

En regardant tout cela de plus près, il me semble apparent que certaines opérations réapparaîtront à plusieurs reprises dans le code :

Dans ma démarche de solution personnelle, j'y suis allé de manière graduelle :

Dans certains cas, je pourrais aller plus loin, mais je ne suis pas certain que cela aiderait à la lisibilité.

Programme principal

Mon programme principal consiste en une série de tests affichant des résultats à l'écran. C'est une manière parmi plusieurs de procéder; j'aurais aussi pu faire un programme interactif (je le fais rarement, pour être honnête, car les tests deviennent vite fastidieux), ou encore un programme validant les tests par des assertions dynamiques.

Les tests proposés ne sont pas exhaustifs; j'ai demandé plus de vous dans ma liste d'exigences (votre fonction devra fonctionner avec...) mais je triche un peu du fait que je connais bien les pièges qui nous guettent ici. Ne soyez pas complaisantes ou complaisants, et testez votre code avec rigueur.

#include <algorithm>
#include <utility>
#include <ostream>
#include <string>
#include <vector>
#include <locale>
#include <tuple>
#include <numeric>
//
// outils divers...
//
// fonction à écrire...
//
// code de test...
//
#include <iostream>
int main() {
   using namespace std;
   int vals[] { 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 6, 6 };
   for (int i = 0; i < 6; ++i)
      tester_trouver_consecutifs(begin(vals), end(vals), i, cout);
   tester_plus_longue_sequence(begin(vals), end(vals), cout);
   tester_plus_longue_sequence(
      begin(vals), end(vals), [](int n) {
         return n % 2 != 0;
      }, "entiers impairs", cout
   );
   string tests[] {
      "   j'aime mon   prof! ",
      "j'aime mon prof!",
      "",
      "j'aime mon   prof! ",
      "   j'aime mon   prof!",
      "x"
   };
   tester_inverser_mots(begin(tests), end(tests), cout);
   tester_inverser_lettres(begin(tests), end(tests), cout);
}

Fonctions de tests

Comme le montre le programme principal, plus haut, j'ai écrit des fonctions de test pour chacun des algorithmes à tester. À noter :

  • J'ai passé un flux en sortie à chacune d'elles, pour qu'il soit plus facile d'envoyer les résultats dans un fichier si je le souhaite. Pour mes tests, j'ai utilisé la sortie standard (modélisée par std::cout) mais ce n'est qu'une option parmi plusieurs
  • Je me trouvais à afficher les éléments d'une séquence à quelques reprises, ce que j'ai refactorisé en un algorithme d'affichage sur un flux (fonction afficher_sequence())
  • Ce que les fonctions de tests font est appeler les fonctions à écrire et afficher des résultats. Ce n'est pas le rôle des algorithmes que nous avions à développer que d'écrire à la console, après tout
template <class It>
   void tester_trouver_consecutifs(It debut, It fin, int n, std::ostream &os) {
      using namespace std;
      afficher_sequence(debut, fin, os);
      os << '\n';
      if (auto pos = trouver_consecutifs(debut, fin, n); pos == fin)
         os << "Pas de sous-sequence de longueur " << n << " dans cette sequence\n" << endl;
      else
         os << "La 1re sous-sequence de longueur " << n << " dans cette sequence debute a la position "
            << distance(debut, pos) << '\n' << endl;
   }

template <class It>
   void tester_plus_longue_sequence(It debut, It fin, std::ostream &os) {
      using namespace std;
      if (auto res = plus_longue_sequence(debut, fin); res.first == res.second)
         os << "La sequence est vide\n";
      else {
         os << "La plus longue sequence est de longueur " << distance(res.first, res.second)
            << " et contient ";
         afficher_sequence(res.first, res.second, os);
         os << '\n';
      }
      os << endl;
   }

template <class It, class Pred>
   void tester_plus_longue_sequence
      (It debut, It fin, Pred pred, const std::string &presentation_predicat, std::ostream &os) {
      using namespace std;
      if (auto res = plus_longue_sequence(debut, fin, pred);res.first == res.second)
         os << "La sequence est vide\n";
      else {
         os << "La plus longue sequence de " << presentation_predicat << " est de longueur "
            << distance(res.first, res.second) << " et contient ";
         afficher_sequence(res.first, res.second, os);
         os << '\n';
      }
      os << endl;
   }

template <class It>
   void tester_inverser_mots(It debut, It fin, std::ostream &os) {
      using namespace std;
      for_each(debut, fin, [&os](const string &s) {
         os << "Avant : \"" << s << "\"\nApres : \"" << inverser_mots(s) << "\"\n" << endl;
      });
   }

template <class It>
   void tester_inverser_lettres(It debut, It fin, std::ostream &os) {
      using namespace std;
      for_each(debut, fin, [&os](const string &s) {
         os << "Avant : \"" << s << "\"\nApres : \"" << inverser_lettres(s) << "\"\n" << endl;
      });
   }

Algorithmes à écrire

L'approche que j'ai pris pour chacun des algorithmes qui devaient être écrits va comme suit.

Pour la fonction trouver_consecutifs(debut,fin,n), ma vision des choses était :

  • Prenons chacune des sous-séquences de la séquence , dans l'ordre
  • Évaluons sa taille avec la fonction distance()
  • Si la taille est au moins n, alors nous avons trouvé
  • Si nous n'en trouvons aucune, ou encore si n est déraisonnable (selon ma lecture, cela signifie ), alors l'algorithme retourne fin, signifiant que rien de pertinent n'a été trouvé

Mon implémentation repose sur l'outil consecutifs(debut,fin), qui retourne une paire représentant la sous-séquence d'éléments de valeur consécutive dans

template <class It>
   It trouver_consecutifs(It debut, It fin, int n) {
      using namespace std;
      if (debut == fin || n <= 0) return fin;
      for (auto p = consecutifs(debut, fin); p.second != fin; debut = p.second, p = consecutifs(debut, fin))
         if (distance(p.first, p.second) >= n)
            return p.first;
      return fin;
   }

Pour la fonction plus_longue_sequence(debut,fin), ma vision des choses était :

  • Prenons chacune des sous-séquences d'éléments de même valeur de la séquence , dans l'ordre
  • Évaluons sa taille avec la fonction distance()
  • Conservons les extrémités de cette sous-séquence s'il s'agit de la plus longue trouvée jusqu'ici

Mon implémentation repose sur l'outil consecutifs(debut,fin), qui retourne une paire représentant la sous-séquence d'éléments consécutifs de même valeur dans

Il est clair que plus_longue_sequence(debut,fin) sera en moyenne plus lente que trouver_consecutives(debut,fin,n) puisque cette dernière pourra s'arrêter dès qu'une sous-séquence convenable aura été trouvée.

Il serait possible d'optimiser plus_longue_sequence() dans le cas des itérateurs autres que ceux de catégorie Random Access en conservant la longueur de la plus longue sous-séquence trouvée dans une variable temporaire.

Notez que j'ai utilisé un mécanisme de C++ 17 nommé les Compile-Time Argument Deduction pour déduire pair<It,It> à partir de pair(fin,fin). J'aurais aussi pu utiliser make_pair(fin,fin) avec un compilateur plus âgé.

template <class It>
   std::pair<It,It> plus_longue_sequence(It debut, It fin) {
      using namespace std;
      auto res = pair{ fin, fin };
      for (auto p = consecutifs(debut, fin); p.second != fin; debut = p.second, p = consecutifs(debut, fin))
         if (distance(p.first, p.second) >= distance(res.first, res.second))
            res = p;
      return res;
   }

Pour la fonction plus_longue_sequence(debut,fin,pred), ma vision des choses était :

  • Prenons chacune des sous-séquences d'éléments satisfaisant le prédicat pred de la séquence , dans l'ordre
  • Évaluons sa taille avec la fonction distance()
  • Conservons les extrémités de cette sous-séquence s'il s'agit de la plus longue trouvée jusqu'ici

Mon implémentation repose sur l'outil consecutifs(debut,fin,pred), qui retourne une paire représentant la sous-séquence d'éléments consécutifs satisfaisant le prédicat pred dans

Pour que l'algorithme fonctionne, il faut comprendre que par définition, une séquence sera faite d'une alternance de sous-séquences satisfaisant, puis ne satisfaisant pas, le prédicat. C'est pourquoi j'ai défini l'outil negation_logique(pred) qui retourne un prédicat qui ne sera vrai pour un certain paramètre arg que si pred(arg) est faux; ceci facilite l'implémentation de cette alternance.

Le test suivant la répétitive couvre le cas où la plus longue sous-séquence terminerait la séquence originale.

J'ai utilisé ici encore un mécanisme de C++ 17 nommé les Compile-Time Argument Deduction pour déduire pair<It,It> à partir de pair(fin,fin). J'aurais aussi pu utiliser make_pair(fin,fin) avec un compilateur plus âgé.

template <class It, class Pred>
   std::pair<It, It> plus_longue_sequence(It debut, It fin, Pred pred) {
      using namespace std;
      auto res = pair{ fin, fin };
      auto p = consecutifs(debut, fin, pred);
      for (; debut = p.second, p = consecutifs(debut, fin, negation_logique(pred)), p.second != fin;
           debut = p.second, p = consecutifs(debut, fin, pred))
         if (distance(p.first, p.second) >= distance(res.first, res.second))
            res = p;
      if (distance(p.first, p.second) >= distance(res.first, res.second))
         res = p;
      return res;
   }

J'ai groupé inverser_mots() et inverser_lettres() dans un même bloc, puisque l'essentiel des deux algorithmes est identique. En effet, il s'agit de :

  • Découper la séquence originale en groupes de blancs et de non-blancs. Pour des raisons de simplicité, j'ai choisi de prendre des paires d'itérateurs dans chaque cas pour retenir le début et la fin de chacune des sous-séquences, mais on aurait aussi pu copier les données, donc le texte des sous-séquences
    • j'ai écrit la fonction separer_sous_sequences(debut,fin,pred) pour ce faire, puisque la logique était la même dans chaque cas
    De démarer la séquence de destination par des blancs seulement si la séquence source débutait par un blanc. J'ai abstrait ceci en « démarrer la séquence en notant si le prédicat s'avère pour son premier élément »
  • Construire deux séquences de sous-séquences, soit les blancs et les mots (les « non-blancs »)
  • Transformer certaines sous-séquences. Ceci varie selon les algorithmes :
    • dans le cas de la fonction inverser_mots(), on parle d'inverser l'ordre des mots
    • dans le cas de la fonction inverser_lettres(), on parle d'inverser l'ordre des lettres dans chaque mot
  • Ensuite, fusionner les sous-séquences en alternance, commençant par la séquence de sous-séquences la plus opportune, et
  • Retourner la concaténation de toutes ces sous-séquences. J'ai utilisé std::accumulate() pour ce faire

Il y aurait lieu d'optimiser encore l'une et l'autre, mais j'ai choisi d'arrêter ici par souci de lisibilité.

J'ai utilisé dans separer_sous_sequences() des Structured Bindings de C++ 17 pour alléger l'écriture. Ce n'est évidemment pas nécessaire (j'aurais pu utiliser les paires en tant que paires, tout simplement). J'ai fait de même dans inverser_mots() et dans inverser_lettres() pour récupérer les deux vecteurs retournées par separer_sous_sequences()

 

template <class It, class Pred>
   auto separer_sous_sequences(It debut, It fin, Pred pred) {
      using namespace std;
      vector<pair<It, It>> oui, non;
      for (bool use_neg = pred(*debut); debut != fin; use_neg = !use_neg)
         if (use_neg) {
            auto [d,f] = consecutifs(debut, fin, negation_logique(pred));
            oui.emplace_back(debut, f);
            debut = f;
         } else {
            auto [d,f] = consecutifs(debut, fin, pred);
            non.emplace_back(debut, f);
            debut = f;
         }
      return pair{ oui, non };
   }

std::string inverser_mots(std::string s) {
   using namespace std;
   using It = string::iterator;
   if (s.empty()) return s;
   const auto &loc = locale{ "" };
   auto [blancs, mots] = separer_sous_sequences(begin(s), end(s), est_blanc(loc));
   reverse(begin(mots), end(mots));
   auto v = isspace(s.front(), loc) ?
      fusionner_alternance(std::move(blancs), std::move(mots)) :
      fusionner_alternance(std::move(mots), std::move(blancs));
   return accumulate(begin(v), end(v), string{}, [](const string &s, auto &&p) {
      return s + string(p.first, p.second);
   });
}

std::string inverser_lettres(std::string s) {
   using namespace std;
   using It = string::iterator;
   if (s.empty()) return s;
   const auto &loc = locale{ "" };
   auto [blancs, mots] = separer_sous_sequences(begin(s), end(s), est_blanc(loc));
   for(auto & p : mots)
      reverse(p.first, p.second);
   auto v = isspace(s.front(), loc) ?
      fusionner_alternance(std::move(blancs), std::move(mots)) :
      fusionner_alternance(std::move(mots), std::move(blancs));
   return accumulate(begin(v), end(v), string{}, [](const string &s, auto &&p) {
      return s + string(p.first, p.second);
   });
}

Outils construits en cours de route

Ce qui suit montre des outils construits au fur et à mesure de ma progression à travers les exercices proposés.

La fonction consecutifs(debut,fin,pred) retourne une paire d'éléments pour lesquels s'avère. Il se peut que debut==f, signifiant une séquence vide, dans le cas où !pred(*debut)

template <class It, class Pred>
   std::pair<It, It> consecutifs(It debut, It fin, Pred pred) {
      return { debut, std::find_if(debut, fin, pred) };
   }

La fonction consecutifs(debut,fin) retourne une paire d'éléments pour lesquels *debut==e. Il se peut que debut==f, signifiant une séquence vide, dans le cas où !pred(*debut).

J'ai utilisé une syntaxe compacte de C++ 14 pour la capture de ma λ, soit [x = *debut] signifiant « fait une copie de *debut à la construction et nomme-la», mais cette manoeuvre n'est pas essentielle à la fonction (on aurait pu faire la même chose avec une variable locale).

template <class It>
   std::pair<It, It> consecutifs(It debut, It fin) {
      return debut == fin?
                std::make_pair(debut,fin) :
                consecutifs(debut, fin, [x = *debut](auto val) { return val != x; });
   }

La fonction negation_logique(pred) retourne un foncteur qui prend un paramètre arg quelconque dont l'opérateur () retourne la négation de pred(arg). On aurait pu écrire, avc C++ 11 ou avant, ceci :

template <class Pred>
   class negation_logique_ {
      Pred pred;
   public:
      negation_logique_(Pred pred) : pred{ pred } {
      }
      template <class T>
         bool operator()(const T &arg) {
            return !pred(arg);
         }
   };
template <class Pred>
   negation_logique_<Pred> negation_logique(Pred pred) {
      return { pred };
   }

... et obtenir du code machine pleinement équivalent, mais ça aurait été plus laborieux.

template<class Pred>
   auto negation_logique(Pred pred) {
      return [=](auto arg) { return !pred(arg);  };
   }

La fonction est_blanc(loc) retourne un prédicat foncteur qui retournera true pour un caractère c seulement si c est un blanc au sens de loc.

auto est_blanc(const std::locale &loc) {
   return [&loc](char c) { return std::isspace(c, loc); };
}

La fonction afficher_sequence(debut,fin,pos) affichera les éléments de sur os, intercalant un espace entre chaque paire d'éléments.

template <class It>
   void afficher_sequence(It debut, It fin, std::ostream &os) {
      using namespace std;
      if (debut == fin) return;
      os << *debut;
      for_each(next(debut), fin, [&os](auto val) { os << ' ' << val; });
   }

La fonction fusionner_alternance(premier,second) est particulière au sens où elle est destinée à un usage « interne ». Elle suppose que premier est au moins aussi grand (en termes de nombre d'éléments) que second, responsabilité qui incombe au code client (c'est une précondition de la fonction) et qui n'est pas validée.

Son rôle est de construire et de retourner un conteneur contenant des éléments de premier et de second en alternance, commençant par premier. Le conteneur construit puis retourné sera du même type que celui des conteneurs premier et second.

J'ai utilisé res.insert(end(res),*q) pour l'insertion de manière à être plus général que push_back(), qui n'est pas supporté par tous les types de conteneurs.

//
// precondition: premier.size() >= second.size()
//
template <class T, class R = T>
   R fusionner_alternance(T premier, T second) {
      using namespace std;
      R res;
      for (auto p = begin(premier), q = begin(second); p != end(premier); ++p) {
         res.insert(end(res), *p);
         if (q != end(second)) {
            res.insert(end(res), *q);
            ++q;
         }
      }
      return res;
   }

Valid XHTML 1.0 Transitional

CSS Valide !