Inscription / Connexion Nouveau Sujet
Niveau calculatrices
Partager :

Algorithme

Posté par
puisea Posteur d'énigmes
17-07-07 à 21:22

Bonsoir à tous,

Je suis à la recherche de l'algorithme le plus efficace possible pour tirer n nombres entiers positifs aléatoires différents les uns des autres et tous inférieurs à p. (Avec n < p).

Le premier algorithme qui vient à l'esprit, est de tirer un nombre aléatoirement dans l'intervalle voulu et de le comparer aux nombres déjà tirés. S'il a déjà été tiré on recommence la manip' et sinon on le garde. Mais lorsqu'on va arriver au tirage des derniers nombres cela devient moins performant étant donné que les chances de tirer un nombre une nouvelle fois augmentent...

Voila, voila... Merci d'avance.

PS : à noter que cela sera programmé en PHP par la suite.

Posté par
jamo Moderateur
re : Algorithme 17-07-07 à 21:29

Bonsoir,

imaginons qu'on crée une liste des n nombres de 1 à n. Tu en tires un au hasard, et tu le retires de la liste qui n'en contient plus que n-1 (en prenant le dernier de la liste et en le mettant à la place de celui tiré. Ensuite, tu retires un nombre au hasard dans cette liste de n-1 nombres, qui n'en contient plus que n-2. Etc ...

Et voilà, en p tirages, tu as ta liste !

Posté par
puisea Posteur d'énigmes
re : Algorithme 17-07-07 à 21:37

Oui je suis entièrement d'accord jamo

Seulement pour programmer ca en PHP, là je coince... Ce n'est pas vraiment un langage adapté aux listes

Tu as peut-être une idée ?

Posté par
jamo Moderateur
re : Algorithme 17-07-07 à 21:40

J'avoue ne pas connaitre le PHP.

Les tableaux n'existent pas ?

Sinon, un petit tour sur le forum http://www.developpez.com/ et tu auras vite ta réponse, étant donné que ton problème est purement d'ordre informatique

Posté par
jamo Moderateur
re : Algorithme 17-07-07 à 21:43

Sinon, j'ai bien une autre idée, mais je ne sais pas quelle sera la qualité d'un point de vue "aléatoire".

Elle consiste à avoir une seule liste des n nombres entiers, et à lui appliquer un certain nombre de permutations de 2 nombres, ceux-ci étant pris au hasard.

Cela ne permet de n'avoir qu'un seul tableau.

Par contre, je ne sais pas combien de fois il faut faire des permutations pour avoir une vraie liste "aléatoire" ??

Posté par
critou
re : Algorithme 17-07-07 à 21:44

PHP n'est pas adapté aux listes, mais les tableaux ça passe, donc peut-être que ceci pourrait t'aider : (en remplissant le tableau des entiers de 1 à p)

Posté par
jamo Moderateur
re : Algorithme 17-07-07 à 21:46

Bonsoir critou,

j'ai l'impression que le programme que tu lui proposes fonctionne comme ce qu'il avait décrit au début et qui semblait l'embeter.

Mais bon, tout dépend si ses valeurs de n et p sont grandes, ce n'est sans doute pas si long que ça ...

Posté par
puisea Posteur d'énigmes
re : Algorithme 17-07-07 à 21:47

Oui les tableaux existent, mais ils ne sont pas très simples d'utilisation.

Effectivement pour le forum, c'est la solution la plus directe.

Ton autre idée soulève une question intéressante, à partir de quand quelque chose de "mixé" devient aléatoire ?

Je vais me rabattre sur un autre forum pour la réponse informatique. Merci.

Posté par
jamo Moderateur
re : Algorithme 17-07-07 à 21:49

De toute façon, cela restera pseudo-aléatoire, quoi qu'on fasse !

Mais tout dépend de ton application, ça peut suffire, on peut se contenter d'un "petit mélange" parfoisà la place d'un vrai tirage aléatoire, c'est suffisant

Posté par
puisea Posteur d'énigmes
re : Algorithme 17-07-07 à 21:50

Et bien à vrai dire pour être plus précis, dans le cas que je veux programmer p=52 et n est soit 9, soit 17. Donc programmer de la manière de mon premier post n'est pas si long que ca, mais bon c'était histoire de voir si une solution plus élégante et adaptée au PHP existait (ce qui doit sans aucun doute être le cas).

Posté par
critou
re : Algorithme 17-07-07 à 21:51

Sais pas trop, moi et PHP ça fait deux
Je ne crois pas, vu qu'on supprime les éléments du tableau au fur et à mesure qu'on les tire, il n'y a pas moyen de retomber sur une valeur déjà tirée... ça fait bien un unique tirage par valeur.
Ça ressemble plus à ton idée avec les listes je trouve

Posté par
puisea Posteur d'énigmes
re : Algorithme 17-07-07 à 21:53

La méthode de ton lien critou est celle de mon post initial (mais merci quand même, ce sera toujours ca de moins à taper ! )

Posté par
puisea Posteur d'énigmes
re : Algorithme 17-07-07 à 21:54

Euh non, en fait je n'ai rien dit, il s'agit bien de la méthode proposée par jamo avec les listes.

Posté par
critou
re : Algorithme 17-07-07 à 21:59

Il y a ça aussi (plus simple, fonction préexistante) : http://fr3.php.net/manual/fr/function.array-rand.php



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !