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

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé
    Profil pro
    Inscrit en
    Janvier 2006
    Messages
    344
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2006
    Messages : 344
    Par défaut random() x10 sans doublons
    bonjour ,

    actuellement je fais un qcm en php/mysql

    et je souhaiterai 10 nombres aléatoires sans doublons

    donc pour l'instant ca donne ca:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     
     
    if (($nbquest>=0) and ($nbquest<=($maxquest-1))){//if1
     
    	for ($i=0;$i<$nbquest;$i++){//for1
     
    	    $num[$i]=rand(0,$maxquest);
    	    echo"num ->$num[$i]";
    	    echo"<br><br>";
     
    	}//end for1
     
    }//endif 1
    il y a une fonction array_unique() dans php qui enleve les doublons d'un tableau mais je n'ai plus 10 nombres

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
     
    $mynum=array_unique($num);
    echo "<pre>";
    print_r($mynum);
    echo "</pre>";				
    $nbnum=array_count_values($mynum);
    donc je me dis que peut-etre un algo...

    j aurai besoin un peu d ' aide car je ne sais pas pourquoi en algo je bute toujours


    merci

  2. #2
    Expert confirmé
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 40
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Par défaut
    Un truc bète que j'avais utilisé dans un de mes premiers projets universitaires :

    Tu as un tableau de 1 à n.

    Tu fais un random entre 1 et n, tu obtiens i. Tu déplace ce i à la fin du tableau. (échange le dernier élément du tableau avec celui en i).

    Tu refais un random entre 1 et n-1.

    Tu répètes l'opération jusqu'à ce que tu ai tes n nombres.

  3. #3
    Membre Expert
    Avatar de Sivrît
    Profil pro
    Inscrit en
    Février 2006
    Messages
    953
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2006
    Messages : 953
    Par défaut
    Sinon si l'on veut n valeurs parmis m valeurs possibles avec n<<m, et que donc un tableau à m éléments n'est pas possible (pas facile avec nos machines et leurs centaines de mo de ram ) :

    - On tire n valeurs en les insérant dans une liste triée pour avoir l'unicité (si une valeur y est déjà on retire)
    - Ensuite (à supposer qu'on ait besoin d'un ordre aléatoire), on applique la méthode de PRomu@ld

  4. #4
    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
    Par défaut
    Si la porbabilité de doublon est suffisament faible (un statisticien saurait nous dire combien ? ^^) :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     
     
    if (($nbquest>=0) and ($nbquest<=($maxquest-1))){//if1
     
    	while ($num.size < 10) {
    	    $randNum = rand(0,$maxquest);
     
    	    if (in_array($randNum,$num)) continue;
     
    	    $num[] = $randNum;
    	}
     
    }//endif 1
    J'emploie continue à titre d'exemple pour un code plus clair au cas où il y aurait plus d'opération à faire lors de l'ajout d'un élément encore non présent dans ton tableau.

  5. #5
    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 : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

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

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    On a une complexité en O(n²), c'est pas génial...

  6. #6
    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
    Par défaut
    Citation Envoyé par Miles
    On a une complexité en O(n²), c'est pas génial...

    Pour n=10, c'est pas bien grave. Et comme c'est un QCM, c'est peu probable que ça atteigne 100.000 questions aléatoires enfin, j'espère

  7. #7
    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
    Par défaut
    Citation Envoyé par Miles
    On a une complexité en O(n²), c'est pas génial...
    Heu... c'est naïf comme raisonnement.
    Si on prends 10 numéros parmis 100 on a :

    au 1-er passage : 0% chance que l'élément soit déjà dans le tableau.
    au 2-° passage : 1% chance que l'élément soit déjà dans le tableau.
    au 3-° passage : 2% chance que l'élément soit déjà dans le tableau.
    ...

    En 10 passages il y aura eu 45% chance qu'un l'élément ait déjà été dans le tableau.
    ~20% (si mes calculs sont bons) chance que deux éléments ait déjà été dans le tableau.
    Et ~9% (si mes calculs sont bons) chance que trois éléments ait déjà été dans le tableau.

    Au plus les nombres parmis desquelles on en prendra dix sont nombreux, au moins il y a de chance que des passages supplémentaires soient nécessaire.
    C'est l'algorithme le plus rapide dans ces cas là.

  8. #8
    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
    Par défaut
    Citation Envoyé par Sergejack
    Si la porbabilité de doublon est suffisament faible (un statisticien saurait nous dire combien ? ^^) :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     
     
    if (($nbquest>=0) and ($nbquest<=($maxquest-1))){//if1
     
    	while ($num.size < 10) {
    	    $randNum = rand(0,$maxquest);
     
    	    if (in_array($randNum,$num)) continue;
     
    	    $num[] = $randNum;
    	}
     
    }//endif 1
    J'emploie continue à titre d'exemple pour un code plus clair au cas où il y aurait plus d'opération à faire lors de l'ajout d'un élément encore non présent dans ton tableau.

    Si on veut faire un tableau de n nombres sans doublons.

    Si on en a déjà tiré p. Le probabilité d'en tirer un que l'on a déjà pris est donc de : p/n.

    Ce qui fait que pour 1000 nombres dans le tableau, si on en a déjà tiré 999, il faudra en temps moyen réaliser 1000 tours de boucle pour prendre celui qu'on a déjà pris...

    Le temps moyen est de : Sum(p, p=1 à n) = O(n²).

    Dans le pire ces cas, c'est un temps infini (si on tombe toujours sur un nombre déjà tiré). [edit : quasiment infini, la probabilité de tirait 100^100 fois le même nombre de suite est non nulle, pour être plus précis, c'est un algorithme probabiliste de type las vegas, sa terminaison étant presque sûre]

  9. #9
    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
    Par défaut
    Citation Envoyé par millie
    Si on veut faire un tableau de n nombres sans doublons.

    Si on en a déjà tiré p. Le probabilité d'en tirer un que l'on a déjà pris est donc de : p/n.

    Ce qui fait que pour 1000 nombres dans le tableau, si on en a déjà tiré 999, il faudra en temps moyen réaliser 1000 tours de boucle pour prendre celui qu'on a déjà pris...

    Le temps moyen est de : Sum(p, p=1 à n) = O(n²).

    Dans le pire ces cas, c'est un temps infini (si on tombe toujours sur un nombre déjà tiré). [edit : quasiment infini, la probabilité de tirait 100^100 fois le même nombre de suite est non nulle, pour être plus précis, c'est un algorithme probabiliste de type las vegas, sa terminaison étant presque sûre]
    Heureusement que j'ai établi l'hypothèse "la porbabilité de doublon est suffisament faible" sinon j'aurais eu droit à... Ben, non, j'ai quand même eu droit à ce post que tu a fait.
    J'apporte la meilleure réponse à la question "tirer 10 numéros parmis x" avec x grand (sans doute plus grand que 100) mais y a quand même des gens qui pour contester ma réponse réinvente la question.
    Ma solution ne marche pas non plus lorsque l'on veut tirer 1001 nombres parmis 1000.
    A entendeur de mauvaise foie, salut.

  10. #10
    Membre confirmé Avatar de harsh
    Inscrit en
    Février 2005
    Messages
    229
    Détails du profil
    Informations forums :
    Inscription : Février 2005
    Messages : 229
    Par défaut
    Citation Envoyé par PRomu@ld
    Un truc bète que j'avais utilisé dans un de mes premiers projets universitaires :

    Tu as un tableau de 1 à n.

    Tu fais un random entre 1 et n, tu obtiens i. Tu déplace ce i à la fin du tableau. (échange le dernier élément du tableau avec celui en i).

    Tu refais un random entre 1 et n-1.

    Tu répètes l'opération jusqu'à ce que tu ai tes n nombres.
    Pourquoi ne pas s'etre arreté sur cette idee? On peut pas trouver mieux comme complexité O(1) et une equiprobabilite assurée sur l'espace des solutions.

  11. #11
    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
    Par défaut
    Citation Envoyé par harsh
    Pourquoi ne pas s'etre arreté sur cette idee? On peut pas trouver mieux comme complexité O(1) et une equiprobabilite assurée sur l'espace des solutions.

    La complexité est en O(n) si l'opération random est en O(1). Mais c'est vrai que cette solution est extremement simple et fiable (niveau probabilité).

  12. #12
    Membre confirmé Avatar de harsh
    Inscrit en
    Février 2005
    Messages
    229
    Détails du profil
    Informations forums :
    Inscription : Février 2005
    Messages : 229
    Par défaut
    Si tu parles de la complexité de tiré n elements ok pour O(n), je me basais sur la complexité de tirage d'un element

  13. #13
    Membre confirmé 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
    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)

  14. #14
    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
    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 ?

  15. #15
    Membre émérite Avatar de 10_GOTO_10
    Profil pro
    Inscrit en
    Juillet 2004
    Messages
    890
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2004
    Messages : 890
    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.

  16. #16
    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, 18h12
  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, 09h42
  3. remplir un tableau sans doublons ...
    Par ryo-san dans le forum C
    Réponses: 22
    Dernier message: 10/11/2005, 12h43
  4. [Postgresql] insertion sans doublon
    Par Pwill dans le forum Décisions SGBD
    Réponses: 3
    Dernier message: 08/06/2005, 11h37
  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, 15h56

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