Systèmes Réducteur nouvel algo

**zhao** · 19/08/2008, 11h59

Bonjour Zavonen :-)

Je crois comprendre ce que tu veut dire en gros il faudrait a ton programme une heuristique de type génétique ou similaire pour exploiter a fond ton idée ?
Bon j'ai l'impression que beaucoup d'espoir repose maintenant sur les epaules de
khayyam90 en tout cas j'espere qu'il accepteras de se lancer dans la bataille :-)
et qu'il auras le temps de faire un prog C sur ce concept de génétique avec mes souhaits que j'ai donné plus haut et un autre avec ton idée ça serais vraiment génial , je reprends espoir :-)
j'ai quand même l'impression que la ténacité paie :-)
@+ :-)

**Nemerle** · 20/08/2008, 13h57

Si j'étais vous, je regarderai les représentations du groupe symétrique...

**pseudocode** · 20/08/2008, 14h31

Envoyé par Nemerle

Si j'étais vous, je regarderai les représentations du groupe symétrique...

Je ne vois pas où tu veux en venir.

Pour rester dans le domaine des groupes, pour moi le problème serait plus dans la construction de l'action de groupe qui consiste à choisir "k" elements dans un set de X=C(n,p).

**pseudocode** · 21/08/2008, 11h30

Comme j'aime bien les images, j'ai représenté graphiquement la matrice du "nombre d'elements en commun" entre les grilles prises 2 à 2. J'ai mis un "X" dans la case de la matrice si ce nombre est supérieur ou égal a K.

--> image pour les cas 10 6/5

Le probleme consiste donc a prendre des lignes de la matrice telle que leur réunion fasse une ligne complète de "X". Dans les cas 10 6/5, voici une solution a 14 lignes:

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
 
[01 03 04 05 08 09 ] :   XX        X         X                   X                            XX XX XXX   X  X  X   X  X  X        X  X  X                  X                                                   X  X  X                  
[02 04 05 07 09 10 ] :                                         XX  X        X         X                                                 X                 XX  X        X         X       XX  XXXXX  X X  X X         X              X X  
[01 02 04 06 08 10 ] :       X X    X               X      X X    X X XXXX X X    X      X X               X                        X      X X                     X                        X      X X                                   
[03 05 06 07 08 10 ] :                                                                                           X X X  X   X                   X                        X X X  X   X                   X    X X X  X   X   XXXXXX X    X
[01 02 03 06 07 09 ] :      X X  X    X X  X    XXXX XX X            X         X        X X             X         X        X X                                  X         X        X X                                                   
[01 02 03 04 05 10 ] : XXXXX   X  X XX   X  X XX             X  X XX                            X  X XX                                                 X  X XX                                                                          
[03 04 06 07 08 09 ] :                                                                                 XX X  X             X              X                    XX X  X             X              X          XX X  X   XXXXXX    XX    X 
[01 05 07 08 09 10 ] :                                                              XXXX    X                          XXXX    X      XXXX    XXXXXXX                                                      X                    X     X X
[02 03 05 06 08 09 ] :                 XX    X     X                             X                                  X                                 XX    X     X      XX XXXX  XX  X    X           X  X     X           X  X         
[01 02 04 05 06 07 ] : XX   X         X                   XXXXXXX   XXX       XXX            X                                  XXX                  X                                  XXX                                              
[01 03 04 06 09 10 ] :        XX     X               X                   X                     XX     X XXXXX  XX     X      XX      X      XX                      X                                             X      XX              
[02 03 04 07 08 10 ] :          X X X                  X                   X                                  X                                          X X X X X X XXXX       X   X  X       X   X  X             X   X  X             
[01 02 03 07 08 09 ] :          XX X      XX X  XX X  XXXX                X         X   X   X                X         X   X   X                                     X         X   X   X                                                 
[02 05 06 08 09 10 ] :                                                           XXX   X   X                                                      X                         XXX   X   X    XXX   X   X XXXXXX                  X     X  X
Réunion des lignes   : XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Si quelqu'un est amateur de Tetris...

**Zavonen** · 21/08/2008, 12h02

Envoyé par pseudocode

Comme j'aime bien les images, j'ai représenté graphiquement la matrice du "nombre d'elements en commun" entre les grilles prises 2 à 2. J'ai mis un "X" dans la case de la matrice si ce nombre est supérieur ou égal a K.

Oui, chaque ligne correspond en fait à une boule de rayon 1, mais tu les as aplaties. De fait ni toi ni moi ne pouvons représenter correctement ces boules (en fait des hypercubes) dans un espace de dimension 6, mais si nous pouvions nous verrions tout de suite pourquoi elles s'emboitent et remplissent l'espace. Sur ta représentation plane les proximités n'apparaissent pas, tes boules sont pleines de trous.
En fait, puisque nous sommes limités du point de vue de la représentation à 3 dimensions, il faudrait trouver une astuce généralisée du genre de la géométrie descriptive pour 'voir' un relèvement à partir d'une épure.
J'avais comme toi fait le rapprochement avec le jeu mais je ne me souvenais pas bien du nom (ce gadget russe faisait fureur il y a plusieurs années), je l'ai nommé 'Tantrix' au lieu de 'Tetris' (appelation correcte).

**zhao** · 21/08/2008, 15h31

Bonjour Zavonen,Pseudocode,khayyam90 et a tout le forum .

Parfait j'observe , j'apprends bref je me regale jamais j'aurais pensé a ce genre de choses :-)

J'espere que khayyam90 me feras mon prog C comme je le souhaitais dans un de mes post j'aimerais tellement avoir ce genre de prog pour l'étudier et le comprendre enfin on verra bien :-)
@+ :-)

**khayyam90** · 22/08/2008, 13h57

Envoyé par zhao

J'espere que khayyam90 me feras mon prog C[...]

oulala, un algorithme génétique ne s'écrit pas comme ça
* je ne vois toujours pas comment appliquer un algo génétique à ton problème (fonction à optimiser ? types d'objets à considérer ?)
* mine de rien, ça prend pas mal de temps

zhao, tout ce que je peux faire c'est t'encourager à lire les docs à ce sujet.

**Zavonen** · 22/08/2008, 19h52

Et je gagne !
10 systèmes réducteurs à 14 éléments pour 10-5/6

70 [[2, 3, 4, 6, 8, 9], [1, 6, 7, 8, 9, 10], [2, 4, 5, 7, 9, 10], [1, 3, 4, 5, 8, 10], [1, 2, 3, 5, 6, 7], [4, 5, 6, 7, 8, 10], [2, 3, 7, 8, 9, 10], [1, 3, 5, 6, 9, 10], [1, 2, 4, 5, 8, 9], [1, 3, 4, 6, 7, 9], [1, 2, 3, 4, 6, 10], [2, 5, 6, 7, 8, 10], [3, 4, 5, 7, 8, 9], [1, 2, 4, 7, 8, 10]]
72 [[2, 3, 4, 6, 7, 9], [1, 6, 7, 8, 9, 10], [2, 4, 5, 8, 9, 10], [1, 3, 4, 5, 7, 10], [1, 2, 3, 5, 6, 8], [4, 5, 6, 7, 8, 10], [2, 3, 7, 8, 9, 10], [1, 3, 5, 6, 9, 10], [1, 2, 4, 5, 7, 9], [1, 3, 4, 6, 8, 9], [1, 2, 3, 4, 6, 10], [2, 5, 6, 7, 8, 10], [3, 4, 5, 7, 8, 9], [1, 2, 4, 7, 8, 10]]
73 [[2, 3, 4, 6, 7, 8], [1, 6, 7, 8, 9, 10], [2, 4, 5, 8, 9, 10], [1, 3, 4, 5, 7, 10], [1, 2, 3, 5, 6, 9], [4, 5, 6, 7, 9, 10], [2, 3, 7, 8, 9, 10], [1, 3, 5, 6, 8, 10], [1, 2, 4, 5, 7, 8], [1, 3, 4, 6, 8, 9], [1, 2, 3, 4, 6, 10], [2, 5, 6, 7, 9, 10], [3, 4, 5, 7, 8, 9], [1, 2, 4, 7, 9, 10]]
76 [[2, 3, 4, 5, 8, 9], [1, 5, 7, 8, 9, 10], [2, 4, 5, 6, 7, 10], [1, 3, 4, 6, 7, 8], [1, 2, 3, 6, 9, 10], [4, 6, 7, 8, 9, 10], [2, 3, 5, 7, 8, 10], [1, 3, 5, 6, 7, 9], [1, 2, 4, 5, 6, 8], [1, 3, 4, 5, 9, 10], [1, 2, 3, 4, 7, 9], [2, 6, 7, 8, 9, 10], [3, 4, 5, 6, 8, 10], [1, 2, 4, 8, 9, 10]]
78 [[2, 3, 4, 5, 7, 9], [1, 5, 7, 8, 9, 10], [2, 4, 5, 6, 8, 10], [1, 3, 4, 6, 7, 8], [1, 2, 3, 6, 9, 10], [4, 6, 7, 8, 9, 10], [2, 3, 5, 7, 8, 10], [1, 3, 5, 6, 8, 9], [1, 2, 4, 5, 6, 7], [1, 3, 4, 5, 9, 10], [1, 2, 3, 4, 8, 9], [2, 6, 7, 8, 9, 10], [3, 4, 5, 6, 7, 10], [1, 2, 4, 7, 9, 10]]
79 [[2, 3, 4, 5, 7, 8], [1, 5, 7, 8, 9, 10], [2, 4, 5, 6, 9, 10], [1, 3, 4, 6, 8, 10], [1, 2, 3, 6, 7, 9], [4, 6, 7, 8, 9, 10], [2, 3, 5, 8, 9, 10], [1, 3, 5, 6, 7, 10], [1, 2, 4, 5, 6, 8], [1, 3, 4, 5, 7, 9], [1, 2, 3, 4, 7, 10], [2, 6, 7, 8, 9, 10], [3, 4, 5, 6, 8, 9], [1, 2, 4, 8, 9, 10]]
100 [[1, 4, 5, 6, 8, 10], [2, 3, 5, 6, 7, 9], [1, 2, 7, 8, 9, 10], [3, 4, 7, 8, 9, 10], [1, 2, 3, 4, 6, 10], [2, 4, 5, 6, 8, 9], [1, 3, 5, 6, 7, 8], [1, 4, 5, 7, 9, 10], [2, 3, 5, 8, 9, 10], [1, 2, 3, 4, 5, 7], [2, 4, 6, 7, 8, 10], [1, 3, 4, 6, 8, 9], [3, 5, 6, 7, 9, 10], [1, 2, 6, 7, 9, 10]]
115 [[1, 3, 5, 6, 8, 10], [2, 4, 5, 6, 7, 9], [1, 2, 7, 8, 9, 10], [3, 4, 7, 8, 9, 10], [1, 2, 3, 4, 6, 10], [2, 3, 5, 6, 8, 9], [1, 4, 5, 6, 7, 8], [1, 3, 5, 7, 9, 10], [2, 4, 5, 8, 9, 10], [1, 2, 3, 4, 5, 7], [2, 3, 6, 7, 8, 10], [1, 3, 4, 6, 8, 9], [4, 5, 6, 7, 9, 10], [1, 2, 6, 7, 9, 10]]
185 [[1, 2, 3, 5, 9, 10], [1, 2, 6, 7, 8, 10], [3, 4, 5, 7, 8, 10], [2, 4, 5, 6, 8, 9], [1, 3, 4, 6, 7, 9], [5, 6, 7, 8, 9, 10], [2, 3, 4, 6, 7, 10], [1, 3, 4, 8, 9, 10], [1, 2, 4, 5, 7, 9], [1, 2, 3, 5, 6, 8], [2, 3, 7, 8, 9, 10], [1, 4, 5, 6, 9, 10], [1, 3, 5, 6, 7, 9], [1, 2, 4, 5, 7, 8]]
195 [[1, 2, 3, 4, 9, 10], [1, 2, 6, 7, 8, 10], [3, 4, 5, 7, 8, 10], [2, 4, 5, 6, 8, 9], [1, 3, 5, 6, 7, 9], [4, 6, 7, 8, 9, 10], [2, 3, 5, 6, 7, 10], [1, 3, 5, 8, 9, 10], [1, 2, 4, 5, 7, 9], [1, 2, 3, 4, 6, 8], [2, 3, 7, 8, 9, 10], [1, 4, 5, 6, 9, 10], [1, 3, 4, 6, 7, 9], [1, 2, 4, 5, 7, 8]]
>>>

Je laisse tomber les boules une à une et appliquant deux principes:
Remplir le plus d'espace possible. Ne jamais laisser un espace trop grand inoccupé.

Code python :

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
# -*- coding: cp1252 -*-
 
#décide si la décomposition de n en binaire comporte exactement p chiffres 1.
def hpcb(n,p):
    s=0
    while n:
        s+=n%2
        n=n/2
    return s==p
 
# retourne tous les nombres entre 0 et n-1 ayant p fois le chiffre 1 en système binaire
def fcar(p,n):
    return [i for i in range(0,n) if hpcb(i,p)]
 
# merci Guigui !
def bin_optimise(n):
    """Convertit un nombre en binaire"""
    if n == 0: return '0'
    res = ''
    while n != 0: n, res = n >> 1, `n & 1` + res
    res='0'*(10-len(res))+res
    return res
 
# retourne toutes les combinaisons de E à p éléments dans l'ordre
def Combinaisons (E,p):
    H=fcar(p,2**len(E))
    #H.reverse()
    return H
 
# associe une partie de L à p élément à un nombre
def assoc(L,h):
    k = len(L)-1
    M=[L[k-i] for i in range(0,k+1)]
    result=[]
    i=0
    while h:
        r=h%2
        if r:
            result.append(M[i])
        h=h/2
        i+=1
    result.reverse()
    return result
 
 
def dist(X,Y):
    global AL
    acc=0
    s1=AL.get(X)
    s2=AL.get(Y)
    for i in range(0,len(s1)):
        if s1[i]=='1' and s2[i]=='1':
            acc+=1
    return 6-acc
 
def Boule(X):
    global Tab1
    return [Y for Y in Tab1 if dist(X,Y)<=1]
 
def join(L1,L2):
    R=L1[:]
    R+=[X for X in L2 if X not in L1]
    R.sort()
    return R
 
def maxhole(L):
    return max([(L[i+1]-L[i]) for i in range(0,len(L)-1)])
 
#variables globales
Valid=[]
Tab1=[]
E=range(1,11)
Ligne=[]
AL=dict()
 
def next():
    global Tab1,Ligne
    def S(X):
        return sum([1 for Y in Boule(X) if Y not in Ligne])
    M=max([S(X) for X in Tab1])
    Tab2=[X for X in Tab1 if S(X)==M]
    m=min([maxhole(join(Ligne,Boule(X))) for X in Tab2])
    R=[X for X in Tab2 if maxhole(join(Ligne,Boule(X)))==m]
    return R
 
def step(i):
    global Valid, Ligne
    x=next()[0]
    Ligne=join(Ligne,Boule(x))
    Valid.append(x)
 
def main():
    global Reste,Tab1,Valid,E,Ligne,Bin,AL
    Tab1=Combinaisons(E,6)
    Valid=[]
    AL=dict([[X,bin_optimise(X)]for X in Tab1])
    Count=0
    for i in range(70,209):
        Ligne=Boule(Tab1[i])
        Valid=[]
        Valid.append(Tab1[i])
        for j in range(1,14):
            step(j)
        if len(Ligne)>=210:
            print i, [assoc(E,X) for X in Valid]
 
if __name__ == '__main__':
    main()

**zhao** · 22/08/2008, 23h43

WHAOUU Zavonen je suis IMPRESSIONNE tu est le meilleur , je sais pas comment tu as pu penser a ce genre de choses ( que j'ai toujours pas bien compris d'ailleurs ;-) )
Je viens de les verifier elles sont toutes BONNES :-)
vraimennt chapeau bas :-)

**zhao** · 22/08/2008, 23h49

Envoyé par khayyam90

oulala, un algorithme génétique ne s'écrit pas comme ça
* je ne vois toujours pas comment appliquer un algo génétique à ton problème (fonction à optimiser ? types d'objets à considérer ?)
* mine de rien, ça prend pas mal de temps

zhao, tout ce que je peux faire c'est t'encourager à lire les docs à ce sujet.

J'ai deja lu et j'essaie de comprendre et franchement cela n'est pas evident pour moi :-)
Mais c'est pas grave si tu n'as pas le temps je comprends je mettrais beaucoup beaucoup plus de temps a essayer de le mettre au point moi meme ( a mon avis ça va se chiffrer en années ;-) )
Ce qu'il faut comprendre c'est que je n'ai pas votre niveau et que pour comprendre j'ai besoin d'exemple correspondant a mon probleme be oui on n'est pas tous egaux a ce niveau :-)
@+ :-)

**Zavonen** · 23/08/2008, 19h37

@ Zhao:
Voici l'équivalent C du programme python précédent.
Il tourne à peu près en 15 secondes et trouve les 10 mêmes solutions.
Je pense qu'il est généralisable mais je n'ai pas eu le temps de le paramétrer, tu pourras peut être le faire toi-même (je donne quelques indications en commentaires).
A fin Septembre.

Code C :

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
#include <stdio.h>
#include <stdlib.h>
 
unsigned int * Tab1,*Valid; // Les trois tableaux du traitement (algo Zhao)
unsigned int taille; // contiendra la taille de Tab1, Reste et Valid
unsigned char * numeros; // Contiendra tous les numéros possibles (1,2,3,...10,..)
unsigned int * Ligne; // la ligne à remplir
// 210 et 25 à remplacer dans le cas général
unsigned int  Boules[210][25]; // les 210 boules unité
unsigned int *Q; // purement utilitaire
unsigned int *T; // idem
 
//calcule les puissances de 2
unsigned int power2(unsigned int n)
{
    unsigned int result=1;
    int i;
    for (i=1;i<=n;i++)
        result *=2; // multiplier résultat par 2
    return result;
}
 
// calcule le nombre de chiffres de n en binaire
// une expérience récente sur le forum DVP a prouvé que les décalages ne sont pas plus rapides.
unsigned int nbcb(unsigned int n)
{
    unsigned int s=0; // totalisateur
    while (n) // tant que n est non nul
    {
        s+=n%2; // ajoute le chiffre des unités
        n/=2; // divise n par 2
    }
    return s;
}
 
// distance d'un point à un autre
// 6 est à changer pour un paramètre
unsigned int distance (unsigned int m, unsigned int n)
{
    return 6-nbcb(m&n);
}
 
// 25 est à changer pour un paramètre
// taille des boules unités
unsigned int * Boule(unsigned int n)
{
    unsigned int * R;
    unsigned int i,j;
    R= (unsigned int *) malloc(25);
    for (i=0,j=0;i<taille;i++)
    {
        if (distance(Tab1[i],n)<=1)
            R[j++]=Tab1[i];
    }
    return R;
}
 
// Calcule les coefficients Cp,n
unsigned int Cpn(unsigned int p, unsigned int n)
{
    unsigned int s=0; // totalisateur
    unsigned int i;
    for (i=0;i<power2(n);i++)
        if (nbcb(i)==p) s++;// Si p chiffres en base 2 on incrémente le compteur
    return s;
}
 
// initialise Tab1 Boules Valid numeros
// 25 à changer pour un paramètre
void init(unsigned int p,unsigned int n)
{
    unsigned int i,j;
    unsigned int *B;
    taille=Cpn(p,n); // nombre de combinaisons de p dans n
    // on remplit Tab1 à l'envers
    Ligne= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        Ligne[i]=0;
    Tab1= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0,j=0;i<power2(n);i++)
        if (nbcb(i)==p)
            Tab1[j++]=i;
    // Valid est initalisé rien qu'avec des zéros ce qui veut dire 'vide'
    Valid= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        Valid[i]=0;
    Q= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        Q[i]=0;
    T= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        T[i]=0;
    // C'est la liste des numéros possibles pour restituer les listes à partir des binaires
    numeros=(unsigned char *) malloc (n);
    for (i=0;i<n;i++)
        numeros[i]=(unsigned char)(i+1);
    for (i=0;i<taille;i++)
    {
        for (j=0;j<25;j++)
        {
            B=Boule(Tab1[i]);
            Boules[i][j]=B[j];
            free(B);
        }
    }
}
 
// ajouter un élément à Valid
// on le met au premier emplacement contenant une donnée nulle
void append(unsigned int n)
{
    unsigned int i=0;
    while (Valid[i])i++; // avancer jusqu'à trouver un zéro
    Valid[i]=n;
}
 
// Calcule la longueur d'un tableau (le nombre d'éléments non nuls)
unsigned int longueur (unsigned int * T)
{
    unsigned int i,s=0;
    for (i=0;i<taille;i++)
        if (T[i])s++;
        else
            break;
    return s;
}
 
// reconstitue une liste de numéros à partir d'un nombre binaire
char * restitue (unsigned int n,unsigned int p, unsigned int k)
{
    char * r=(char *) malloc(p); // pour p nombres tous <256
    unsigned int i,u,v;
    for (i=0;i<p;i++)
        r[i]=0;
    i=0;
    v=0;
    while (k) // tant que k n'est pas nul
    {
        u=k%2; // prendre le chiffre des unités de k
        if (u) // est il égal à 1 ?
            r[v++]=numeros[i]; // Si oui placer le numéro correspondant
        k=k/2; // diviser k par 2
        i++; // incrémenter i
    }
    return r;
}
 
// Liste tous les binaires de Valid sous forme de listes
void MontreValid(unsigned int n,unsigned int p, unsigned int r)
{
    unsigned int i,j; // compteurs de boucles
    char * pc; // pour récupérer les listes
    printf("%d\n",r);
    printf("Solution:\n");
    for (i=0;i<14;i++) // affichage des éléments de Valid
    {
        pc=restitue(n,p,Valid[i]); // allocation de mémoire et affectation
        for (j=0;j<p;j++) // affiche la liste reconstituée
            printf("%2d ",pc[j]);
        printf("\n");
        free(pc); // libération de la mémoire allouée
    }
}
 
// vérifie si l'entier k est dans la liste L
int IsIn(unsigned int k, unsigned int * L, unsigned int q)
{
    unsigned int i;
    for (i=0;i<q;i++)
        if (k==L[i])
            return 1;
    return 0;
}
 
//combien d'éléments nouveaux apporte la boule de centre
// Tab1[n] à Ligne
// 25 à changer pour un paramètre
unsigned int Brings(unsigned int n)
{
    unsigned int i,s;
    s=0;
    for (i=0;i<25;i++)
    {
        if (!IsIn(Boules[n][i],Ligne, longueur(Ligne)))
            s++;
    }
    return s;
}
// apport maximum possible à Ligne par ajout d'une boule
unsigned int AppMax()
{
    unsigned int M=0;
    unsigned int i,a;
    for (i=0;i<taille;i++)
    {
        a=Brings(i);
        if (a>M)
            M=a;
    }
    return M;
}
 
// distance maximum entre deux entiers consécutifs
// de la liste triée L de longueur n
unsigned int MaxHole(unsigned int * L, unsigned int n)
{
    unsigned int m=0;
    unsigned int i;
    for (i=0; i<n-1;i++)
    {
        if ((L[i+1]-L[i])>m)
            m=L[i+1]-L[i];
    }
    return m;
}
 
 
// fonction de comparaison pour qsort (appel dans join)
int comp (const void * a, const void * b)
{
    return *(int *)a - *(int *)b;
}
 
// ajoute à L les éléments de la boule de centre Tab1[k]
// qui n'y sont pas déjà et trie L par ordre croissant
// 25 à changer pour un paramètre
void join(unsigned int * L, unsigned int k)
{
    unsigned int i,j;
    i=0;
    while (L[i]) i++;
    for (j=0;j<25;j++)
    {
        if (!IsIn(Boules[k][j],L,longueur(L)))
            L[i++]=Boules[k][j];
    }
    qsort(L,longueur(L),sizeof(int),comp);
}
 
// recherche le minimum des MaxHole
// pour des indices situés dans T
// 2000 arbitraire doit être supérieur à la plus grande valeur de Tab1
unsigned int MinMaxHole(unsigned int *T,unsigned int tT )
{
    unsigned int i,j,m,a;
    for (i=0,m=2000;i<tT;i++)
    {
        for (j=0;j<taille;j++)
            Q[j]=Ligne[j];
        join(Q,T[i]);
        a=MaxHole(Q,longueur(Q));
        if (a<m)
            m=a;
    }
    return m;
}
 
// trouve le prochain indice à retenir
unsigned int Next()
{
    unsigned int M=AppMax();
    unsigned int m,i,j,s,a,b,tT;
    for (i=0,s=0;i<taille;i++)
    {
        if (Brings(i)==M)
            s++;
    }
    for (i=0;i<taille;i++)
        T[i]=0;
    tT=0;
    for (i=0,j=0;i<taille;i++)
    {
        if (Brings(i)==M)
        {
            T[j++]=i;
            tT++;
        }
    }
    m=MinMaxHole(T,tT);
    for (i=0;i<tT;i++)
    {
        for (j=0;j<taille;j++)
            Q[j]=Ligne[j];
        join(Q,T[i]);
        a=MaxHole(Q,longueur(Q));
        if (a==m)
            break;
    }
    b=T[i];
    return b;
}
 
void Step()
{
    unsigned int k=Next();
    join(Ligne,k);
    append(Tab1[k]);
}
 
// Voir la ligne
void MontreLigne()
{
    unsigned int i;
    for (i=0;i<taille;i++)
        printf("%04d-",Ligne[i]);
}
 
//fonction principale
// 210 à remplacer par paramètre
int main()
{
    unsigned int i,j,k;
    init(6,10); // initialisation
    for (i=0,k=1;i<210;i++)
    {
        // réinitialisation de ligne
        for (j=0;j<taille;j++)
            Ligne[j]=0;
        // réinitialisation de Valid
        for (j=0;j<15;j++)
            Valid[j]=0;
        join(Ligne,i);
        append(Tab1[i]);
        for (j=0;j<13;j++)
            Step();
        if (Ligne[209])
        {
            printf("%d-%d\n",k++,i);
            MontreValid(10,6,i);
        }
    }
 
    return 0;
}

**zhao** · 24/08/2008, 01h23

Merci beaucoup Zavonen ,merci pour ta patience ,ta disponibilité et surtout cette envie de transmettre un peu de ton savoir pour que des personnes comme moi puissent progresser , je vais donc "étudier" ton prog pendant tes vacances :-)
Amicalement
Zhao

**Zavonen** · 24/08/2008, 23h29

@ Zhao (et à tous ceux que cela intéresse).
Tu as eu des difficultés à modifier mon prog parce que ma fonction init est mal écrite (à vrai dire bravo au compilo C de la faire fonctionner quand même pour l'original). Ceci est une version corrigée du programme C, modifiée et adaptée au cas 11-5/6
On trouve exactement 40 systèmes réducteurs à 23 éléments (en 5 minutes quand même...) ce qui me laisse à penser qu'il y a quand même des limites.
En tout cas je réécrirai tout cela proprement à mon retour quand j'aurai plus de temps:

Code C :

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
#include <stdio.h>
#include <stdlib.h>
 
unsigned int * Tab1,*Valid; // Les trois tableaux du traitement (algo Zhao)
unsigned int taille; // contiendra la taille de Tab1, Reste et Valid
unsigned char * numeros; // Contiendra tous les numéros possibles (1,2,3,...10,..)
unsigned int * Ligne; // la ligne à remplir
// 462 et 31 à remplacer dans le cas général
unsigned int  Boules[462][31]; // les 462 boules unité
unsigned int *Q; // purement utilitaire
unsigned int *T; // idem
 
//calcule les puissances de 2
unsigned int power2(unsigned int n)
{
    unsigned int result=1;
    int i;
    for (i=1;i<=n;i++)
        result *=2; // multiplier résultat par 2
    return result;
}
 
// calcule le nombre de chiffres de n en binaire
// une expérience récente sur le forum DVP a prouvé que les décalages ne sont pas plus rapides.
unsigned int nbcb(unsigned int n)
{
    unsigned int s=0; // totalisateur
    while (n) // tant que n est non nul
    {
        s+=n%2; // ajoute le chiffre des unités
        n/=2; // divise n par 2
    }
    return s;
}
 
// distance d'un point à un autre
// 6 est à changer pour un paramètre
unsigned int distance (unsigned int m, unsigned int n)
{
    return 6-nbcb(m&n);
}
 
// Calcule les coefficients Cp,n
unsigned int Cpn(unsigned int p, unsigned int n)
{
    unsigned int s=0; // totalisateur
    unsigned int i;
    for (i=0;i<power2(n);i++)
        if (nbcb(i)==p) s++;// Si p chiffres en base 2 on incrémente le compteur
    return s;
}
 
// initialise Tab1 Boules Valid numeros
// 31 à changer pour un paramètre
void init(unsigned int p,unsigned int n)
{
    unsigned int i,j,h;
    taille=Cpn(p,n); // nombre de combinaisons de p dans n
    //on remplit Tab1 à l'envers
    Ligne= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        Ligne[i]=0;
    Tab1= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0,j=0;i<power2(n);i++)
        if (nbcb(i)==p)
            Tab1[j++]=i;
    // Valid est initalisé rien qu'avec des zéros ce qui veut dire 'vide'
    Valid= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        Valid[i]=0;
    Q= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        Q[i]=0;
    T= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        T[i]=0;
    // C'est la liste des numéros possibles pour restituer les listes à partir des binaires
    numeros=(unsigned char *) malloc (n);
    for (i=0;i<n;i++)
        numeros[i]=(unsigned char)(i+1);
    for (i=0;i<taille;i++)
    {
        for(j=0,h=0;j<taille;j++)
 
        { if (distance(Tab1[i],Tab1[j])<=1)
            Boules[i][h++]=Tab1[j];
        }
    }
}
 
// ajouter un élément à Valid
// on le met au premier emplacement contenant une donnée nulle
void append(unsigned int n)
{
    unsigned int i=0;
    while (Valid[i])i++; // avancer jusqu'à trouver un zéro
    Valid[i]=n;
}
 
// Calcule la longueur d'un tableau (le nombre d'éléments non nuls)
unsigned int longueur (unsigned int * T)
{
    unsigned int i,s=0;
    for (i=0;i<taille;i++)
        if (T[i])s++;
        else
            break;
    return s;
}
 
// reconstitue une liste de numéros à partir d'un nombre binaire
char * restitue (unsigned int n,unsigned int p, unsigned int k)
{
    char * r=(char *) malloc(p); // pour p nombres tous <316
    unsigned int i,u,v;
    for (i=0;i<p;i++)
        r[i]=0;
    i=0;
    v=0;
    while (k) // tant que k n'est pas nul
    {
        u=k%2; // prendre le chiffre des unités de k
        if (u) // est il égal à 1 ?
            r[v++]=numeros[i]; // Si oui placer le numéro correspondant
        k=k/2; // diviser k par 2
        i++; // incrémenter i
    }
    return r;
}
 
// Liste tous les binaires de Valid sous forme de listes
void MontreValid(unsigned int n,unsigned int p, unsigned int r)
{
    unsigned int i,j; // compteurs de boucles
    char * pc; // pour récupérer les listes
    printf("%d\n",r);
    printf("Solution:\n");
    for (i=0;i<25;i++) // affichage des éléments de Valid
    {
        pc=restitue(n,p,Valid[i]); // allocation de mémoire et affectation
        for (j=0;j<p;j++) // affiche la liste reconstituée
            printf("%2d ",pc[j]);
        printf("\n");
        free(pc); // libération de la mémoire allouée
    }
}
 
// vérifie si l'entier k est dans la liste L
int IsIn(unsigned int k, unsigned int * L, unsigned int q)
{
    unsigned int i;
    for (i=0;i<q;i++)
        if (k==L[i])
            return 1;
    return 0;
}
 
//combien d'éléments nouveaux apporte la boule de centre
// Tab1[n] à Ligne
// 31 à changer pour un paramètre
unsigned int Brings(unsigned int n)
{
    unsigned int i,s;
    s=0;
    for (i=0;i<31;i++)
    {
        if (!IsIn(Boules[n][i],Ligne, longueur(Ligne)))
            s++;
    }
    return s;
}
// apport maximum possible à Ligne par ajout d'une boule
unsigned int AppMax()
{
    unsigned int M=0;
    unsigned int i,a;
    for (i=0;i<taille;i++)
    {
        a=Brings(i);
        if (a>M)
            M=a;
    }
    return M;
}
 
// distance maximum entre deux entiers consécutifs
// de la liste triée L de longueur n
unsigned int MaxHole(unsigned int * L, unsigned int n)
{
    unsigned int m=0;
    unsigned int i;
    for (i=0; i<n-1;i++)
    {
        if ((L[i+1]-L[i])>m)
            m=L[i+1]-L[i];
    }
    return m;
}
 
 
// fonction de comparaison pour qsort (appel dans join)
int comp (const void * a, const void * b)
{
    return *(int *)a - *(int *)b;
}
 
// ajoute à L les éléments de la boule de centre Tab1[k]
// qui n'y sont pas déjà et trie L par ordre croissant
// 31 à changer pour un paramètre
void join(unsigned int * L, unsigned int k)
{
    unsigned int i,j;
    i=0;
    while (L[i]) i++;
    for (j=0;j<31;j++)
    {
        if (!IsIn(Boules[k][j],L,longueur(L)))
            L[i++]=Boules[k][j];
    }
    qsort(L,longueur(L),sizeof(int),comp);
}
 
// recherche le minimum des MaxHole
// pour des indices situés dans T
// 2000 arbitraire doit être supérieur à la plus grande valeur de Tab1
unsigned int MinMaxHole(unsigned int *T,unsigned int tT )
{
    unsigned int i,j,m,a;
    for (i=0,m=3000;i<tT;i++)
    {
        for (j=0;j<taille;j++)
            Q[j]=Ligne[j];
        join(Q,T[i]);
        a=MaxHole(Q,longueur(Q));
        if (a<m)
            m=a;
    }
    return m;
}
 
// trouve le prochain indice à retenir
unsigned int Next()
{
    unsigned int M=AppMax();
    unsigned int m,i,j,s,a,b,tT;
    for (i=0,s=0;i<taille;i++)
    {
        if (Brings(i)==M)
            s++;
    }
    for (i=0;i<taille;i++)
        T[i]=0;
    tT=0;
    for (i=0,j=0;i<taille;i++)
    {
        if (Brings(i)==M)
        {
            T[j++]=i;
            tT++;
        }
    }
    m=MinMaxHole(T,tT);
    for (i=0;i<tT;i++)
    {
        for (j=0;j<taille;j++)
            Q[j]=Ligne[j];
        join(Q,T[i]);
        a=MaxHole(Q,longueur(Q));
        if (a==m)
            break;
    }
    b=T[i];
    return b;
}
 
void Step()
{
    unsigned int k=Next();
    join(Ligne,k);
    append(Tab1[k]);
}
 
// Voir la ligne
void MontreLigne()
{
    unsigned int i;
    for (i=0;i<taille;i++)
        printf("%04d-",Ligne[i]);
}
 
//fonction principale
int main()
{
    unsigned int i,j,k;
    init(6,11); // initialisation
    printf("%d\n", taille);// vérif
    for (i=0,k=1;i<taille;i++)
    {
        // réinitialisation de ligne
        for (j=0;j<taille;j++)
            Ligne[j]=0;
        // réinitialisation de Valid
        for (j=0;j<25;j++)
            Valid[j]=0;
        join(Ligne,i);
        append(Tab1[i]);
        for (j=0;j<22;j++)
            Step();
        if (Ligne[461])
        {
            printf("%d-%d\n",k++,i);
            MontreValid(11,6,i);
        }
     }
 
    return 0;
}

**zhao** · 25/08/2008, 02h10

Bonjour Zavonen et a tous :-)
Oui bien sur que cela m'intéresse :-)
quand aux limites oui mais HEUREUSEMENT car sinon quel intérêt ? et grâce a ses fameuses limites regarde depuis le début de mes posts sur ce problème ce que tu as réussi a faire ! , tu les as a chaque fois repoussé trouver de nouveaux algo , des programmes de plus en plus performant a mesure que la difficulté augmentait , bref vive les limites :-)
et ma conclusion sur ce point est, que ce n'est que dans la difficulté que nous progressons et certainement pas dans la facilité et je pense que cela est vrai dans tous les compartiments de la vie :-)
Bonnes Vacances .
@+ :-)

**Zavonen** · 25/08/2008, 07h11

Voici une version améliorée, l'algo étant inchangé. Il y a quelques optimisations, moins d'appels de fonctions pour une version presque deux fois plus rapide.
Oui dans le cas de 11, passer les ensembles réducteurs de 29 à 23, c'est loin d'être négligeable. En outre si on regarde les pourcentages de gain de 10 à 11 par rapport au glouton pur on est effectivement en droit d'attendre un résultat inférieur à 150 pour n=15.
Note bien que je ne suis absolument pas sûr qu'on puisse atteindre 15.
atteindre n=13 avec cet algo c'est possible j'en suis sûr.
Atteindre n=14 est possible aussi, si on ne cherche qu'UNEsolution (et non pas TOUTES comme à présent).
Mais 15 sera vraiment difficile, à moins d'avoir de la chance ou de remanier profondément cet algo.

Code C :

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
#include <stdio.h>
#include <stdlib.h>
 
unsigned int * Tab1,*Valid; // Les trois tableaux du traitement (algo Zhao)
unsigned int taille; // contiendra la taille de Tab1, Reste et Valid
unsigned char * numeros; // Contiendra tous les numéros possibles (1,2,3,...10,..)
unsigned int * Ligne; // la ligne à remplir
// 462 et 31 à remplacer dans le cas général
unsigned int  Boules[462][31]; // les 462 boules unité
unsigned int *Q; // purement utilitaire
unsigned int *T; // idem
 
//calcule les puissances de 2
unsigned int power2(unsigned int n)
{
    unsigned int result=1;
    int i;
    for (i=1;i<=n;i++)
        result *=2; // multiplier résultat par 2
    return result;
}
 
// calcule le nombre de chiffres de n en binaire
// une expérience récente sur le forum DVP a prouvé que les décalages ne sont pas plus rapides.
unsigned int nbcb(unsigned int n)
{
    unsigned int s=0; // totalisateur
    while (n) // tant que n est non nul
    {
        s+=n%2; // ajoute le chiffre des unités
        n/=2; // divise n par 2
    }
    return s;
}
 
// distance d'un point à un autre
// 6 est à changer pour un paramètre
unsigned int distance (unsigned int m, unsigned int n)
{
    return 6-nbcb(m&n);
}
 
 
// Calcule les coefficients Cp,n
unsigned int Cpn(unsigned int p, unsigned int n)
{
    unsigned int s=0; // totalisateur
    unsigned int i;
    for (i=0;i<power2(n);i++)
        if (nbcb(i)==p) s++;// Si p chiffres en base 2 on incrémente le compteur
    return s;
}
 
// initialise Tab1 Boules Valid numeros
// 31 à changer pour un paramètre
void init(unsigned int p,unsigned int n)
{
    unsigned int i,j,h;
    taille=Cpn(p,n); // nombre de combinaisons de p dans n
    //on remplit Tab1 à l'envers
    Ligne= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        Ligne[i]=0;
    Tab1= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0,j=0;i<power2(n);i++)
        if (nbcb(i)==p)
            Tab1[j++]=i;
    // Valid est initalisé rien qu'avec des zéros ce qui veut dire 'vide'
    Valid= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        Valid[i]=0;
    Q= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        Q[i]=0;
    T= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        T[i]=0;
    // C'est la liste des numéros possibles pour restituer les listes à partir des binaires
    numeros=(unsigned char *) malloc (n);
    for (i=0;i<n;i++)
        numeros[i]=(unsigned char)(i+1);
    for (i=0;i<taille;i++)
    {
        for (j=0,h=0;j<taille;j++)
 
        {
            if (distance(Tab1[i],Tab1[j])<=1)
                Boules[i][h++]=Tab1[j];
        }
    }
}
 
// ajouter un élément à Valid
// on le met au premier emplacement contenant une donnée nulle
void append(unsigned int n)
{
    unsigned int i=0;
    while (Valid[i])i++; // avancer jusqu'à trouver un zéro
    Valid[i]=n;
}
 
// Calcule la longueur d'un tableau (le nombre d'éléments non nuls)
unsigned int longueur (unsigned int * T)
{
    unsigned int i,s=0;
    for (i=0;i<taille;i++)
        if (T[i])s++;
        else
            break;
    return s;
}
 
// reconstitue une liste de numéros à partir d'un nombre binaire
char * restitue (unsigned int n,unsigned int p, unsigned int k)
{
    char * r=(char *) malloc(p); // pour p nombres tous <316
    unsigned int i,u,v;
    for (i=0;i<p;i++)
        r[i]=0;
    i=0;
    v=0;
    while (k) // tant que k n'est pas nul
    {
        u=k%2; // prendre le chiffre des unités de k
        if (u) // est il égal à 1 ?
            r[v++]=numeros[i]; // Si oui placer le numéro correspondant
        k=k/2; // diviser k par 2
        i++; // incrémenter i
    }
    return r;
}
 
// Liste tous les binaires de Valid sous forme de listes
void MontreValid(unsigned int n,unsigned int p, unsigned int r,unsigned int k)
{
    unsigned int i,j; // compteurs de boucles
    char * pc; // pour récupérer les listes
    printf("%d-%d\n",k,r);
    printf("Solution:\n");
    for (i=0;i<23;i++) // affichage des éléments de Valid
    {
        pc=restitue(n,p,Valid[i]); // allocation de mémoire et affectation
        for (j=0;j<p;j++) // affiche la liste reconstituée
            printf("%2d ",pc[j]);
        printf("\n");
        free(pc); // libération de la mémoire allouée
    }
}
 
// vérifie si l'entier k est dans la liste L
int IsIn(unsigned int k, unsigned int * L, unsigned int q)
{
    unsigned int i;
    for (i=0;i<q;i++)
        if (k==L[i])
            return 1;
    return 0;
}
 
//combien d'éléments nouveaux apporte la boule de centre
// Tab1[n] à Ligne
// 31 à changer pour un paramètre
unsigned int Brings(unsigned int n)
{
    unsigned int i,s;
    s=0;
    for (i=0;i<31;i++)
    {
        if (!IsIn(Boules[n][i],Ligne, longueur(Ligne)))
            s++;
    }
    return s;
}
 
// distance maximum entre deux entiers consécutifs
// de la liste triée L de longueur n
unsigned int MaxHole(unsigned int * L, unsigned int n)
{
    unsigned int m=0;
    unsigned int i;
    for (i=0; i<n-1;i++)
    {
        if ((L[i+1]-L[i])>m)
            m=L[i+1]-L[i];
    }
    return m;
}
 
// fonction de comparaison pour qsort (appel dans join)
int comp (const void * a, const void * b)
{
    return *(int *)a - *(int *)b;
}
 
// ajoute à L les éléments de la boule de centre Tab1[k]
// qui n'y sont pas déjà et trie L par ordre croissant
// 31 à changer pour un paramètre
void join(unsigned int * L, unsigned int k)
{
    unsigned int i,j;
    i=0;
    while (L[i]) i++;
    for (j=0;j<31;j++)
    {
        if (!IsIn(Boules[k][j],L,longueur(L)))
            L[i++]=Boules[k][j];
    }
    qsort(L,longueur(L),sizeof(int),comp);
}
 
// trouve le prochain indice à retenir
unsigned int Next()
{
    unsigned int M,m,i,j,s,a,b,tT;
    M=0;
    for (i=0;i<taille;i++)
    {
        a=Brings(i);
        if (a>M)
            M=a;
    }
 
    for (i=0,s=0;i<taille;i++)
    {
        if (Brings(i)==M)
            s++;
    }
    for (i=0;i<taille;i++)
        T[i]=0;
    tT=0;
    for (i=0,j=0;i<taille;i++)
    {
        if (Brings(i)==M)
        {
            T[j++]=i;
            tT++;
        }
    }
    for (i=0,m=3000,b=T[0];i<tT;i++)
    {
        for (j=0;j<taille;j++)
            Q[j]=Ligne[j];
        join(Q,T[i]);
        a=MaxHole(Q,longueur(Q));
        if (a<m)
        {
            m=a;
            b=T[i];
        }
    }
    return b;
}
 
void Step()
{
    unsigned int k=Next();
    join(Ligne,k);
    append(Tab1[k]);
}
 
//fonction principale
// 462 à remplacer par paramètre
int main()
{
    unsigned int i,j,k;
    init(6,11); // initialisation
    for (i=0,k=1;i<taille;i++)
    {
        // réinitialisation de ligne
        for (j=0;j<taille;j++)
            Ligne[j]=0;
        // réinitialisation de Valid
        for (j=0;j<25;j++)
            Valid[j]=0;
        join(Ligne,i);
        append(Tab1[i]);
        for (j=0;j<22;j++)
            Step();
        if (Ligne[461])
        {
            MontreValid(11,6,i,k++);
        }
    }
    return 0;
}

**Zavonen** · 25/08/2008, 08h28

Pour n=12 je trouve une solution à 42 combinaisons
On peut peut être faire mieux.
1-53
Solution:
2 3 4 5 8 9
1 2 6 8 9 10
1 3 4 5 6 10
1 2 3 4 7 12
1 2 5 6 7 11
3 4 6 7 8 11
1 5 7 8 9 12
5 6 8 10 11 12
1 3 7 9 10 11
2 3 6 9 11 12
4 6 7 9 10 12
2 4 7 8 10 11
2 3 5 7 10 12
1 4 5 9 11 12
1 2 3 5 8 11
1 2 4 6 8 12
3 4 8 9 10 12
2 4 5 6 7 9
1 4 5 7 8 10
2 7 8 9 11 12
1 4 6 8 9 11
3 4 5 7 11 12
3 5 6 7 8 9
2 3 4 6 10 11
1 2 5 9 10 12
1 6 7 10 11 12
1 3 8 10 11 12
5 6 7 9 10 11
1 2 3 4 7 9
2 4 5 6 8 12
2 3 6 7 8 10
3 5 8 9 10 11
1 3 5 6 9 12
1 2 4 5 10 11
3 4 5 6 9 10
2 5 7 8 9 11
1 2 4 6 7 12
1 2 3 4 8 12
1 2 3 4 6 12
1 2 3 7 8 12
1 2 4 7 8 11
1 2 4 9 10 11

Process returned 0 (0x0) execution time : 295.500 s
Press any key to continue.

Code C :

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
#include <stdio.h>
#include <stdlib.h>
 
unsigned int * Tab1,*Valid; // Les trois tableaux du traitement (algo Zhao)
unsigned int taille; // contiendra la taille de Tab1, Reste et Valid
unsigned char * numeros; // Contiendra tous les numéros possibles (1,2,3,...10,..)
unsigned int * Ligne; // la ligne à remplir
// 924 et 37 à remplacer dans le cas général
unsigned int  Boules[924][37]; // les 924 boules unité
unsigned int *Q; // purement utilitaire
unsigned int *T; // idem
 
//calcule les puissances de 2
unsigned int power2(unsigned int n)
{
    unsigned int result=1;
    int i;
    for (i=1;i<=n;i++)
        result *=2; // multiplier résultat par 2
    return result;
}
 
// calcule le nombre de chiffres de n en binaire
// une expérience récente sur le forum DVP a prouvé que les décalages ne sont pas plus rapides.
unsigned int nbcb(unsigned int n)
{
    unsigned int s=0; // totalisateur
    while (n) // tant que n est non nul
    {
        s+=n%2; // ajoute le chiffre des unités
        n/=2; // divise n par 2
    }
    return s;
}
 
// distance d'un point à un autre
// 6 est à changer pour un paramètre
unsigned int distance (unsigned int m, unsigned int n)
{
    return 6-nbcb(m&n);
}
 
 
// Calcule les coefficients Cp,n
unsigned int Cpn(unsigned int p, unsigned int n)
{
    unsigned int s=0; // totalisateur
    unsigned int i;
    for (i=0;i<power2(n);i++)
        if (nbcb(i)==p) s++;// Si p chiffres en base 2 on incrémente le compteur
    return s;
}
 
// initialise Tab1 Boules Valid numeros
// 37 à changer pour un paramètre
void init(unsigned int p,unsigned int n)
{
    unsigned int i,j,h;
    taille=Cpn(p,n); // nombre de combinaisons de p dans n
    Ligne= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        Ligne[i]=0;
    Tab1= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0,j=0;i<power2(n);i++)
        if (nbcb(i)==p)
            Tab1[j++]=i;
    // Valid est initalisé rien qu'avec des zéros ce qui veut dire 'vide'
    Valid= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        Valid[i]=0;
    Q= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        Q[i]=0;
    T= (unsigned int *) malloc (taille*sizeof(unsigned int));
    for (i=0;i<taille;i++)
        T[i]=0;
    // C'est la liste des numéros possibles pour restituer les listes à partir des binaires
    numeros=(unsigned char *) malloc (n);
    for (i=0;i<n;i++)
        numeros[i]=(unsigned char)(i+1);
    for (i=0;i<taille;i++)
    {
        for (j=0,h=0;j<taille;j++)
 
        {
            if (distance(Tab1[i],Tab1[j])<=1)
                Boules[i][h++]=Tab1[j];
        }
    }
}
 
// ajouter un élément à Valid
// on le met au premier emplacement contenant une donnée nulle
void append(unsigned int n)
{
    unsigned int i=0;
    while (Valid[i])i++; // avancer jusqu'à trouver un zéro
    Valid[i]=n;
}
 
// Calcule la longueur d'un tableau (le nombre d'éléments non nuls)
unsigned int longueur (unsigned int * T)
{
    unsigned int i,s=0;
    for (i=0;i<taille;i++)
        if (T[i])s++;
        else
            break;
    return s;
}
 
// reconstitue une liste de numéros à partir d'un nombre binaire
char * restitue (unsigned int n,unsigned int p, unsigned int k)
{
    char * r=(char *) malloc(p); // pour p nombres tous <376
    unsigned int i,u,v;
    for (i=0;i<p;i++)
        r[i]=0;
    i=0;
    v=0;
    while (k) // tant que k n'est pas nul
    {
        u=k%2; // prendre le chiffre des unités de k
        if (u) // est il égal à 1 ?
            r[v++]=numeros[i]; // Si oui placer le numéro correspondant
        k=k/2; // diviser k par 2
        i++; // incrémenter i
    }
    return r;
}
 
// Liste tous les binaires de Valid sous forme de listes
void MontreValid(unsigned int n,unsigned int p, unsigned int r,unsigned int k,unsigned int nl)
{
    unsigned int i,j; // compteurs de boucles
    char * pc; // pour récupérer les listes
    printf("%d-%d\n",k,r);
    printf("Solution:\n");
    for (i=0;i<nl;i++) // affichage des éléments de Valid
    {
        pc=restitue(n,p,Valid[i]); // allocation de mémoire et affectation
        for (j=0;j<p;j++) // affiche la liste reconstituée
            printf("%2d ",pc[j]);
        printf("\n");
        free(pc); // libération de la mémoire allouée
    }
}
 
// vérifie si l'entier k est dans la liste L
int IsIn(unsigned int k, unsigned int * L, unsigned int q)
{
    unsigned int i;
    for (i=0;i<q;i++)
        if (k==L[i])
            return 1;
    return 0;
}
 
//combien d'éléments nouveaux apporte la boule de centre
// Tab1[n] à Ligne
// 37 à changer pour un paramètre
unsigned int Brings(unsigned int n)
{
    unsigned int i,s;
    s=0;
    for (i=0;i<37;i++)
    {
        if (!IsIn(Boules[n][i],Ligne, longueur(Ligne)))
            s++;
    }
    return s;
}
 
// distance maximum entre deux entiers consécutifs
// de la liste triée L de longueur n
unsigned int MaxHole(unsigned int * L, unsigned int n)
{
    unsigned int m=0;
    unsigned int i;
    for (i=0; i<n-1;i++)
    {
        if ((L[i+1]-L[i])>m)
            m=L[i+1]-L[i];
    }
    return m;
}
 
// fonction de comparaison pour qsort (appel dans join)
int comp (const void * a, const void * b)
{
    return *(int *)a - *(int *)b;
}
 
// ajoute à L les éléments de la boule de centre Tab1[k]
// qui n'y sont pas déjà et trie L par ordre croissant
// 37 à changer pour un paramètre
void join(unsigned int * L, unsigned int k)
{
    unsigned int i,j;
    i=0;
    while (L[i]) i++;
    for (j=0;j<37;j++)
    {
        if (!IsIn(Boules[k][j],L,longueur(L)))
            L[i++]=Boules[k][j];
    }
    qsort(L,longueur(L),sizeof(int),comp);
}
 
// trouve le prochain indice à retenir
unsigned int Next()
{
    unsigned int M,m,i,j,s,a,b,tT;
    M=0;
    for (i=0;i<taille;i++)
    {
        a=Brings(i);
        if (a>M)
            M=a;
    }
 
    for (i=0,s=0;i<taille;i++)
    {
        if (Brings(i)==M)
            s++;
    }
    for (i=0;i<taille;i++)
        T[i]=0;
    tT=0;
    for (i=0,j=0;i<taille;i++)
    {
        if (Brings(i)==M)
        {
            T[j++]=i;
            tT++;
        }
    }
    for (i=0,m=33000,b=T[0];i<tT;i++)
    {
        for (j=0;j<taille;j++)
            Q[j]=Ligne[j];
        join(Q,T[i]);
        a=MaxHole(Q,longueur(Q));
        if (a<m)
        {
            m=a;
            b=T[i];
        }
    }
    return b;
}
 
void Step()
{
    unsigned int k=Next();
    join(Ligne,k);
    append(Tab1[k]);
}
 
//fonction principale
// 924 à remplacer par paramètre
int main()
{
    unsigned int i,j,k;
    init(6,12); // initialisation
    for (i=53,k=1;i<taille;i++)
    {
        // réinitialisation de ligne
        for (j=0;j<taille;j++)
            Ligne[j]=0;
        // réinitialisation de Valid
        for (j=0;j<50;j++)
            Valid[j]=0;
        join(Ligne,i);
        append(Tab1[i]);
        printf("%d\n",i);
        for (j=0;j<41;j++)
        {
            Step();
        }
        if (Ligne[923])
        {
            MontreValid(12,6,i,k++,42);
            return 0;
        }
    }
    return 0;
}

**zhao** · 25/08/2008, 08h29

Oui Zavonen les progrès réalisé sur ce problème sont vraiment impressionnant je vais faire les tests pour voire ce que cela donne pour n=15 bof je m'inquiète pas on trouveras ( enfin surtout toi ;-) ) et même au-delà de 15 si on le veut ,comme dit dans mon post précédent a chaque fois tu trouve autre chose ,tu améliore , plus performant , plus rapide bref je me sens un peu petit mais c'est pas grave j'apprends énormément de choses et je ne suis pas le seul regarde le nombre d'affichage de ce problème plus de 1180 c'est te dire que je suis a mon avis loin d'être le seul a me régaler :-)
PS) il est loin d'être lent comme tu dit ton programme pour info avec mon portable HP 8710w il met ....15 segondes pour trouver une solution pour 12 6/5 :-)
@+ :-)

**Jean-Marc.Bourguet** · 25/08/2008, 09h03

Dommage que je n'ai pas le temps de regarder cela en detail. Quelques petites optimisations qui m'ont sautees aux yeux.

Code :

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

1
2
3
4
5
6
7
8
9
10
unsigned int nbcb(unsigned int n)
{
    unsigned int s=0; // totalisateur
    while (n) // tant que n est non nul
    {
        s+=n%2; // ajoute le chiffre des unités
        n/=2; // divise n par 2
    }
    return s;
}

Certains compilateurs fournissent une fonction intrinseque (__builtin_popcount pour gcc par exemple). Hors cela, la version la plus rapide consiste a utiliser un tableau -- mais il faut aussi tenir compte du temps de remplissage de ce tableau. Voir http://graphics.stanford.edu/~seander/bithacks.html pour quelques autres techniques.

Code :

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

1
2
3
4
5
6
7
8
unsigned int power2(unsigned int n)
{
    unsigned int result=1;
    int i;
    for (i=1;i<=n;i++)
        result *=2; // multiplier résultat par 2
    return result;
}

Peut se remplacer avantageusement par

Code :

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

1
2
3
4
unsigned int power2(unsigned int n)
{
    return 1 << n;
}

Code :

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

1
2
3
4
5
6
7
8
unsigned int Cpn(unsigned int p, unsigned int n)
{
    unsigned int s=0; // totalisateur
    unsigned int i;
    for (i=0;i<power2(n);i++)
        if (nbcb(i)==p) s++;// Si p chiffres en base 2 on incrémente le compteur
    return s;
}

Desole, mais la j'ai rigole.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
unsigned Cpn(unsigned p, unsigned n)
{
   assert(p<=n);
   unsigned result = 1;
   unsigned i;
   for (i = 0; i < p; ++i) {
      result *= (n-i);
      result /= (i+1);
   }
   return result;
}

**Zavonen** · 25/08/2008, 09h53

Tes remarques sont sans doute toutes justifiées mais ce n'est pas là qu'on peut gagner du temps.
Ces fonctions que tu suggères de remplacer ne sont appelées que pour la phase d'initialisation, c'est à dire du point de vue du temps absolument rien.
J'ai par contre trouvé des optimisations intéressantes du point de vue de l'algo lui-même, je publierai plus tard car c'est encore en gestation.
PS: Ton calcul de Cpn est dangereux. Il peut faire intervenir des coefficients non entiers, des arrondis, etc....Qu'est ce qui te garantit la divisibilité par i+1 à chaque étape?
Le mien n'est pas bon mais pour l'occase je m'en fiche.
Pour voir qqch de bien voir par exemple mon cours sur Théorie des ensembles coefficients Cpn calcul avec un générateur de python au moyen de la récurrence de Pascal (aucun risque de débordement ni d'arrondi) dans la mesure du faisable bien sûr.

**zhao** · 25/08/2008, 10h15

de toute façon ce n'est pas le C qui nous intéresse en premier le C n'est qu'un outil non ce qui est remarquable c'est les ALGOS qui sont tous plus performant les uns que les autres le C vient après ,pour concrétiser le(s) concept(s) de Zavonen a un certain moment le C prendras beaucoup plus d'importance pour optimiser le temps de traitements , moi ce que j'admire c'est la puissance des algos de Zavonen qui permette a chaque fois de reculer les limites :-)

Systèmes Réducteur nouvel algo

Mathématiques

Discussions similaires

Partager

Partager