Projet

Général

Profil

Rechercher rapidement dans une liste,

pour construire une liste à conditions par exemple voir exemple

Je veux faire une recherche les verbes dans une liste de mots indexée, une structure du genre QMap<int,QString> phraseBoileau et récupérer k 5 mots correspondant à ma recherche.

QMap<int,QString> phraseBoileau;
    maListe.insert(0,"ce");
    maListe.insert(1,"qui");
    maListe.insert(2,"se");
    maListe.insert(3,"conçoit");
    maListe.insert(4,"bien");
    maListe.insert(5,"s'énonce");
    maListe.insert(6,"clairement");
    maListe.insert(7,"et");
    maListe.insert(8,"les");
    maListe.insert(9,"mots");
    maListe.insert(10,"pour");
    maListe.insert(11,"le");
    maListe.insert(12,"dire");
    maListe.insert(13,"parviennent");
    maListe.insert(14,"aisément");

Je vais créer trois listes pour cela :
une liste dans laquelle j'écris toutes les keys existant dans ma QMap

QList<int> indexExistants = phraseBoileau.keys();

Index existants
0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|
0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|

une autre contenant autant d'éléments ordonnés que la première

QList<int> correspondance;
        for (int i = 0; i < indexExistants.count(); i++) 
      {
            correspondance << i;
        }

Correspondance
0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|
0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|

une dernière contenant les index déjà rencontrés, vide pour le moment

QList<int> indexUtilises;

Tant que je n'aurai pas atteint le nombre k de mots (ou la fin de ma liste, il est possible qu'elle contiennent moins de k mots intéressants)
Je vais utiliser un entier "nombreMotsTrouves" et un booléen "finListeAtteint" (initialisés à 0 et faux)

int nombreMotsTrouves=0;
bool finListeAtteint=false;
while (nombreMotsTrouves < k && !finListeAtteint)

Je vais tirer au sort un nombre inférieur ou égal au nombre d'éléments dans ma deuxième liste
int indexTirage = rand() % (correspondance.count());

par exemple 8
et enlever la valeur de la deuxième liste
int indexSorti = correspondance.takeAt(indexTirage);

Correspondance
0|1|2|3|4|5|6|7|8| 9|10|11|12|13|
0|1|2|3|4|5|6|7|9|10|11|12|13|14|

Comme je le tire dans la liste correspondance, je suis sûr que je ne peux jamais tirer un nombre déjà tiré, puisqu'ils ont été enlevés au fur et à mesure.
Si l'index que je viens de tirer n'a jamais été tiré avant

if (!indexUtilises.contains(indexSorti))

ici OK
alors je traite le mot "phraseBoileau[indexSorti]", j'ajoute "indexSorti" à la liste "indexUtilises", et j'augmente éventuellement "nombreMotsTrouves" d'1.
phraseBoileau8 n'est pas un verbe
indexUtilises << indexSorti;

indexUtilises
0|
8|
nombreMotsTrouves=0

Si j'ai atteint la fin de la liste par une des conditions
if(indexUtilises.count()>=indexExistants.count()||correspondance.count() <= 0)

J'utilise mon booléen pour arrêter ma boucle, mais mon nombre k n'est pas atteint (et il serait bon que je le signale à l'utilisateur, message du genre Il n'y a pas k verbes dans la phrase de Boileau)
finListeAtteint = true;

non, fin de liste pas atteinte, je refais un tirage dans
Correspondance
0|1|2|3|4|5|6|7|8| 9|10|11|12|13|
0|1|2|3|4|5|6|7|9|10|11|12|13|14|

Même si je retire 8, ce n'est pas un problème puisqu'il y a maintenant la référence à ma phrase 9 dans la case
Je retire 8
Correspondance
0|1|2|3|4|5|6|7| 8| 9|10|11|12|
0|1|2|3|4|5|6|7|10|11|12|13|14|
phraseBoileau9 n'est pas un verbe
indexUtilises
0|1|
8|9|
nombreMotsTrouves=0
Je tire 3
Correspondance
0|1|2|3|4|5|6| 7| 8| 9|10|11|
0|1|2|4|5|6|7|10|11|12|13|14|
phraseBoileau3 est un verbe
indexUtilises
0|1|2|
8|9|3|
nombreMotsTrouves=1
etc...

Dans mon cas, correspondance sera vide avant que nombreMotsTrouves atteigne 5 et je m'arrêterai là

Redmine Appliance - Powered by TurnKey Linux