[Résolu] [Calc] Erreur 522 avec COMBINAISON : pourquoi ?

[alhazred]

Bonjour,

D'accord, je préfère en général résoudre moi-même mes problèmes (et éventuellement faire profiter le forum des solutions), mais là je sèche

Un sujet récent m'a suggéré de constituer une liste en ordre aléatoire des nombres entiers de 1 à 70. Pas de problème, l'appel Combinaison(70,70) renvoie ces nombres sous forme de tableau (voir ce sujet)

Pour afficher ce tableau dans une feuille, j'utilise la formule matricielle

Code : Tout sélectionner

{=COMBINAISON(70;70)}

Toujours pas de problème, les nombres s'affichent correctement.

Là où ça coince, c'est qu'en faisant plusieurs fois ctrl+maj+F9 pour refaire le calcul, j'obtiens parfois (de l'ordre de 1 fois sur 10) des cellules avec "Err :522"

J'ai bien sûr pensé d'abord à une erreur dans la fonction, mais n'ai rien trouvé (ce qui ne veut certes pas dire qu'il n'y en ait pas).
J'ai l'impression que ce comportement ne se produit qu'avec un rythme rapide des recalculs (déclenchement de la macro avant que l'affichage n'ait été rafraichi ? ou redéclenchement avant que la macro ne soit terminée ? mais alors pourquoi seulement "quelquefois" ?)

Et quel rapport avec le numéro 522 ? (D'accord, ça fait beaucoup de questions pour un seul message )

[squenson]

J'ai fait quelques tests et il me semble que cela provient de la durée d'exécution de la fonction. Si j'ajoute un compteur de boucles au milieu du code, la fonction effectue parfois 12 000 à 14 000 passages, ce qui n'est pas négligeable même avec les avec les processeurs.

L'algorithme est le suivant (je schématise) :
1. Je prends un boule dans le sac
2. Je note son numéro
3. S'il est déjà sorti, je remets ma boule dans le sac et je reprends au 1, sinon je l'ajoute à ma liste et je remets quand même la boule dans le sac
4. Si j'ai une liste de n numéros, comme il sont par construction tous différents, j'ai ma réponse

Loesque la liste est presque complète, il faut faire à chaque fois plusieurs dizaines d'essais pour arriver à prendre une boule avec un numéro pas encore sorti, d'où le grand nombre de boucles.

Il serait beaucoup plus rapide de procéder ainsi:
1. Je dispose mes boules de 1 à n dans une liste
2. Je prends la première, puis une autre au hasard, et je les échange (for i = 1 to n --- j = rnd(70) --- res(i) <-> res(j))
3. Je reprends à 2, mais cette fois-ci avec la deuxème, puis la troisième, etc. jusqu'à la dernière
Résultat : 70 swaps maximum, toutes les boules ont une chance de changer de place au moins une fois

Avec cette approche, pas d'erreur 522 même avec des ctrl-maj-F9 très rapide !

[alhazred]

Bonsoir, squenson,

Bonne analyse de l'algorithme de ma fonction Combinaison.

Pour ta deuxième méthode, je la trouve très séduisante... à condition qu'elle donne tous les ordres possibles avec la même probabilité ; ce que je suis, à cette heure-ci, incapable de confirmer ou d'infirmer

Ajout : Désolé, squenson, ça ne marche pas (à moins que je n'aie pas bien saisi la méthode) Prenons le cas de 3 numéros seulement (6 ordres possibles). Ce qui déterminera l'ordre final sera une suite quelconque de trois nombres au hasard entre 1 et 3 Il y a 27 de ces suites, toutes équiprobables ; alors comment les 6 résultats pourraient-ils être équiprobables, puisque 27 n'est pas divisible par 6 ? Plus généralement, pour n numéros, le nombre d'ordres possibles est n! (factorielle n = 1*2*3....*n) et celui des suites de n nombres aléatoires entre 1 et n est n^n. On peut assez facilement démontrer que n^n n'est jamais divisible par n!, sauf pour n=1 ou n=2

[bm92]

Bonsoir,
Je n'ai pas réussi à éliminer l'erreur 522 (référence circulaire), mais elle ne se déclenche plus que sur des répétitions automatiques.
L'algorithme troque le codage contre de la mémoire pour aller plus vite. Mais n'oublions pas que RND() est assez long lui aussi, et parfois on doit boucler pas mal pour éliminer les tirages inutilisables.

Code : Tout sélectionner

Option Explicit

'Renvoie un tableau aléatoire sans répétitions de <n> nombres entiers de 1 à <max>
'Le tableau commence à l'indice 1 et bien sûr n% ne peut être supérieur à max%
Function Combinaison(max As Integer, n As Integer)
	Dim res(1 To n) As Double, dejaFait(1 to max+1) As Boolean
	
	Dim i As Integer, v As Integer
	dejaFait(max+1) = True ' valeur interdite, bogue de Rnd()
	i = 1
	Do 
		v = 1 + Int(Rnd*max)
		if not dejaFait(v)  then
		  res(i) = v
		  dejaFait(v) = True
		  i = i+1
		end if
	Loop until i > n

	Combinaison=res
End Function

[alhazred]

Bonsoir, Bernard,

Jolie amélioration de mon codage ça élimine une des boucles (celle de la vérification de validité)

Ajout : Pour préciser, j'ai chronométré les deux macros (les résultats sont en "ticks" et sont des moyennes sur 6 essais) Combinaison(1000,1000) Bernard : 120 Moi : 14400 Combinaison(2000,2000) Bernard : 230 Moi : 53500 Bernard vainqueur par KO Il semble que la version de Bernard donne des temps proportionnels à n (ce que laissait supposer la suppression de boucle), alors que c'est n^2 pour la mienne !

Mais toujours pas de réponse à la question de départ : d'où vient l'erreur d'affichage, alors que la macro est impec ?

Bof, vais quand même mettre Résolu. ou peut-être Bogue un peu plus tard.

[squenson]

Vous avez raison, ma méthode est biaisée, ce qui est assez étrange car elle semblait bien symétrique. Mais comme souvent en mathématique, il faut se méfier de ses intuitions ! Voici un algorithme (en anglais) qui s'exécute en O(n).

[bm92]

Bonjour,
Je reviens sur ce sujet fermé en espérant le boucler définitivement.
Squenson a bien décrit le problème, mais son esquisse de solution n'est pas bonne.

Ma nouvelle méthode est très proche :

1. Je détermine un tableau des valeurs possibles
2. Je choisis au hasard un index dans le tableau.
3. Je note la valeur pour cet index et je l'enleve de la liste. Plutôt que de retasser le tableau, je copie à l'index obtenu la valeur qui se trouve à l'index maximal.
4. Je décrémente l'index maximal
5. Je recommence au pas 2 en choisissant au hasard dans le tableau plus petit.

Ce qui nous donne, avec quelques améliorations de de détail :

Code : Tout sélectionner

'Renvoie un tableau aléatoire sans répétitions de <nbrTirages> entiers de 1 à <GammeValeurs>
'Le tableau commence à l'indice 1 et bien sûr nbrTirages ne peut être supérieur à GammeValeurs
Function Combinaison(GammeValeurs As Integer, nbrTirages As Integer)
	Dim res(1 To nbrTirages) As Double
	Dim valeurs(1 to GammeValeurs) As Integer
	Dim i As Long, v As Long, valMax As Integer
	' garde-fou
	if (nbrTirages > GammeValeurs) or (nbrTirages < 0) or (GammeValeurs < 0)  then err = 14
 	for i = 1 to GammeValeurs
	  valeurs(i) = i
	next
	valMax = GammeValeurs
	for i = 1 to nbrTirages
	  ' à chaque tour on puise dans la liste des valeurs restantes
	  do
	    v = 1 +Int(Rnd*valMax)
	  loop until v <= valMax ' contournement de bogue RND()
	  res(i) = valeurs(v)
	  valeurs(v) = valeurs(valMax)
	  valMax = valMax -1
	next
	Combinaison=res
End Function

Le nombre d'appels à RND est égal au nombre de tirages (sauf cas très rare de bogue de RND).
Pour Combinaison(70,70) la durée est toujours <= 16 ticks (16ms). Cependant, l'erreur 522 arrive encore, sur une répétition automatique. Voyons pourquoi.

Voici une version bidon de la fonction Combinaison, qui dure 1 seconde:

Code : Tout sélectionner

Function Combinaison(GammeValeurs As Integer, nbrTirages As Integer)
	Dim res(1 To nbrTirages) As Double
	wait 1000
	Combinaison=res
End Function

Bien sûr avec un seul Ctrl-Maj-F9 le résultat sera tout à zéro.
Mais si on répète Ctrl-Maj-F9 avant une seconde, on obtient : err 522.
Ce qui veut dire que si l'appel de la fonction est renouvelé avant la fin d'exécution, Basic suppose une erreur de référence circulaire. Je pense que c'est une protection mise en place par Calc.

[alhazred]

Bonjour à tous,

Là, le sujet est effectivement clos, merci, Bernard (également pour ce que j'ai appris en décortiquant ton code ). Tu confirmes l'une de mes hypothèses "redéclenchement avant que la macro ne soit terminée".

Merci aussi, squenson, pour ton lien.