Système de contraintes

**arnonono** · 10/03/2024, 17h16

Bonjour

J'essaye de générer 6 vecteurs de 0 et 1 de taille 2N vérifiant des contraintes écrites avec l'opération XOR, l'ordre lexicographique et le produit symplectique (proche du produit scalaire) défini par:

si u = ( u1, ... , uN, u_{N+1} , ... , u_{2N} ) et v = ( v1, ... , vN, v_{N+1} , ... , v_{2N} ) alors
sigma(u,v)= u1*vN + u2*v_{N+1} + ... + u_{N}*v_{2N} + u_N*v_1 + ... + u_{2N}*v_N

Il y a plus ou moins 15 contraintes et je sais qu'il y a plusieurs solutions.

Mon problème est que Prolog me donne .false dès que je mets 3 ou 4 contraintes... il y a donc un problème dans mon code et je suis totalement bloqué.

Voici le code:

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
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
 
% Appel automatique à CLP(fd)
:- use_module(library(clpfd)).
 
 
% ordre lexicographique
leq([0],[1]).
 
leq([X|C1],[X|C2]):-
	leq(C1,C2).
 
leq([0|_],[1|_]).
 
% liste de listes de taille N
lengthliste([X],N):-
	length(X,N).
 
lengthliste([X|L],N):-
	length(X,N),
	lengthliste(L,N).
 
 
 
% xor
 
xor(0,0,0).
xor(1,0,1).
xor(0,1,1).
xor(1,1,0).
 
xorListe([X1],[X2],[X]):-
	!,xor(X1,X2,X).
 
xorListe([X1|L1],[X2|L2],[X|L]):-
	xor(X1,X2,X),
	xorListe(L1,L2,L),
	!.
 
 
% on calcule sigma(u,v) en faisant le produit scalaire entre u1,...,uN,uN+1,..U2N et vN+1,...,v2N,v1,...,vN
 
% on coupe L en un morceau de taille N et un autre
split(L,0,[],L).
 
split([X|Xs],N,[X|Ys],Zs) :- N1 is N - 1, split(Xs,N1,Ys,Zs).
 
 
% produit scalaire
ps([X1],[Y1],Res):-
	Res is X1*Y1.
 
ps([X1|L1],[X2|L2],Res):-
	ps(L1,L2,Res2),!,
	Res is xor(X1*X2, Res2).
 
% produit symplectique
sigma(O1,O2,N,Res):-
	split(O2,N,Moitie1,Moitie2),
	append(Moitie2,Moitie1,NewO2),
	ps(O1,NewO2,Res),!.
 
 
 
 
 
 
contraintes(O1,O2,O3,O4,O5,C, N):-
	NN is 2*N,
	length(O1,NN),
	length(O2,NN),
	length(O3,NN),
	length(O4,NN),
	length(O5,NN),
	length(C,NN),
	O1 ins {0,1},
	O2 ins {0,1},
	O3 ins {0,1},
	O4 ins {0,1},
	O5 ins {0,1},
	C ins {0,1},
	xorListeListe([O1,O2,O3,O4],O5),
	xorListe(C,O1,D1),
	xorListe(C,O2,D2),
	xorListe(C,O3,D3),
	xorListe(D3,O5,D4),
	xorListe(D3,O4,D5),
	xorListe(D2,O4,D6),
	xorListe(D2,O5,D7),
	xorListe(D1,O4,D8),
	xorListe(D1,O5,D9),
	leq(O1, C),
	leq(O1, O2),
	leq(O2, O3),
	leq(O3, O4),
	leq(O4, O5),
	leq(O1,D1),
	leq(O2,D2),
	leq(O2,D3),
	leq(O1,D4),
	leq(O1,D5),
	leq(O1,D6),
	leq(O1,D7),
	leq(O2,D8),
	leq(O2,D9),
	sigma(O1,O2,N,1),
	sigma(O1,O3,N,1),
	sigma(O1,O4,N,1),
	sigma(O1,O5,N,1),
	sigma(O2,O3,N,1),
	sigma(O2,O4,N,1),
	sigma(O2,O5,N,1),
	sigma(O3,O4,N,1),
	sigma(O3,O5,N,1),
	sigma(O4,O5,N,1),
	sigma(O4,C,N,1),
	sigma(O1,C,N,0),
	sigma(O2,C,N,0),
	sigma(O3,C,N,0),
	labeling([],[O1,O2,O3,O4,O5,C]).  # utile ?

Merci et bon dimanche

**arnonono** · 10/03/2024, 18h52

Le code suivant me donne l'unique solution pour N=2, j'ai enlevé les cut et j'ai du commenté l'instruction labeling, je ne sais pas pourquoi.

Pour N=3 le programme tourne depuis de longues minutes mais je n'ai toujours aucun résultat...

Je suis preneur de toute remarque:

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
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
 
% Appel automatique à CLP(fd)
:- use_module(library(clpfd)).
 
 
% ordre lexicographique
leq([0],[1]).
 
leq([X|C1],[X|C2]):-
	leq(C1,C2).
 
leq([0|_],[1|_]).
 
% liste de listes de taille N
lengthliste([X],N):-
	length(X,N).
 
lengthliste([X|L],N):-
	length(X,N),
	lengthliste(L,N).
 
 
 
% xor
 
xor(0,0,0).
xor(1,0,1).
xor(0,1,1).
xor(1,1,0).
 
xorListe([X1],[X2],[X]):-
	xor(X1,X2,X).
 
xorListe([X1|L1],[X2|L2],[X|L]):-
	xor(X1,X2,X),
	xorListe(L1,L2,L),
	xorListe(L1, L2, L).
 
xorListeListe([X1,X2],L):-
		xorListe(X1,X2,L).
 
xorListeListe([X1|X],L):-
		xorListeListe(X,LL),
		xorListe(X1,LL,L).
 
 
% on calcule sigma(u,v) en faisant le produit scalaire entre u1,...,uN,uN+1,..U2N et vN+1,...,v2N,v1,...,vN
 
% on coupe L en un morceau de taille N et un autre
split(L,0,[],L).
 
split([X|Xs],N,[X|Ys],Zs) :- N1 is N - 1, split(Xs,N1,Ys,Zs).
 
 
% produit scalaire
ps([X1],[Y1],Res):-
	Res is X1*Y1.
 
ps([X1|L1],[X2|L2],Res):-
	ps(L1,L2,Res2),!,
	Res is xor(X1*X2, Res2).
 
% produit symplectique
sigma(O1,O2,N,Res):-
	split(O2,N,Moitie1,Moitie2),
	append(Moitie2,Moitie1,NewO2),
	ps(O1,NewO2,Res),!.
 
 
 
 
 
 
contraintes(O1,O2,O3,O4,O5,C, N):-
	NN is 2*N,
	length(O1,NN),
	length(O2,NN),
	length(O3,NN),
	length(O4,NN),
	length(O5,NN),
	length(C,NN),
	O1 ins {0,1},
	O2 ins {0,1},
	O3 ins {0,1},
	O4 ins {0,1},
	O5 ins {0,1},
	C ins {0,1},
	xorListeListe([O1,O2,O3,O4],O5),
	xorListe(C,O1,D1),
	xorListe(C,O2,D2),
	xorListe(C,O3,D3),
	xorListe(D3,O5,D4),
	xorListe(D3,O4,D5),
	xorListe(D2,O4,D6),
	xorListe(D2,O5,D7),
	xorListe(D1,O4,D8),
	xorListe(D1,O5,D9),
	leq(O1, C),
	leq(O1, O2),
	leq(O2, O3),
	leq(O3, O4),
	leq(O4, O5),
	leq(O1,D1),
	leq(O2,D2),
	leq(O2,D3),
	leq(O1,D4),
	leq(O1,D5),
	leq(O1,D6),
	leq(O1,D7),
	leq(O2,D8),
	leq(O2,D9),
	sigma(O1,O2,N,1),
	sigma(O1,O3,N,1),
	sigma(O1,O4,N,1),
	sigma(O1,O5,N,1),
	sigma(O2,O3,N,1),
	sigma(O2,O4,N,1),
	sigma(O2,O5,N,1),
	sigma(O3,O4,N,1),
	sigma(O3,O5,N,1),
	sigma(O4,O5,N,1),
	sigma(O4,C,N,1),
	sigma(O1,C,N,0),
	sigma(O2,C,N,0),
	sigma(O3,C,N,0).
	%labeling([],[O1,O2,O3,O4,O5,C]).

**Trap D** · 15/03/2024, 11h45

Bonjour
Je ne connais absolument rien au produit symplectique. Je me suis contenté de regarder le code Prolog.
Je l'ai un peu modifié, mais c'est à la marge. La seule modif importante est dans

Code :

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

1
2
3
4
xorListe([X1|L1],[X2|L2],[X|L]):-
	xor(X1,X2,X),
	xorListe(L1,L2,L).
	%xorListe(L1, L2, L).

J'ai commenté le deuxième xorListe mais c'est peut-être une erreur de ma part.
J'ai obtenu ce résultat :

Code :

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

1
2
3
4
5
6
7
8
9
?- time(contraintes(O1,O2,O3,O4,O5,C,3)).
 
% 18,078,043,024 inferences, 1737.219 CPU in 1742.618 seconds (100% CPU, 10406314 Lips)
O1 = [0, 0, 0, 0, 1, 1],
O2 = [0, 0, 1, 0, 0, 0],
O3 = [0, 0, 1, 0, 0, 1],
O4 = [0, 1, 0, 0, 0, 1],
O5 = [0, 1, 0, 0, 1, 1],
C = [0, 0, 0, 1, 1, 0] .

J'ai fait deux versions, une avec clpfd et l'autre sans:

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
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
 
% ordre lexicographique
%leq([0],[1]).
leq([0|_],[1|_]).
 
 
leq([X|C1],[X|C2]):-
	leq(C1,C2).
 
 
 
% xor
xor(0,0,0).
xor(1,0,1).
xor(0,1,1).
xor(1,1,0).
 
xorListe([X1],[X2],[X]):-
	xor(X1,X2,X).
 
xorListe([X1|L1],[X2|L2],[X|L]):-
	xor(X1,X2,X),
	xorListe(L1,L2,L).
        %xorListe(L1,L2,L).
 
xorListeListe([X1,X2],L):-
		xorListe(X1,X2,L).
 
xorListeListe([X1|X],L):-
		xorListeListe(X,LL),
		xorListe(X1,LL,L).
 
 
% on calcule sigma(u,v) en faisant le produit scalaire entre u1,...,uN,uN+1,..U2N et vN+1,...,v2N,v1,...,vN
 
% on coupe L en un morceau de taille N et un autre
%split(L,0,[],L).
 
%split([X|Xs],N,[X|Ys],Zs) :- N1 is N - 1, split(Xs,N1,Ys,Zs).
split(L,N,L1,L2):-
    length(L1,N),
    append(L1,L2,L).
 
 
% produit scalaire
 
ps([X1],[Y1],Res):-
	Res is X1*Y1.
 
ps([X1|L1],[X2|L2],Res):-
	ps(L1,L2,Res2),!,
	Res is xor(X1*X2, Res2).
 
% produit symplectique
sigma(O1,O2,N,Res):-
	split(O2,N,Moitie1,Moitie2),
	append(Moitie2,Moitie1,NewO2),
	ps(O1,NewO2,Res).
 
init(N, L) :-
	NN is 2*N,
	length(L,NN),
        forall(member(X,L), member(X,[0,1])).
 
 
contraintes(O1,O2,O3,O4,O5,C, N):-
/*
	NN is 2*N,
	length(O1,NN),
	length(O2,NN),
	length(O3,NN),
	length(O4,NN),
	length(O5,NN),
	length(C,NN),
	O1 ins {0,1},
	O2 ins {0,1},
	O3 ins {0,1},
	O4 ins {0,1},
	O5 ins {0,1},
	C ins {0,1},
*/
        maplist(init(N), [O1,O2,O3,O4,O5,C]),
	xorListeListe([O1,O2,O3,O4],O5),
	xorListe(C,O1,D1),
	xorListe(C,O2,D2),
	xorListe(C,O3,D3),
	xorListe(D3,O5,D4),
	xorListe(D3,O4,D5),
	xorListe(D2,O4,D6),
	xorListe(D2,O5,D7),
	xorListe(D1,O4,D8),
	xorListe(D1,O5,D9),
	leq(O1, C),
	leq(O1, O2),
	leq(O2, O3),
	leq(O3, O4),
	leq(O4, O5),
	leq(O1,D1),
	leq(O2,D2),
	leq(O2,D3),
	leq(O1,D4),
	leq(O1,D5),
	leq(O1,D6),
	leq(O1,D7),
	leq(O2,D8),
	leq(O2,D9),
	sigma(O1,O2,N,1),
	sigma(O1,O3,N,1),
	sigma(O1,O4,N,1),
	sigma(O1,O5,N,1),
	sigma(O2,O3,N,1),
	sigma(O2,O4,N,1),
	sigma(O2,O5,N,1),
	sigma(O3,O4,N,1),
	sigma(O3,O5,N,1),
	sigma(O4,O5,N,1),
	sigma(O4,C,N,1),
	sigma(O1,C,N,0),
	sigma(O2,C,N,0),
	sigma(O3,C,N,0).

la seconde avec clpfd, (il ne faut jamais utiliser les cut avec clpfd).

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
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
 
% Appel automatique à CLP(fd)
:- use_module(library(clpfd)).
 
 
% ordre lexicographique
leq([0],[1]).
 
leq([X|C1],[X|C2]):-
	leq(C1,C2).
 
leq([0|_],[1|_]).
 
% liste de listes de taille N
lengthliste([X],N):-
	length(X,N).
 
lengthliste([X|L],N):-
	length(X,N),
	lengthliste(L,N).
 
 
 
% xor
 
xor(0,0,0).
xor(1,0,1).
xor(0,1,1).
xor(1,1,0).
 
xorListe([X1],[X2],[X]):-
	xor(X1,X2,X).
 
xorListe([X1|L1],[X2|L2],[X|L]):-
	xor(X1,X2,X),
	xorListe(L1,L2,L).
	%xorListe(L1, L2, L).
 
xorListeListe([X1,X2],L):-
		xorListe(X1,X2,L).
 
xorListeListe([X1|X],L):-
		xorListeListe(X,LL),
		xorListe(X1,LL,L).
 
 
% on calcule sigma(u,v) en faisant le produit scalaire entre u1,...,uN,uN+1,..U2N et vN+1,...,v2N,v1,...,vN
 
% on coupe L en un morceau de taille N et un autre
split(L,N,L1,L2):-
    length(L1,N),
    append(L1,L2,L).
 
 
% produit scalaire
ps([X1],[Y1],Res):-
	Res is X1*Y1.
 
ps([X1|L1],[X2|L2],Res):-
	ps(L1,L2,Res2),
	Res is xor(X1*X2, Res2).
 
% produit symplectique
sigma(O1,O2,N,Res):-
	split(O2,N,Moitie1,Moitie2),
	append(Moitie2,Moitie1,NewO2),
	ps(O1,NewO2,Res).
 
 
 
init(N, L) :-
	NN is 2*N,
	length(L,NN),
        L ins {0,1}.
 
 
contraintes(O1,O2,O3,O4,O5,C, N):-
        maplist(init(N), [O1,O2,O3,O4,O5,C]),
	xorListeListe([O1,O2,O3,O4],O5),
	xorListe(C,O1,D1),
	xorListe(C,O2,D2),
	xorListe(C,O3,D3),
	xorListe(D3,O5,D4),
	xorListe(D3,O4,D5),
	xorListe(D2,O4,D6),
	xorListe(D2,O5,D7),
	xorListe(D1,O4,D8),
	xorListe(D1,O5,D9),
	leq(O1, C),
	leq(O1, O2),
	leq(O2, O3),
	leq(O3, O4),
	leq(O4, O5),
	leq(O1,D1),
	leq(O2,D2),
	leq(O2,D3),
	leq(O1,D4),
	leq(O1,D5),
	leq(O1,D6),
	leq(O1,D7),
	leq(O2,D8),
	leq(O2,D9),
	sigma(O1,O2,N,1),
	sigma(O1,O3,N,1),
	sigma(O1,O4,N,1),
	sigma(O1,O5,N,1),
	sigma(O2,O3,N,1),
	sigma(O2,O4,N,1),
	sigma(O2,O5,N,1),
	sigma(O3,O4,N,1),
	sigma(O3,O5,N,1),
	sigma(O4,O5,N,1),
	sigma(O4,C,N,1),
	sigma(O1,C,N,0),
	sigma(O2,C,N,0),
	sigma(O3,C,N,0),
	labeling([ff],C).

[/EDIT]
Quelques résultats pour 3

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
?- time(contraintes(O1,O2,O3,O4,O5,C,3)).
% 18,078,043,024 inferences, 1739.141 CPU in 1740.283 seconds (100% CPU, 10394814 Lips)
O1 = [0, 0, 0, 0, 1, 1],
O2 = [0, 0, 1, 0, 0, 0],
O3 = [0, 0, 1, 0, 0, 1],
O4 = [0, 1, 0, 0, 0, 1],
O5 = [0, 1, 0, 0, 1, 1],
C = [0, 0, 0, 1, 1, 0] ;
% 6,633 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
O1 = [0, 0, 0, 0, 1, 1],
O2 = [0, 0, 1, 0, 0, 0],
O3 = [0, 0, 1, 0, 0, 1],
O4 = [0, 1, 0, 0, 0, 1],
O5 = [0, 1, 0, 0, 1, 1],
C = [1, 0, 0, 0, 1, 0] ;
% 1,792 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
O1 = [0, 0, 0, 0, 1, 1],
O2 = [0, 0, 1, 0, 0, 0],
O3 = [0, 0, 1, 0, 0, 1],
O4 = [0, 1, 0, 0, 0, 1],
O5 = [0, 1, 0, 0, 1, 1],
C = [1, 0, 0, 1, 1, 0] ;
% 54,681 inferences, 0.000 CPU in 0.005 seconds (0% CPU, Infinite Lips)
O1 = [0, 0, 0, 1, 1, 1],
O2 = [0, 0, 1, 0, 0, 0],
O3 = [0, 0, 1, 0, 0, 1],
O4 = [0, 1, 0, 0, 0, 1],
O5 = [0, 1, 0, 1, 1, 1],
C = [1, 1, 0, 0, 1, 0] ;
% 1,788 inferences, 0.000 CPU in 0.000 seconds (0% CPU, Infinite Lips)
O1 = [0, 0, 0, 1, 1, 1],
O2 = [0, 0, 1, 0, 0, 0],
O3 = [0, 0, 1, 0, 0, 1],
O4 = [0, 1, 0, 0, 0, 1],
O5 = [0, 1, 0, 1, 1, 1],
C = [1, 1, 0, 1, 1, 0] ;
% 63,539,678 inferences, 5.703 CPU in 5.707 seconds (100% CPU, 11141204 Lips)
O1 = [0, 0, 0, 0, 1, 1],
O2 = [0, 0, 1, 0, 1, 0],
O3 = [0, 0, 1, 0, 1, 1],
O4 = [0, 1, 0, 0, 0, 0],
O5 = [0, 1, 0, 0, 1, 0],
C = [0, 0, 0, 1, 1, 0]

Sont-ils corrects ?

Système de contraintes

Prolog

Discussions similaires

Partager

Partager