x nbr alea non repeterRésolu

Question

bonjour,
voila encore une quizz lol bah c'est pas compliquer mais bon je trouve plus le code j'aimerais generer x nombres aleatoire dans un listbox (un chiffre par ligne) et je veux pas deux fois le meme nombre par exemple je click sur generer et ses regler sur tirer 50 chiffre aleatoires bah premiere ligne du listbox un chiffre deuxieme ligne deuxieme chiffre etc etc ... mais je ne veux aucun doublon donc avoir tt les chiffre jusque 50 (en commencant par 1) mais dans le desordre :-)
je sais pas si c'est clair mais sa dois etre facile a faire :p

Merci d'avance
Diablaman

Dolphin Boy · Accepted Answer

Salut, je te propose ce code :

Private Sub Command1_Click()
Dim i As Integer, j As Integer
Dim t As Boolean
Dim x As Integer
  Randomize Time 'init pour le calcul aléatoire
  For i = 1 To 50
    t = False
    x = Int((50 * Rnd) + 1)
    For j = 0 To List1.ListCount - 1
      If List1.List(j) = x Then
        t = True
        i = i - 1
        Exit For
      End If
    Next
    If t = False Then
      List1.AddItem x
    End If
  Next
End Sub

cs_DARKSIDIOUS · Answer

Ou plus optimisé : créer tout d'abord ton listbox dans l'ordre, et appliquer désordre dessus à 50 reprises : déplacer intervertir 2 élements tirés aléatoirement à la position que tu veux.

Ca évite surtout la boucle for j qui prend un peu de temps pour rien arrivé à la fin du tableau (pour tirer les derniers nombres aléatoires).

diablamanshadow · Answer

merci a vous deux mais finalement j'ai adopter la source de dolphin qui est rapide et fonctionne nikel ;-) mais il faut pas oublier de mettre list1.clear au debut de ton code juste sous le _click pour pas que sa bug si tu veux faire des tirrage en appuyant sur un bouton sinon il tombe dans une boucle infinnie et plante le prog ;-)

cs_DARKSIDIOUS · Answer

Pourtant, ma solution est plus élégante et plus courte :

Dim i As Integer
Dim j As Integer
Dim x As Integer
Dim y As Integer
Dim t As String
    List1.Clear
    Randomize Timer
    'remplissage de la liste
    For i = 1 To 50
        List1.AddItem (i)
    Next i
    For i = 1 To 50
        'récup des 2 index aléatoires
        x = Int((50 * Rnd))
        y = Int((50 * Rnd))
        'swap de l'élément aléatoire
        t = List1.List(x)
        List1.List(x) = List1.List(y)
        List1.List(y) = t
    Next i

Dolphin Boy · Answer

diablamanshadow > exact pour le clear.

DARKSIDIOUS > ta solution n'est pas à écarter. Elle est probablement plus rapide (à vérifier) mais tu utilises la permutation aléatoire et donc elle se rapproche beaucoup moins de la mienne d'un vrai tirage aléatoire.

Je m'explique, par exemple le loto :

Que les boules soit rangées ou non dans l'ordre de 1 à 49 (elles sont plutôt dans un bordel complet), on n'effectue pas de permutations entre les 49 boules pour ne retenir que les 6 premières.
On prend la 1ère qui se présente, puis la 2ème parmi les restantes et ainsi de suite.

En fait, en prog, si on veut imiter un vrai tirage, il faudrait :
- avoir un tableau de numéros (boules ?) rangé ou non. 
- tirer au hasard une position dans le tableau.
- enregistrer le numéro correspondant
- reconstruire le tableau sans le numéro tiré
- tirer au hasard une position dans le nouveau tableau
- enregistrer le numéro correspondant
- etc... jusqu'à la limite qu'on se donne (au max le nombre de numéros du tableau d'origine)

Pas impossible à faire mais sans doute encore plus long.

cs_DARKSIDIOUS · Answer

Dolphin Boy : oui je suis d'accord, mais le résultat est le même, en bien plus efficace car je ne fais que  permutations et 100 tirages aléatoires (on pourrait d'ailleur se limiter qu'à 50). Cela évite surtout ta deuxième boucle qui doit parcourir à chaque tirage aléatoire les éléments de la liste !

Si tu veux comparer, essaye ceci (ton code pour 500 éléments) :
Private Declare Function GetTickCount Lib "kernel32" () As Long

Private Sub Form_Click()

Dim i As Integer, j As Integer
Dim t As Boolean
Dim x As Integer

Dim time As Long

    time = GetTickCount
  Randomize time 'init pour le calcul aléatoire
  For i = 1 To 500
    t = False
    x = Int((500 * Rnd) + 1)
    For j = 0 To List1.ListCount - 1
      If List1.List(j) = x Then
        t = True
        i = i - 1
        Exit For
      End If
    Next
    If t = False Then
      List1.AddItem x
    End If
  Next
  MsgBox GetTickCount - time

End Sub

Et le mien (pour 500 éléments) :
Private Declare Function GetTickCount Lib "kernel32" () As Long

Private Sub Form_Click()

Dim i As Integer
Dim j As Integer
Dim x As Integer
Dim y As Integer
Dim t As String
Dim time As Long

    time = GetTickCount

    Randomize Timer
    'remplissage de la liste
    For i = 1 To 500
        List1.AddItem (i)
    Next i
    For i = 1 To 500
       'récup des 2 index aléatoires
        x = Int((500 * Rnd))
        y = Int((500 * Rnd))
        'swap de l'élément aléatoire
        t = List1.List(x)
        List1.List(x) = List1.List(y)
        List1.List(y) = t
    Next i
  MsgBox GetTickCount - time

End Sub

Résultats ? Mon algo écrase litéralement le tien :
3314 ms pour le tien 
218 ms pour le mien 
Soit un rapport de 15 x plus rapide.

L'astuce consiste en fait à ne pas balayer la listbox éléments par éléments, car c'est ce qui prend le plus de temps !

Je t'accorde que pour 50 éléments, le temps gagné est négligeable dans le meilleur des cas, mais il le devient déjà moins si tu n'as pas de chance (si les tirage aléatoires te donnent souvent des numéros déjà tirés, alors ton algo rame à mort !).

Voilà, c'est ma petite intervention niveau optimisation : ton algo est bon, il correspond à ce qu'il se passe dans la réalité, mais le mien fait la même chose en plus rapide. 

C'est comme si tu comparer les méthodes de tri : la méthode qu'on utilise dans la vie n'est pas la plus rapide à faire éxécuter par un ordinateur ;)

cs_DARKSIDIOUS · Answer

A oui, sinon pour revenir sur ton idée de reconstruction de tableau, elle est certainement plus rapide que ton algo car justement, tu ne teste pas les éléments déjà tirés, tu les élimine => pas besoin de boucle de test, la construction du tableau est bien plus rapide que le parcourt d'un listbox !

Gobillot · Answer

Salut,


la méthode DARKSISIOUS:

   - très valable

   - sauf qu'il faut faut prendre i comme premier index et le mélanger avec un deuxième index aléatoire
      pour éviter qu'un numéro ne soit pas permuté


dernière méthode Dolphin Boy:

   - très valable et toute aussi courte

   - pas besoin de reconstruire le Tableau, il suffit de permuter le numéro tiré en fin du tableau position (i)

   - le résultat se trouve dans ce même tableau  (ici la ListBox)


    Dim i As Integer

    Dim x As Integer

    Dim t As String

    

    List1.Clear

    Randomize Timer
    'remplissage de la liste
    For i = 1 To 50

        List1.AddItem i

        Next i

    For i = 50 To 1 Step -1
       'tirage aléatoire
        x = Int(i * Rnd)
       'swap de l'élément aléatoire
        t = List1.List(x)

        List1.List(x) = List1.List(i - 1)   '(i -1) parce que l'index commence à zéro

        List1.List(i - 1) = t

        Next i

Daniel

Dolphin Boy · Answer

DARKSIDIOUS > je m'incline question rapidité mais pas question véracité et puis tes permutations peuvent aussi être les mêmes presqu'aussi souvent que mes tirages.
D'autre part,  je suis OK avec le fait que la ou les méthodes réelles ne sont pas les plus rapides à faire exécuter par un ordi (voir les prog d'echecs par rapport à un bon joueur humain, mais c'est hors sujet). 
Je me demande d'ailleurs parfois ce qu'il vaut mieux, la rapidité d'exécution par l'ordi avec un résultat contestable ou une exécution plus lente mais avec des résultats plus proches de la réalité. Tout dépend de ce qu'on veut obtenir en sortie. 
Tiens, ça me rappelle l'éternel débat (en musique) entre le MP3 et la véritable numérisation de l'analogique. 
Bon, j'arrête là mon délire, c'est vrai que parcourir une listbox c'est très lent, pour optimiser, on peut passer déjà par un tableau de résultats d'abord et remplir la listbox en dernier.
Ensuite, mon idée de reconstruction du tableau, c'était juste une idée mais, si j'ai le temps ce week end, je vais essayer de la mettre en pratique. A moins que quelqu'un me devance.

Bonne prog à tous

Gobillot · Answer

c'est fait,


temps = 156 ms (en compilé pas beaucoup mieux)

c'est la ListBox qui prend tout le temps

avec un Tableau ce serait plus rapide.

Daniel

Dolphin Boy · Answer

Toutes mes excuses Daniel, pas vu ton intervention mais tu me donnes une bonne idée.

diablamanshadow · Answer

perso je ne joue pas avec des 500 elements mais je jouerais avec a tt casser 60 elements donc je prefere une methode plus "humaine" comme dolphin ;-)
donc voila voila sinon je test un peu tt (dites comment vous voyez le temp d'execution d'une partie de code :? )

Gobillot · Answer

pour avoir le temps utilise l'API GetTickCount comme a fait DARLSIDIOUS

par différence on a le temps en millisecondes

temps du tirage=            0 ms

temps après controle = 31 ms


Option Explicit


Private Declare Function GetTickCount Lib "kernel32" () As Long


Private Sub Command1_Click()

    Dim i    As Integer

    Dim x    As Integer

    Dim t    As String

    Dim Ta() As Long

    Dim Tp   As Long

    

    Tp = GetTickCount

    Randomize Timer

    'remplissage de la liste

    ReDim Ta(500)

    For i = 1 To 500

        Ta(i) = i

        Next i

    For i = 500 To 1 Step -1
       'tirage aléatoire
        x = Int(i * Rnd) + 1
       'swap de l'élément aléatoire
        t = Ta(x)

        Ta(x) = Ta(i)

        Ta(i) = t

        Next i

    MsgBox GetTickCount - Tp

    
  'controle dans une ListBox triée
    List1.Clear

    For i = 1 To 500

        x = Ta(i)

        List1.AddItem Format$(x, "000")

        Next

    MsgBox GetTickCount - Tp


End Sub

Daniel

X nbr alea non repeter

13 réponses

Votre réponse

Discussions similaires