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

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

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

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

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

[O( N )]

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)

[Sergejack]

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 ?

[10_GOTO_10]

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 ?

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.

[Invité]

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()

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