Version imprimable
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.
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.
Je cherche de trouver tout les possibilité.
je pense pas que ça va dépasser 2000 séries!
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.
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:
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
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...
:D 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(N1, ... ,N6) = Si=16(Nik) (le choix de l'exposant minimal (k) ne va pas de soi, il dépasse probablement (2));
# F(N1, ... ,N6) = Si=16(K / Ni) ;
il faut alors prendre K = PPCM(2, 3, 4, ... , 30) = 24 * 33 * 52 * 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(N1, ... ,N6) = Si=16(100(i-1) * Ni) .
Ainsi deux combinaisons différentes ne peuvent conduire à des résultats identiques: l'application définie est bien injective.
Variante plus rapide:
a) ranger les six termes selon l'ordre croissant, puis
b) calculer la somme (on y revient !): F(N1, ... ,N6) = Si=16(31(i-1) * Ni) ,
laquelle ne dépasse pas (316 - 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: Fmax = 25 + 26*31 + 27*312 + ... + 30*315 = 886 517 565 .
PS: le nombre de combinaisons possibles (donc de sortes de listes, indépendamment de l'ordre des termes) est bien
C306 = (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(N1, ... , N6) .
@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:
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
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:
afin de bien initialiser le compteur, et que les listes présentent les propriétés recherchées ?Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22Dim 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 ...
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.
Le maintien de la limite unique (30) risque de provoquer un plantage à l'exécution
car lorsque (n1) vaudra 30, la seconde boucle deviendra numériquementCode:
2
3
4
5
6
7
et ainsi de suite ...Code:
2
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:
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.Code:
2
Le seul risque est de récupérer moins de 2000 résultats.
Si on veut 'dispatcher' régulièrement les solutions retenues, on peut procéder comme ci-dessous (variables rest_univ et rest_2000) :
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).Code:
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
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é)...
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:
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