IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

random() x10 sans doublons


Sujet :

Algorithmes et structures de données

  1. #21
    Membre régulier Avatar de O( N )
    Homme Profil pro
    Développeur Web
    Inscrit en
    Juillet 2006
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : Juillet 2006
    Messages : 126
    Points : 120
    Points
    120
    Par défaut
    Bonjour a tous,

    je voudrais éclaircir un peu le problème (qui me plait bien)

    Le problème ici est : "Ne pas avoir de doublons dans les
    nombres pris au hazard" (je ne parle pas des cas
    particuliers qui offriraient des solutions certainements
    éllégantes voire simples)

    Pour çà deux solutions :

    Soit on cherche à chaque itération si le nombre pris est un
    doublon. => on reporte le problème sur "Trouvé un
    élément dans un ensemble".

    Soit on cherche à retirer les éléments déjà pris et le
    problème devient "Trouvé une structure d'informations
    permettant de sélectionné uniquement les éléments
    restants".

    je suis assez content de partager la même réponse que
    vous sur la complexité en O(N) (ou O(random(N)) = 0(1))
    avec équiprobabilité garantit

    Je peux vous dire qu'il existe mieux pour ce qui est de la
    complexité temporelle, je crois dire sans me tromper en
    O(random(N)) uniquement.

    Pensez-vous trouver l'idée ?

    Elle n'est pas trés compliquée et demande de connaître
    une technique algorithmique.

    Je ne vous donnerez pas la solution, car ce qui est
    intéressant n'est pas d'avoir la solution d'un problème mais
    comprendre comment on y est arrivé. (Généralement en ce
    posant de bonnes questions, ce qui reste évident à dire
    malheureusement pour nous !)

    Il nous resterait à améliorer la fonction random(N) pour
    être certain qu'elle soit en O(1)
    Dans la vie il faut se cultiver ! Je suis développeur,
    je cultive des bogues.

    Citer c'est avouer qu'on a les mêmes idées que d'autres
    sans être capable de faire des phrases soit même ! - moi

  2. #22
    Membre éprouvé

    Profil pro
    Inscrit en
    Juillet 2006
    Messages
    1 448
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations forums :
    Inscription : Juillet 2006
    Messages : 1 448
    Points : 1 234
    Points
    1 234
    Par défaut
    Citation Envoyé par O( N )
    Je ne vous donnerez pas la solution, car ce qui est
    intéressant n'est pas d'avoir la solution d'un problème mais
    comprendre comment on y est arrivé.
    (Généralement en ce
    posant de bonnes questions, ce qui reste évident à dire
    malheureusement pour nous !)
    Intéressant, demander le chemin sans évoquer la destination.
    Au fait, tu préfères lequel des 8 ?
    Most Valued Pas mvp

  3. #23
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    Il nous resterait à améliorer la fonction random(N) pour
    être certain qu'elle soit en O(1)
    En C me semble t-il, la fonction de random est un générateur congruentiel linéaire (dans la plupart des cas, c'est un tel générateur qui est défini).

    C'est défini par 4 entiers :

    -m : module
    -a : multiplicateur (entre 1 et m strictement)
    -c : un entier entre 0 et m
    -X(0) : une valeur initiale (souvent obtenu avec le temps)

    La fonction s'écrit :
    X(n+1) = (aX(n)+c) mod m

    Ce qui fait que dans ce cas, le random est bien en O(1).

    [edit] Zut, lorsque j'ai écrit ça, je croyais que j'étais sur le forum de C, enfin, tant pis, puisque la plupart des générateurs sont écrits comme ça, ça s'appliquera également pour l'algo

    [edit 2]
    Dans drand48 sous linux (si on regarde la page du manuel), on a :
    a = 3740067437
    c = 11^8
    m = 2^48
    Je ne répondrai à aucune question technique en privé

  4. #24
    Membre régulier Avatar de O( N )
    Homme Profil pro
    Développeur Web
    Inscrit en
    Juillet 2006
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : Juillet 2006
    Messages : 126
    Points : 120
    Points
    120
    Par défaut
    Sympas,
    je connaissais pas le fonctionnement de l'aléatoire
    j'imaginais une fonction tres tres compliquée issue de la théorie mathématiques du chaos ou un truc de ce genre.

    Donc pas abordable simplement pour la comprennette

    Pour le temps, je me doutais bien qu'il y avait un truc de ce genre la dedans.

    Pour être tous d'accord, Chez moi j'avais trouvé un algo en
    O(N) pour le temps et O(N) pour l'espace qui me trouvez N
    nombres aléatoires sans doublons compris entre 1 et Max.
    avec 0 < N <= Max.
    Dans la vie il faut se cultiver ! Je suis développeur,
    je cultive des bogues.

    Citer c'est avouer qu'on a les mêmes idées que d'autres
    sans être capable de faire des phrases soit même ! - moi

  5. #25
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Attention, ça, ça ne génère que du hasard faible, pas du hasard fort, qui ne peut être obtenu par calcul, mais que par observation d'un processus physique - genre bruit d'une diode -

  6. #26
    Membre régulier Avatar de O( N )
    Homme Profil pro
    Développeur Web
    Inscrit en
    Juillet 2006
    Messages
    126
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur Web

    Informations forums :
    Inscription : Juillet 2006
    Messages : 126
    Points : 120
    Points
    120
    Par défaut
    On peut pas mélanger les techniques mathématiques du
    chaos avec le temps, çà ne ferait pas un hazard intéressant ?
    Dans la vie il faut se cultiver ! Je suis développeur,
    je cultive des bogues.

    Citer c'est avouer qu'on a les mêmes idées que d'autres
    sans être capable de faire des phrases soit même ! - moi

  7. #27
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Non. Le mieux, c'est le bruit physique, il n'est pas prévisible, tout le reste l'est à plus ou moins à grande échelle.

  8. #28
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    Même ici avec la technique utilisée, on utilise une fonction f tel que : X(n+1) = f(X(n)), et comme la suite X est dans un intervalle entier fini, X sera périodique forcement à partir d'un certain rang. Donc, prévisible avec certains types de tests (il y a des séries de tests que l'on fait en général pour montrer qu'un générateur est un bon générateur).

    Mais en principe, ça suffit pour des applications "normales".

    Mais là, c'est un autre sujet...
    Je ne répondrai à aucune question technique en privé

  9. #29
    Expert confirmé
    Avatar de Pragmateek
    Homme Profil pro
    Formateur expert .Net/C#
    Inscrit en
    Mars 2006
    Messages
    2 635
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Formateur expert .Net/C#
    Secteur : Conseil

    Informations forums :
    Inscription : Mars 2006
    Messages : 2 635
    Points : 4 062
    Points
    4 062
    Par défaut
    f sera périodique forcement
    Pas si elle converge; dans ce cas elle devient stationnaire à partir d'un certain rang.
    Formateur expert .Net/C#/WPF/EF Certifié MCP disponible sur Paris, province et pays limitrophes (enseignement en français uniquement).
    Mon blog : pragmateek.com

  10. #30
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    En fait, c'est X qui sera périodique à partir d'un certain rang, j'ai rectifié

    Et si X devient stationnaire, elle est quand même périodique.
    Je ne répondrai à aucune question technique en privé

  11. #31
    Membre expérimenté Avatar de 10_GOTO_10
    Profil pro
    Inscrit en
    Juillet 2004
    Messages
    885
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2004
    Messages : 885
    Points : 1 522
    Points
    1 522
    Par défaut
    Citation Envoyé par O( N )
    Je peux vous dire qu'il existe mieux pour ce qui est de la
    complexité temporelle, je crois dire sans me tromper en
    O(random(N)) uniquement.

    Pensez-vous trouver l'idée ?

    Citation Envoyé par Quelqu'un dans l'autre post
    En fait il s'agit nom pas de générer des nb aléatoires, mais de sortir une série donnée dans un ordre aléatoire.
    Il suffit donc de tirer un nombre aléatoire A entre 1 et N! (le nombre d'arrangements possible de N nombres). Ensuite, il suffit d'établir une correspondance entre chaque A et un arrangement des N nombres.

    Aucune boucle, on ne peut pas faire moins complexe.

    Ca c'est la théorie. Parce qu'en pratique, si N = 500, ça suppose de tirer un nombre entre 1 et 500! , ce qui fait... un certain nombre. Et de mémoriser les correspondances entre les 500! nombres aléatoires et les 500! arrangements des 500 nombres.

    Bon, c'est peut-être pas franchement utilisable, ma solution.

  12. #32
    Invité
    Invité(e)
    Par défaut
    Bonjour,

    Je n'ai pas lu tout le topic, mais je vais essayer de proposer une solution, qui n'est pas algorithmique du tout (enfin, qui dépend fortement du language...)

    Tu veux utiliser php, et dans php, il y'a une fonction qui s'appelle shuffle()

    Citation Envoyé par http://fr.php.net/manual/fr/function.shuffle.php
    bool shuffle ( array &array )

    shuffle() mélange les éléments du tableau array.

    Note : Cette fonction assigne de nouvelles clés pour les éléments du paramètre array. Elle effacera toutes les clés existantes que vous aviez pû assigner, plutôt que de réordonner les clés.
    ceci devrait te permettre de continuer

Discussions similaires

  1. [C#] checkbox et random sans doublons
    Par fredza dans le forum Développement Windows
    Réponses: 2
    Dernier message: 03/08/2011, 19h12
  2. Comment remplir un tableau avec random sans doublon ?
    Par muntu dans le forum Collection et Stream
    Réponses: 15
    Dernier message: 16/07/2010, 10h42
  3. remplir un tableau sans doublons ...
    Par ryo-san dans le forum C
    Réponses: 22
    Dernier message: 10/11/2005, 13h43
  4. [Postgresql] insertion sans doublon
    Par Pwill dans le forum Décisions SGBD
    Réponses: 3
    Dernier message: 08/06/2005, 12h37
  5. Comment mettre à jour une ligne sans doublon via déclencheur
    Par fuelcontact dans le forum MS SQL Server
    Réponses: 2
    Dernier message: 02/08/2004, 16h56

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo