Tirer un élément aléatoire parmi les plus grands éléments d'un std::vector

Bonjour je suis étudient et je travaille actuellement sur un alpha-beta dans un jeux ou il est fréquent que plusieurs coup aient la même valeurs.

Mettons que mon algorithme me sorte le tableau de tuple (coup, valeur) suivant :

[c1:23, c2:-9, c3:23, c4:12, c5:23]

Je souhaite choisir un coup aléatoirement parmi c1, c3 et c5. Je voudrais donc savoir si la STL permet de faire ça simplement.

Merci d'avance.

je dirai oui, en utilisant un std::sort et un comparator bien pensé

Si le problème est de tirer un indice pair/impair :

Code:

---

1 2 3 4 5

std::vector<std::tuple<Coup,Valeur>> v;   int indice_pair = std::rand() % (v.size() / 2) * 2; int indice_impair = std::rand() % ((v.size()-1) / 2) * 2 + 1;

---

Citation:

---

Envoyé par leternel

je dirai oui, en utilisant un std::sort et un comparator bien pensé

---

Merci pour ta réponse, si je comprend bien, je modifie mon comparateur de tuple

Code:

---

1 2 3 4

bool tupleCoup::greater(std::tuple<Coup, int> a, std::tuple<Coup, int> b) { return std::get<1>(a) > std::get<1>(b); }

---

de la manière suivante :

Code:

---

1 2 3 4 5 6 7 8

bool tupleCoup::greater(std::tuple<Coup, int> a, std::tuple<Coup, int> b) { if (std::get<1>(a) > std::get<1>(b)) return true; else if (std::get<1>(a) == std::get<1>(b)) return ((rand()%100) >= 50); return false; }

---

La liste est bien triée dans l'ordre décroissant mais les élléments egaux sont mélangés.

Merci pour ton aide :ccool:

Il serait intéressant de faire des tests pour voir si la répartition est bonne. Il est probable que c1, c3 et c5 n'aient pas une chance sur trois d'être tiré chacun.

Je conseille la lecture de http://en.wikipedia.org/wiki/Fisher%...ing_algorithms

Sinon, et si tu n'as pas des contraintes de perf trop drastiques, un simple tri, un comptage du nombre de valeurs identiques, puis un choix parmi ces valeurs me semble le plus simple.

Citation:

---

Envoyé par Iradrille

Il serait intéressant de faire des tests pour voir si la répartition est bonne. Il est probable que c1, c3 et c5 n'aient pas une chance sur trois d'être tiré chacun.

---

En effet, la répartition dépend du tri implémenté par std::sort, (cf. ici), mais bon on peut pas vraiment savoir quel tri est (sera) implémenté, du coup ça semble difficile de prédire si la répartition sera uniforme ou non (de toute façon les stateux dirons que ça suit une loi normale :P). Mais à la rigueur c'est pas grave.

Citation:

---

Envoyé par JolyLoic

Je conseille la lecture de http://en.wikipedia.org/wiki/Fisher%...ing_algorithms

Sinon, et si tu n'as pas des contraintes de perf trop drastiques, un simple tri, un comptage du nombre de valeurs identiques, puis un choix parmi ces valeurs me semble le plus simple.

---

Enfaite j'ai plus des contraintes de perf (l'algo s'exécute sur un temps limité) que sur répartition. Tout ce qui compte c'est que mon IA ne bouge pas tout le temps le même pion (dans ce jeu il est très risqué et du coup l'IA campe).

Citation:

---

Envoyé par ahoff

En effet, la répartition dépend du tri implémenté par std::sort, (cf. ici), mais bon on peut pas vraiment savoir quel tri est (sera) implémenté, du coup ça semble difficile de prédire si la répartition sera uniforme ou non (de toute façon les stateux dirons que ça suit une loi normale :P). Mais à la rigueur c'est pas grave.

---

Que ce soit un Quicksort ou autre, ça sera un tri en O(n log(n)), je vois mal la STL implémenter un BubleSort ou autre en O(n²), bien que ça peut être plus rapide dans certains cas précis.
(Enfin il est possible que le type de tri change en fonction de la taille du conteneur, mais c'est à prendre en compte ici)

Du coup, comme propose JolyLoic, si tu fais un tri "normal" (O(n log(n)), suivi d'une recherche linéaire pour trouver le nombre de coups optimaux (O(n)), suivi d'un choix aléatoire parmi ces coups optimaux (O(1)), tu restes en O(n log(n)) mais avec une meilleure répartition. :)

Voire même, si tu te moques de louper certains résultats, tu fais un partial_sort pour ne récupérer que les 15 premiers résultats (c'est du n log(m), avec m = 15, quelque soit n). Ensuite, parmi les valeurs égales dans ces 15 premiers résultats, tu sélectionne un au hasard.