avec 200 ? vous avez conservé le randomSeed() dans la boucle while (celui de la ligne 17 dans le code que j'ai copié dans ma réponse) ?
Sinon je ne dis pas que ça ne marche pas dans votre cas avec N tout petit, juste que ça va prendre un certain temps (comme le fût du canon) qui est indéterminée et que plus N est grand, plus c'est difficile et ça va prendre du temps voire ne jamais marcher.
Explication:
En gros au début vous avez les N cases de votre tableau rndTest toutes à false. (donc 0 à true)
Imaginons que N = 1000
vous tirez un nombre au hasard, vous êtes sûr de tomber sur une case 'false' puisqu'il n'y en a pas de 'true'
Vous avez donc maintenant 999 cases à 'false' et 1 à 'true'
Vous tirez un nombre au hasard, si vous n'avez pas de bol vous pouvez tomber sur la case qui est déjà 'true' et vous devez faire un nouveau tirage. la probabilité que vous tombiez sur une case 'true' c'est 1 / 1000 puisque vous n'avez qu'une case 'true' sur les 1000 -> 0.1% de chances de tomber sur un 'true', vous allez donc très vite trouver une case 'false'
Une fois cette seconde case cochée, Vous avez donc maintenant 998 cases à 'false' et 2 à 'true'
même chose, mais ce coup ci vous avez (2 / 1000) chances de tomber sur une case déjà à 'true' -> 0.2% de chances de tomber sur un 'true'
ainsi de suite.
Quand vous aurez cochées déjà 500 cases vous aurez 500 / 1000 = 50% de chances de tomber sur case occupée --> il vous faudra quelques tirages sans doute pour trouver une case 'false'
quand vous aurez 900 cases cochées, vous aurez 900 / 1000 = 90% de chances de tomber sur case occupée --> il vous faudra de nombreux tirages sans doute pour trouver une case 'false'
quand vous aurez 990 cases cochées, vous aurez 990 / 1000 = 99% de chances de tomber sur case occupée --> il vous faudra de nombreux tirages sans doute pour trouver une case 'false'
quand vous arrivez à la dernière, vous aurez 999 cases cochées, vous aurez 999 / 1000 => juste 0,1% de chances de tomber sur la bonne case encore libre --> il vous faudra de très nombreux tirages sans doute pour trouver cette case 'false'
--> en gros, plus vous cochez les cases, plus c'est difficile de tomber par hasard sur une case libre.
Ce que vous pouvez faire c'est modifier votre code de test pour compter le nombre d'essais nécessaires pour finir le mélange
voilà un bout de code à testerje reprends votre algo, j'ai viré les 2 tableaux car pas la peine d'occuper trop de mémoire et j'ai mis le tableau vrai/faux en global avec une taille max
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62 size_t filsNombre = 100; boolean rndTest[1000]; // Pour tester sur la valeur est déjà tirée unsigned long entreesPinMelange() { size_t rndNumber; size_t rndIndex = 0; unsigned long nombreDessais = 0; for (size_t r = 0; r < filsNombre; r++) // Tout le tableau de test à false { rndTest[r] = false; } while (rndIndex < filsNombre) { // randomSeed(analogRead(0)); // ATTENTION SI ON FAIT CA ON AUGMENTE LE RISQUE DE TOURNER SANS FIN rndNumber = random(0, filsNombre); nombreDessais++; if ((nombreDessais % 500UL) == 0) Serial.write('.'); // on met un point tous les 500 tests if (rndTest[rndNumber] == false) // Si nombre hasard pas déjà tiré { // entreesPin[rndIndex] = entreesPinBase[rndNumber]; on ne le fait pas pour économiser la mémoire rndTest[rndNumber] = true; // Enregistrer le numéro comme tiré rndIndex ++; } } // Serial.print("il a fallu "); // Serial.print(nombreDessais); // Serial.println(" essais "); return nombreDessais; } void setup() { Serial.begin(115200); randomSeed(analogRead(A0)); } void loop() { unsigned long minEssai = 0xFFFFFFFF, maxEssai = 0; // on mélange 20 fois pour voir le min et max du nombre d'essais for (int i = 0; i < 20; i++) { unsigned long n = entreesPinMelange(); if (n > maxEssai) maxEssai = n; if (n < minEssai) minEssai = n; } Serial.print("\nil a fallu entre "); Serial.print(minEssai); Serial.print(" et "); Serial.print(maxEssai); Serial.print(" essais pour N="); Serial.println(filsNombre); filsNombre += 100; if (filsNombre > 1000) while (true); // on ne va pas plus loin le tableau déborderai }
j'ai aussi viré la régénération des nombres aléatoire en cours de boucle (le randomSeed) sinon ça ne converge pas car pour une seed donnée vous êtes à peu près sur de tomber sur votre chiffre dans un délai raisonnable mais si vous changez la seed à chaque fois, on augmente le risque.
voilà ce que ça me donne:
................
il a fallu entre 360 et 1115 essais pour N=100
..........................................
il a fallu entre 924 et 2251 essais pour N=200
...................................................................
il a fallu entre 1337 et 2469 essais pour N=300
................................................................................................
il a fallu entre 2145 et 4259 essais pour N=400
..................................................................................................................................
il a fallu entre 2286 et 6533 essais pour N=500
....................................................................................................................................................
il a fallu entre 3242 et 4938 essais pour N=600
........................................................................................................................................................................................................
il a fallu entre 3647 et 7281 essais pour N=700
.................................................................................................................................................................................................................................
il a fallu entre 4612 et 9303 essais pour N=800
.................................................................................................................................................................................................................................................................
il a fallu entre 4666 et 10728 essais pour N=900
...................................................................................................................................................................................................................................................................................................
il a fallu entre 5670 et 9908 essais pour N=1000
si on met le randomSeed() et que j'avance de 5 en 5
il a fallu entre 5 et 24 essais pour N=5
il a fallu entre 11 et 40 essais pour N=10
il a fallu entre 28 et 82 essais pour N=15
il a fallu entre 38 et 84 essais pour N=20
..................................................
il a fallu entre 127 et 5851 essais pour N=25
... // .....
il a fallu entre 1043 et 115608 essais pour N=30
--> et ça bloque (enfin ça prend tellement longtemps que j'ai arrêté d'attendre)
Dans le cas de l'algo que j'ai posté on fait (N-1) opérations à tous les coups pour mélanger le tableau de N éléments. donc même avec 1000 éléments dans le tableau on ne fera que 999 tirages aléatoires et échanges.
Partager