Générateur d'une série de nombres

**IME14** · 28/08/2017, 12h34

Bonjour,

Quelqu'un pourrai m'aider au niveau de ce problème :

Je cherche à trouver un algorithme sous "langage c" ou "VBA" qui génère des série de 6 nombres N1N2N3N4N5N6 sous les contraintes suivantes :

1- Les Ni varient de 1 à 30.
2- Pour tout i, j de 1 à 6, Ni différent de Nj.
3- Je ne veux pas avoir meme nombres dans deux série (par exemple si la série N°1 est: 123456, tous les séries qui se composent de 1, 2, 3, 4, 5, 6 sont inacceptable).

merci pour tous vos repenses.

**tbc92** · 28/08/2017, 12h56

La dernière contrainte est 'embêtante'. Pour savoir comment la gérer, il faut une information supplémentaire : combien de tirages (environ) tu dois faire. Si tu dois faire une trentaine de tirages, on peut pour chaque tirage tester en comparant avec tous les tirages précédents, mais si tu dois faire 50000 tirages, ou plus, il faut procéder différemment.

**IME14** · 28/08/2017, 13h03

Je cherche de trouver tout les possibilité.
je pense pas que ça va dépasser 2000 séries!

**tbc92** · 28/08/2017, 13h23

Cette contrainte (ne pas sortir 2 fois la même série , en prenant en compte que 1,2,3,4,5,6, c'est comme 1,2,3,4,6,5 ), comment la gérer ?

Option 1 : on fait un tirage au hasard, on compare les 6 nombres tirés avec tous les jeux déjà sortis, et si c'est unn jeu déjà sorti, on refait un tirage au hasard. Au risque de devoir faire 10 ou 20 essais si on a déjà fait beaucoup de tirages.

Option 2 : on recense une fois pour toutes toutes les combinaisons possibles ( il y en a 30x29x28x27x26x25/6/5/4/3/2/1 = 593775 ; A chaque tirage parmi ces 593775 combinaisons, on supprime la combinaison en question de la liste des combinaisons disponibles.

Ici, avec jusqu'à 2000 tirages à faire, les 2 options sont viables, mais je suis quand même partisan de l'option 2.

**IME14** · 28/08/2017, 15h18

Oui c'est exact tu as bien compris le problème.

Pou l'option 1: oui c'est exactement l'idée que j'ai, mais je l'ai programme sous langage VBA Excel & Langage C l’exciton des deux programmes ne donenet pas des résultats je ne sais pas ou est le problème ci-dessous le code en VBA EXCEL:

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
63
64
65
66
Sub programme()
Dim n1 As Integer
Dim n2 As Integer
Dim n3 As Integer
Dim n4 As Integer
Dim n5 As Integer
Dim n6 As Integer
Dim j As Integer
Dim initial As Integer
 
 
 
Dim r As Integer
i = 1
For n1 = 1 To 7
For n2 = 1 To 7
For n3 = 1 To 7
For n4 = 1 To 7
For n5 = 1 To 7
For n6 = 1 To 7
 
initial = 1
r = 1
p = i
If n1 <> n2 And n1 <> n3 And n1 <> n4 And n1 <> n5 And n1 <> n6 And n2 <> n3 And n2 <> n4 And n2 <> n5 And n2 <> n6 And n3 <> n4 And n3 <> n5 And n3 <> n6 And n4 <> n5 And n4 <> n6 And n5 <> n6 Then
If initial = 1 Then
initial = initial + 1
r = 0
Else
 
For j = 1 To p
If (n1 = Cells(j, 1) Or n1 = Cells(j, 2) Or n1 = Cells(j, 3) Or n1 = Cells(j, 4) Or n1 = Cells(j, 5) Or n1 = Cells(j, 6)) Then
If (n2 = Cells(j, 1) Or n2 = Cells(j, 2) Or n2 = Cells(j, 3) Or n2 = Cells(j, 4) Or n2 = Cells(j, 5) Or n2 = Cells(j, 6)) Then
If (n3 = Cells(j, 1) Or n3 = Cells(j, 2) Or n3 = Cells(j, 3) Or n3 = Cells(j, 4) Or n3 = Cells(j, 5) Or n3 = Cells(j, 6)) Then
If (n4 = Cells(j, 1) Or n4 = Cells(j, 2) Or n4 = Cells(j, 3) Or n4 = Cells(j, 4) Or n4 = Cells(j, 5) Or n4 = Cells(j, 6)) Then
If (n5 = Cells(j, 1) Or n5 = Cells(j, 2) Or n5 = Cells(j, 3) Or n5 = Cells(j, 4) Or n5 = Cells(j, 5) Or n5 = Cells(j, 6)) Then
If (n6 = Cells(j, 1) Or n6 = Cells(j, 2) Or n6 = Cells(j, 3) Or n6 = Cells(j, 4) Or n6 = Cells(j, 5) Or n6 = Cells(j, 6)) Then
r = 0
End If
End If
End If
End If
End If
End If
End If
Next
End If
 
If (r = 0) Then
Cells(i, 1) = n1
Cells(i, 2) = n2
Cells(i, 3) = n3
Cells(i, 4) = n4
Cells(i, 5) = n5
Cells(i, 6) = n6
i = i + 1
End If
 
Next
Next
Next
Next
Next
Next
 
End Sub

Pour l'option 2: le nombre des possibilités totale sans compté la 3ème contrainte A(30,6) >>> 33 million (c'est le nombre des arrangement) et non pas 30x29x28x27x26x25/6/5/4/3/2/1 = 593775, donc ça va prendre énormément du temps pour lister et tester un par un meme pour la complexité de programme...

**wiwaxia** · 28/08/2017, 15h23

On peut aussi caractériser toute combinaison de six termes par une fonction somme appropriée, qui prenne une valeur caractéristique; par exemple:
# F(N₁, ... ,N₆) = S_i=1⁶(N_i^k) (le choix de l'exposant minimal (k) ne va pas de soi, il dépasse probablement (2));
# F(N₁, ... ,N₆) = S_i=1⁶(K / N_i) ;
il faut alors prendre K = PPCM(2, 3, 4, ... , 30) = 2⁴ * 3³ * 5² * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 2 329 089 562 800 (calculs à vérifier).

C'est d'ailleurs une question au sujet de laquelle je n'ai pas rencontré de réponse générale.

Une autre solution consiste à:
a) ranger les six termes selon l'ordre croissant, puis
b) calculer la somme (on y revient !): F(N₁, ... ,N₆) = S_i=1⁶(100^(i-1) * N_i) .
Ainsi deux combinaisons différentes ne peuvent conduire à des résultats identiques: l'application définie est bien injective.

**wiwaxia** · 28/08/2017, 15h48

Variante plus rapide:

a) ranger les six termes selon l'ordre croissant, puis
b) calculer la somme (on y revient !): F(N1, ... ,N6) = S_i=1⁶(31^(i-1) * Ni) ,
laquelle ne dépasse pas (31⁶ - 1) = 887 503 680, et peut donc être représentée par un entier au format LongInt.

La limite supérieure est en réalité plus faible: F_max = 25 + 26*31 + 27*31² + ... + 30*31⁵ = 886 517 565 .

PS: le nombre de combinaisons possibles (donc de sortes de listes, indépendamment de l'ordre des termes) est bien
C₃₀⁶ = (30!)/(6!*24!) = 593775 .
On est donc très en-dessous de la largeur des domaines des valeurs que présentent les fonctions proposées F(N₁, ... , N₆) .

**tbc92** · 29/08/2017, 00h18

@IME14
utilises des noms de variables explicites, et mets des commentaires, ça facilitera la lecture (pour toi en particulier).

Ici, tu as une variable r. Si je vois bien, tu mets r = 0 pour dire que la solution retenue est valide, et 1 pour dire qu'elle n'est pas valide. Et donc, en ligne 38, je verrais plutôt r=1

De plus, ce que je comprends de ton programme, c'est que tu ne veux pas générer 2000 combinaisons au hasard (et en respectant tes contraintes), mais tu acceptes de les générer dans un ordre logique. Ca simplifie largement la solution.

Voici un bout de code qui devrait marcher :

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
Sub programme()
Dim n1 As Integer
Dim n2 As Integer
Dim n3 As Integer
Dim n4 As Integer
Dim n5 As Integer
Dim n6 As Integer
Dim j As Integer
Dim num_ligne As Integer
Dim NB_Solutions_voulues as Integer
 
NB_Solutions_voulues
 
i = 1
For n1 = 1 To 30
 For n2 = n1+1 To 30
  For n3 = n2+1 To 30
   For n4 = n3+1 To 30
    For n5 = n4+1 To 30
     For n6 = n5+1 To 30   //  On est assuré que n1 < n2 < ... < n6 donc toutes les valeurs sont différentes.
      k = k+1
      if k > NB_Solutions_voulues then exit sub  //   On a généré 2000 combinaisons, on sort.
      Cells(k,1) = n1   
      Cells(k,2) = n2   
      Cells(k,3) = n3   
      Cells(k,4) = n4   
      Cells(k,5) = n5   
      Cells(k,6) = n6   
     Next
    Next
   Next
  Next
 Next
Next
End Sub

**wiwaxia** · 29/08/2017, 07h50

Générer une liste dans l'ordre croissant permet effectivement de se dispenser de tout contrôle.
Mais ne vaudrait -il pas mieux écrire:

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
Dim n1 As Integer
Dim n2 As Integer
Dim n3 As Integer
Dim n4 As Integer
Dim n5 As Integer
Dim n6 As Integer
Dim k As Integer
Dim num_ligne As Integer
Dim NB_Solutions_voulues as Integer

NB_Solutions_voulues
 
k = 1
For n1 = 1 To 25
 For n2 = n1+1 To 26
  For n3 = n2+1 To 27
   For n4 = n3+1 To 28
    For n5 = n4+1 To 29
     For n6 = n5+1 To 30   //  On est assuré que n1 < n2 < ... < n6 donc toutes les valeurs sont différentes.
      k = k+1
 ...

afin de bien initialiser le compteur, et que les listes présentent les propriétés recherchées ?

**tbc92** · 29/08/2017, 09h10

L'initialisation k=1 est peut-être nécessaire, je ne pratique pas assez VBA pour le confirmer, et je n'ai pas testé.
Les plafonds 25 ,26, 27 ... au lieu de 30,30,30... ne changent rien au résultat lui-même. Mais c'est effectivement mieux, ça améliore un peu la performance.

**wiwaxia** · 29/08/2017, 09h49

Le maintien de la limite unique (30) risque de provoquer un plantage à l'exécution

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
For n1 = 1 To 30
 For n2 = n1+1 To 30
  For n3 = n2+1 To 30
   For n4 = n3+1 To 30
    For n5 = n4+1 To 30
     For n6 = n5+1 To 30

car lorsque (n1) vaudra 30, la seconde boucle deviendra numériquement

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 For n2 = 31 To 30

et ainsi de suite ...
Je ne connais pas le langage, et ne sais pas comment réagira le logiciel à cette anomalie.
C'est une erreur logique, qu'il paraît préférable d'éliminer ... Il est d'ailleurs possible que le programme fonctionne sans ennui, dans la mesure où le nombre de séquences (2000) est très inférieur à l'effectif théorique (593775).

# Remarque: puisqu'on aborde ce point de détail, on pourrait introduire un facteur aléatoire en insérant dans l'énumération précédente une condition du genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
IF (Random<0.01) THEN    // instruction à traduire ...

qui permettrait de ne retenir qu'un cas sur cent (on peut s'offrir ce luxe), et de ne pas se retrouver avec la liste compacte des 2000 premières séquences consécutives.
Le seul risque est de récupérer moins de 2000 résultats.

**tbc92** · 29/08/2017, 10h52

Si on veut 'dispatcher' régulièrement les solutions retenues, on peut procéder comme ci-dessous (variables rest_univ et rest_2000) :

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
Sub programme()
Dim n1 As Integer
Dim n2 As Integer
Dim n3 As Integer
Dim n4 As Integer
Dim n5 As Integer
Dim n6 As Integer
Dim j As Integer
Dim Rest_univ as integer, rest_2000 as integer
Dim num_ligne As Integer
Dim NB_Solutions_voulues as Integer
 
NB_Solutions_voulues = 2000
rest_2000 = NB_Solutions_voulues
rest_univ = 593775
 
k=1
For n1 = 1 To 25
 For n2 = n1+1 To 26
  For n3 = n2+1 To 27
   For n4 = n3+1 To 28
    For n5 = n4+1 To 29
     For n6 = n5+1 To 30   //  On est assuré que n1 < n2 < ... < n6 donc toutes les valeurs sont différentes.
      if random() <= rest_2000 / rest_univ then
        k++
        Cells(k,1) = n1   
        Cells(k,2) = n2   
        Cells(k,3) = n3   
        Cells(k,4) = n4   
        Cells(k,5) = n5   
        Cells(k,6) = n6
        rest_2000 --
       end if   
       rest_univ --
     Next
    Next
   Next
  Next
 Next
Next
End Sub

Et dans ce cas, pour être complet, il faut trouver une solution pour permuter aléatoirement les 6 nombres n1,n2,n3,n4,n5,n6 juste avant écriture dans le fichier. (Pas permuter les nombres eux-mêmes, bien sûr, ça planterait les boucles, mais faire en sorte d'écrire aléatoirement n1 en colonne 1 ... ou dans une autre colonne).

**IME14** · 29/08/2017, 11h17

Je vous remercie le programme marche bien mais juste prend énormément du temps dans l'exécution surtout si j'augmente la variable rest_2000 à 30000.
le pire c'est que lorsque je l'augment plus que 40000 au but d'avoir tout toutes le possibilité le programme ne s'exécute pas (message : dépassement de la capacité)...

**tbc92** · 29/08/2017, 12h18

Je pense que si tu mets nb_solutions_voulues = 32767, ça marche, mais à partir de 32768, ça plante. Explication : le type Integer ne supporte pas les nombres au-delà de 32767. Il faut utiliser le type Long. (en fait j'ai un doute, mais je pense quand même que c'est ça)

La dernière variante est effectivement lente, en gros 200 fois plus lente que ma première proposition si on demande juste 3000 combinaisons : en effet, on envisage toutes les possibilités, et on les rejette quasiment toutes, pour en garder en moyenne une sur 200.

Cette variante ci-dessous semble un bon compromis (5 fois plus rapide que la précédente, permet de générer jusqu'à 118755 combinaisons). Et on peut l'adapter en figeant aussi n5 (une seule valeur pour chaque groupe n1,n2,n3,n4) ; et dans ce cas, on peut aller jusqu'à 20475 combinaisons:

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
Sub programme()
Dim n1 As Integer
Dim n2 As Integer
Dim n3 As Integer
Dim n4 As Integer
Dim n5 As Integer
Dim n6 As Integer
Dim j As Integer
 
Dim Rest_univ as long , rest_2000 as long
Dim k as Long , NB_Solutions_voulues as Long
 
NB_Solutions_voulues = 2000
rest_2000 = NB_Solutions_voulues
rest_univ = 118755
 
k=1
For n1 = 1 To 25
 For n2 = n1+1 To 26
  For n3 = n2+1 To 27
   For n4 = n3+1 To 28
    For n5 = n4+1 To 29
      j = round ( random ()* (29-n5),0)  
      n6 = n5+1+j     //  On est assuré que n1 < n2 < ... < n6 donc toutes les valeurs sont différentes.
      if random() <= rest_2000 / rest_univ then
        k++
        Cells(k,1) = n1   
        Cells(k,2) = n2   
        Cells(k,3) = n3   
        Cells(k,4) = n4   
        Cells(k,5) = n5   
        Cells(k,6) = n6
        rest_2000 --
       end if   
       rest_univ --
     Next
    Next
   Next
  Next
 Next
Next
End Sub

Générateur d'une série de nombres

Algorithmes et structures de données

Discussions similaires

Partager

Partager