[Basic] Tirage au hasard sans répétition (combinaison)

Vos meilleures macros et portions de code sont publiées dans cette section.
Aucun support sur une question de programmation ici !

Modérateur : Vilains modOOs

Règles du forum
Aucune question dans cette section !
Celle-ci rassemble les meilleures macros et portions de code. Vous pouvez en revanche commenter ou argumenter le code exposé. Vous pouvez même remercier l'auteur (cela fait toujours plaisir) en indiquant par exemple dans quel cadre ou contexte vous en avez eu l'utilité.
Si vous avez à poster quelque chose, faites-le depuis la section Macros et API et demandez à un modérateur de l'y déplacer.
Avatar de l’utilisateur
alhazred
ManitOOu
ManitOOu
Messages : 3028
Inscription : 01 mai 2011 01:08
Localisation : Casablanca (Maroc)

[Basic] Tirage au hasard sans répétition (combinaison)

Message par alhazred »

Bonjour,

De nombreux fils cherchent une solution permettant d'extraire au hasard des éléments d'une liste en évitant les doublons. Pour les matheux, il s'agit de former une partie (ou combinaison) aléatoire d'un ensemble.

La plupart des solutions proposées se font dans Calc, avec des tas de cases intermédiaires :fou: ... bref, pas pour moi

Le dernier fil auquel j'ai participé m'a conduit à écrire une macro plus générale que celle proposée par Bidouille dans ce fil; la voici:

Code : Tout sélectionner

'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%, n%)
	Dim res(1 To n)
	
	Dim i%,j%,v%
	For i=1 To n
		v=1+Int(Rnd*max)
		If v>max Then 'Rnd est boguée et pourrait donner 1
			i=i-1 'donc on recommence: première boucle
		Else 'on vérifie que la valeur n'existe pas déjà
			For j=1 To i-1
				If v=res(j) Then Exit For
			Next j
			If j<i Then 'il y a répétition donc on recommence
				i=i-1 'deuxième boucle
			Else 'tout va bien
				res(i)=v
			End If
		End If
	Next i
	
	Combinaison=res
End Function
Par exemple Combinaison(5,3) pourrait renvoyer {3,1,4} alors que Combinaison(5,5) mènerait peut-être à {4,5,2,1,3}

Cette macro peut être utilisée directement, par exemple pour former votre prochain Loto gagnant, ou en liaison avec un tableau; dans ce dernier cas, remarquez que les tableaux commencent en général à l'indice 0, alors que les numéros retournés par la fonction sont supérieurs ou égaux à 1.

Par exemple, si le tableau associé contient les noms des cartes à jouer, on pourra simuler une distribution de bridge, ou de tout autre jeu; s'il contient les noms des participants d'une loterie, on pourra obtenir la liste des gagnants.

En prime, un exemple d'utilisation, je vous gâte :P :
Combinaisons-2.odt
(19.11 Kio) Téléchargé 922 fois
 Ajout : 30/10/13 Nouvelle version, suite à un problème sur AOO, signalé par rosaguy ; de plus, la donne de bridge s'affichait incorrectement :oops: 
Remarque: la boucle qui permet d'éviter une répétition pourrait être supprimée (la loi de l'emm... de Murphy généralisée prévoit une probabilité non nulle pour une boucle sans fin, ou tout au moins très longue...) au prix d'une complication de la fonction. Si le cœur vous en dit...
Quant à celle qui évite la bogue, on peut aussi la remplacer par une diminution infinitésimale de la valeur renvoyée par Rnd; dans ce cas, la probabilité d'apparition du dernier nombre est en toute rigueur légèrement augmentée, mais cela ne serait sensible que pour de très grandes valeurs de max%.
 Ajout : À strictement parler, le résultat de Combinaison est plutôt un "arrangement", c'est-à-dire que les nombres sont renvoyés dans un certain ordre, par exemple, on pourra obtenir {3,1,4} , puis {4,3,1}. Pour un joueur de tiercé, ces deux résultats sont différents (rapports dans l'ordre et sans ordre); ils ne le sont pas s'ils représentent le tirage des trois premiers numéros du Loto (combinaison au sens propre). 
 Ajout : 24/09/2013
Une version bien plus rapide m'a été aimablement communiquée par Bernard Marcelly (bm92), avec les mêmes conventions d'appel :

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
    'Macro de Bernard Marcelly
    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
 
Dernière modification par alhazred le 29 oct. 2013 23:10, modifié 6 fois.
À bientôt

LibO 4.1.5.3 et AOO 4.0.1 sous Windows 7, MRI et SDK pour les macros.

Et la sauvegarde incrémentée, c'est sympa !
squenson
PassiOOnné
PassiOOnné
Messages : 564
Inscription : 21 avr. 2007 19:27
Localisation : Lausanne, Suisse

Re: [Writer] Tirage au hasard sans répétition (combinaison)

Message par squenson »

Afin d'éviter une boucle très longue, il vaut mieux procéder de la façon suivante :

Créer un tableau avec les valeurs 1 à max
Pour i de 1 à max
j = int(rnd*max) + 1
if j > max then j = max
Échanger les éléments i et j
Next i
Renvoyer les n premiers éléments du tableau
LibreOffice 4.2.3.3. sous Ubuntu 14.04
Avatar de l’utilisateur
alhazred
ManitOOu
ManitOOu
Messages : 3028
Inscription : 01 mai 2011 01:08
Localisation : Casablanca (Maroc)

Re: [Writer] Tirage au hasard sans répétition (combinaison)

Message par alhazred »

Bonjour,

Désolé, Squenson, ça ne marche pas et voici pourquoi:

On veut tirer 1 numéro de 1 à 2: on forme le tableau (1 ,2) qui sera modifié selon les résultats de rnd()
Disons que rnd() donne 1 dans 2% des cas, on aura alors comme probabilités de int(rnd()*2)+1 :
Pour 1 49,00%
Pour 2 49,00%
Pour 3 2,00%

Maintenant, pour 2 tirages, on a les possibilités suivantes (chaque probabilité étant le produit de celles des deux tirages) :
Probabilité
1;1 24,01% 2;1 24,01% 3;1 0,98%
1;2 24,01% 2;2 24,01% 3;2 0,98%
1;3 0,98% 2;3 0,98% 3;3 0,04%

(les tabulations ne fonctionnent malheureusement pas)

Le résultat 3;3 interviendra, quelle que soit la méthode, dans la probabilité d'obtenir 1 ou 2, et introduira donc un déséquilibre.

Cela me laisse penser (sans que j'en aie de démonstration) qu'il est inévitable soit de négliger ce déséquilibre, soit d'éliminer par une boucle les résultats indésirables.
À bientôt

LibO 4.1.5.3 et AOO 4.0.1 sous Windows 7, MRI et SDK pour les macros.

Et la sauvegarde incrémentée, c'est sympa !
squenson
PassiOOnné
PassiOOnné
Messages : 564
Inscription : 21 avr. 2007 19:27
Localisation : Lausanne, Suisse

Re: [Writer] Tirage au hasard sans répétition (combinaison)

Message par squenson »

Je n'ai jamais rencontré le cas rnd = 1 (je viens de faire 10 millions de tirage sans le rencontrer une seule fois), donc il est minime ! De plus, je le traite par la ligne :
if j > max then j = max
Ceci induit une erreur de moins de 1e-7 sur le dernier élément. Néanmoins il serait plus judicieux de faire:

Code : Tout sélectionner

j = max + 1
While j > max
    j = int(rnd*max) + 1
Wend
LibreOffice 4.2.3.3. sous Ubuntu 14.04
Avatar de l’utilisateur
alhazred
ManitOOu
ManitOOu
Messages : 3028
Inscription : 01 mai 2011 01:08
Localisation : Casablanca (Maroc)

Re: [Writer] Tirage au hasard sans répétition (combinaison)

Message par alhazred »

Bonsoir,

Tu as tout à fait raison, Squenson, quand tu dis que le risque est minime, sinon ça ne serait pas une bogue mais un bang, d'où certaines de mes remarques précédentes.

Quant à ton dernier code, il ne fait rien de mieux que

Code : Tout sélectionner

j = Int(Rnd*max) + 1
If j>max Then j=max
qui, justement, évite la première boucle (mais bien sûr pas la deuxième) et donne (ton erreur de variable est pardonnée):

Code : Tout sélectionner

    '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%, n%)
       Dim res(1 To n)
       
       Dim i%,j%,v%
       For i=1 To n
          v=1+Int(Rnd*max)
          If v>max Then v=max 'pas strictement correct: le résultat Rnd=1 est attribué à max
          'on vérifie que la valeur n'existe pas déjà
          For j=1 To i-1
                If v=res(j) Then Exit For
          Next j
          If j<i Then 'il y a répétition donc on recommence
                i=i-1
          Else 'tout va bien
                res(i)=v
          End If
       Next i
       
       Combinaison=res
    End Function
Je préfère quand même conserver la boucle. En termes mathématiques, une équiprobabilité est possible dans l'ensemble des nombres réels* sur l'intervalle [0;1[ (1 exclus) mais pas sur [0;1] (1 inclus).

*Plus exactement pour des intervalles de même forme [x;y[ et de même longueur aussi petite que l'on veut.
À bientôt

LibO 4.1.5.3 et AOO 4.0.1 sous Windows 7, MRI et SDK pour les macros.

Et la sauvegarde incrémentée, c'est sympa !
Répondre