Discussion :

[megapacman]

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

[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.

[Sivrît]

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

[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.

[Matthieu Brucher]

On a une complexité en O(n²), c'est pas génial...

[millie]

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

[Sergejack]

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à.

[Matthieu Brucher]

n(n-1) comparaisons s'il n'y a pas de doublons.

[Sergejack]

n(n-1) comparaisons s'il n'y a pas de doublons.

(n * (n -1)) / 2;

si on veut 10 (n) éléments sur 100 (m) :

10 * 9 / 2 = 45 comparaisons
Alors que la construction d'un tableau avec les 100 (m) nombres serait de 100 assignations;

Cherche pas, j'ai raison

[harsh]

Euh... Si tout simplement tu prenais le premier element non utilisé qui suit dans ton espace en cas de doublon.

En te demerdant bien, tu dois pouvoir directement passer de ton doublon a la premiere valeur libre avec par exemple un tableau de la taille de ton espace qui contiendrait des references aux listes de valeurs deja prise consecutive... L'ajout d'un valeur dans un liste est O(1), l'acces a la derniere valeur : O(1).... Je dois zapper un truc... sinon le problemen est resolu, merci

[millie]

Euh... Si tout simplement tu prenais le premier element non utilisé qui suit dans ton espace en cas de doublon.

Ca doit faire un truc au pire de O(nlogn), non?

Si à une étape n, les éléments 1,2,3,4,5 ont déjà été choisi.

Il faudra une probabilité de 1/5 que l'élement 6 soit pris ensuite.
Alors qu'avec ta méthode, sa probabilité serait de 6/10 (puisqu'on a 6 si 1 2 3 4 5 ou 6 sont tirés).

[harsh]

hum... je reflechis

edit: c'est vrai

[harsh]

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.

[millie]

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]

[millie]

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é).

[harsh]

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

[Sergejack]

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.

[millie]

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.

La question étant de tirer 10 numero parmi 10. (

J'apporte la meilleure réponse à la question "tirer 10 numéros parmis x" avec x grand

et c'est toi qui me dit que je réinvente la question ????)
Le probabilité du doublon devient 9/10 pour le dernier élément à tirer (ce qui est assez important), donc pourquoi faire une hypothèse qui est fausse ?

La probabilité de tirer p doublons d'affilés pour le dernier tirage est de (9/10)^p qui est non nul pour tout p... Donc on peut pas dire que ce soit une bonne solution, même avec 10.

[Sergejack]

La question étant de tirer 10 numero parmi 10. ( et c'est toi qui me dit que je réinvente la question ????)

Absolument, et tu le confirmes.

[philben]

Bonjour,

Vous avez une réponse dans ce post en VBA :
http://www.developpez.net/forums/sho...d.php?t=172789

La méthode dont parle PRomu@ld est apparue comme l'une des plus rapides quelque soit le nombre de nombres aléatoires.

Amicalement,

Philippe