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

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

Messagepar alhazred » 14 Sep 2011 23:09

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   AgrandirRéduire
'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é 619 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   AgrandirRéduire
    '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 édition par alhazred le 29 Oct 2013 23:10, édité 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 !
Avatar de l’utilisateur
alhazred
ManitOOu
ManitOOu
 
Message(s) : 3028
Inscrit le : 01 Mai 2011 00:08
Localisation : Casablanca (Maroc)

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

Messagepar squenson » 15 Sep 2011 21:06

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
squenson
PassiOOnné
PassiOOnné
 
Message(s) : 564
Inscrit le : 21 Avr 2007 18:27
Localisation : Lausanne, Suisse

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

Messagepar alhazred » 17 Sep 2011 16:54

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 !
Avatar de l’utilisateur
alhazred
ManitOOu
ManitOOu
 
Message(s) : 3028
Inscrit le : 01 Mai 2011 00:08
Localisation : Casablanca (Maroc)

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

Messagepar squenson » 17 Sep 2011 17:40

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   AgrandirRéduire
j = max + 1
While j > max
    j = int(rnd*max) + 1
Wend
LibreOffice 4.2.3.3. sous Ubuntu 14.04
squenson
PassiOOnné
PassiOOnné
 
Message(s) : 564
Inscrit le : 21 Avr 2007 18:27
Localisation : Lausanne, Suisse

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

Messagepar alhazred » 17 Sep 2011 23:34

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   AgrandirRéduire
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   AgrandirRéduire
    '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 !
Avatar de l’utilisateur
alhazred
ManitOOu
ManitOOu
 
Message(s) : 3028
Inscrit le : 01 Mai 2011 00:08
Localisation : Casablanca (Maroc)


Retour vers Suprême de code

Qui est en ligne ?

Utilisateur(s) parcourant ce forum : Aucun utilisateur inscrit et 2 invité(s)