Discussion :

[gorgonite]

Salut,


j'ai cette "fonction" :

Code :

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

1
2
3
4
compatible(?N,?L1,?L2)
% on vérifie que les différences de N avec les éléments contenus dans L1 ne figurent pas dans L2
% sachant que N >= max L1
% et que L2 est l'ensemble des différences entre les éléments de L1

je réussis dans les cas suivants :
- les trois arguments sont définis
- N est une variable
- L2 est une variable


mais j'ai des problèmes pour retrouver L1 à partir de N et L2

j'ai essayé cela :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
compatible_arg2(_,[_],[]).
compatible_arg2(_,L1,[N|L]) :-
	head(L1,A),
	random(0,3000,A),
	!,
	queue(L1,Q),
	head(Q,B),
	plus(N,B,A),
	!,
	compatible(_,Q,L),
	compatible(_,[A|Q],[N|L]).

mais je me retrouve avec trop d'éléments dans L1


si quelqu'un a une solution, ou peux me guider un peu... je suis preneur

[Trap D]

Dans l'absolu, il n'y a pas une infinité de solutions pour L1 ?

Quand tu écris :

Code :

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

1
2
3
4
5
6
compatible_arg2(_,L1,[N|L]) :-
	head(L1,A),
	%random(0,3000,A),
	%!,
	queue(L1,Q),
	...

Tu veux dire que L1 peut s'écrire [A | Q] c'est ça ?

[gorgonite]

Dans l'absolu, il n'y a pas une infinité de solutions pour L1 ?

ben si... d'où le random

Tu veux dire que L1 peut s'écrire [A | Q] c'est ça ?

oui...

[pcaboche]

ben si... d'où le random

Oui... mais non !

En Prolog, une infinité de solutions, c'est une infinité de solutions, c'est pas une solution prise au hasard.

Ton problème m'a l'air vraiment complexe et tiré par les cheveux.

[gorgonite]

En Prolog, une infinité de solutions, c'est une infinité de solutions, c'est pas une solution prise au hasard.

mais sinon il veut pas instancier...

Ton problème m'a l'air vraiment complexe et tiré par les cheveux.

c'est un tout petit morceau d'un projet... pour valider un cours très dur dans un très bon master

[Amon-Râ]

Si il y a une infinité de solution, pourquoi ne pas plutôt interdire les cas qui ne marche pas (et qui sont en quantité finie) ?

Code :

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

1
2
3
 
compatible(+N,-L1,+L2) :- calc_all_differences(N,L1,L2),
                                    !,fail.

où la fonction "calc_all_differences/3" est celle définie dans ton précédant topic : http://www.developpez.net/forums/sho...d.php?t=216433

[gorgonite]

Si il y a une infinité de solution, pourquoi ne pas plutôt interdire les cas qui ne marche pas (et qui sont en quantité finie) ?

Code :

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

1
2
3
 
compatible(+N,-L1,+L2) :- calc_all_differences(N,L1,L2),
                                    !,fail.

où la fonction "calc_all_differences/3" est celle définie dans ton précédant topic : http://www.developpez.net/forums/sho...d.php?t=216433

certes, mais on finit par tomber sur un cas non géré, car dans le calcul on tombe avec deux arguments non instanciés

[billynirvana]

Pourrais-tu être plus explicite pour l'énoncé de ton problème. Je crois que tu cherche à trouver le complémentaire de N dans L1, et mettre la solution dans L2. Je me trompe?

Si c'est le cas, moi je le fais comme suit:

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
complementaire(nil, e2, nil)->;
complementaire(x.e1, e2, x.e3)->
	hors_de(x, e2)!
	complementaire(e1, e2, e3);
complementaire(x.e1, e2, e3)->
	complementaire(e1, e2, e3);
 
hors_de(x, nil)->;
hors_de(x, y.l)->
	dif(x, y)
	hors_de(x, l);
 
/*
> complementaire(1.2.3.nil, 1.4.3.nil, e);
{e=2.nil}
*/

Cdlt

[gorgonite]

@billynirvana: nan pas du tout


mon problème actuel est le suivant

Code :

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

1
2
3
4
compatible(?N,?L1,?L2)
% on vérifie que les différences de N avec les éléments contenus dans L1 ne figurent pas dans L2
% sachant que N >= max L1
% et que L2 est l'ensemble des différences entre les éléments de L1

et je veux pouvoir inverser L1... en ayant bien sûr des valeurs instanciées dans N et L2

[pcaboche]

Code :

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

1
2
3
% on vérifie que les différences de N avec les éléments contenus dans L1 ne figurent pas dans L2
% sachant que N >= max L1
% et que L2 est l'ensemble des différences entre les éléments de L1

Il va falloir traduire chacune des règles énoncées :

% on vérifie que les différences de N avec les éléments contenus dans L1 ne figurent pas dans L2

Dans ce cas, il nous faut un prédicat pour faire la liste des nombres interdits, quelque chose du genre :

Code :

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

1
2
3
4
5
prohibited(N, L2, Prohibited) :-
  maplist( m(N), L2, Prohibited).
 
m(A,B,C) :-
  C is A-B.

Comme ça, à la génération, on fera :

Code :

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

\+memberchk(I, Prohibited),

% sachant que N >= max L1

Dans ce cas, à la la génération, on aura:

Code :

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

between(0, N, I),

et donc, avec ce qui est écrit plus haut :

Code :

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

1
2
between(0, N, I),
\+memberchk(I, Prohibited),

% et que L2 est l'ensemble des différences entre les éléments de L1

Cela implique deux choses :

- Que pour chaque élément I généré, on a bien les différences entre I et les éléments précédemment générés qui se trouvent toutes dans L2 :

Code :

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

1
2
3
4
5
6
7
8
9
checkDiffs(I, Gen, Diffs) :-
  member(E, Gen),
  D1 is E-I,
  D2 is I-E,
  \+ (memberchk(D1, Diffs) , memberchk(D2, Diffs)),
  !,
  fail.
 
checkDiffs(_, _, _).

- Comme L2 est l'ensemble des différences entre les éléments de L1, si la liste généré vérifie cette propriété, alors c'est une solution. Il faut donc un prédicat pour vérifier cette propriété :

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
checkAllDiffs(L, Diffs) :-
  checkAllDiffs(Diffs, L, L, L).
 
 
checkAllDiffs([], [], _, _) :- !.
 
checkAllDiffs(Diffs, [H1|Q1], [H2|Q2], L2) :- 
  !,
  D1 is H1-H2,
  D2 is H2-H1,
  delete(Diffs, D1, Tdiff),
  delete(Tdiff, D2, NDiffs),
  checkAllDiffs(NDiffs, [H1|Q1], Q2, L2).
 
 
checkAllDiffs(Diffs, [_|Q1], [], L2) :- 
  checkAllDiffs(Diffs, Q1, L2, L2).

J'espère que ça aide, parce que je ne suis pas sûr d'avoir tout compris au problème (il aurait fallu quelques exemples).

Sur ce, bonne chance !

[billynirvana]

Je n'ai toujours rien compris, mais pour inverser une liste, moi je fais comme ça:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
%%%%%%%%%%%%%%%%%%%%
%- Inverse une liste l1 et met le resultat dans l2 -%
 
inverser(l1, l2)->
	inv(l1, nil, l2);
 
inv(nil, l0, l0)->;	%- Passage final de parametres -%
inv(x.l1, l0, l2)->
	inv(l1, x.l0, l2);
 
/*
> inverser(1.2.3.4.5.nil, l);
{l=5.4.3.2.1.nil}
*/

[gorgonite]

J'espère que ça aide, parce que je ne suis pas sûr d'avoir tout compris au problème (il aurait fallu quelques exemples).

Ben en fait, non...

voilà les exemples :

Code :

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

1
2
3
4
5
6
7
8
9
10
compatible(3,[1,0],[1]).
Yes
 
 
compatible(N,[1,0],[1]).
N = 3
 
 
compatible(3,[1,0],L).
L = [1]

jusque là j'y arrive... mais je veux aussi

Code :

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

1
2
3
4
compatible(3,L,[1]).
L = [1,0]
L = [7,8]
...

pour chaque argument non instancié je passe par une méthode ad-hoc (compatible_argN), et donc j'ai un problème sur compatible_arg2

[pcaboche]

jusque là j'y arrive... mais je veux aussi

Code :

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

1
2
3
4
compatible(3,L,[1]).
 L = [1,0]
 L = [7,8]
 ...

L=[7,8] ne respecte pas la condition N >= max L1.

Ben en fait, non...

Ah ouais ? T'es sûr ?

Alors regarde ça:

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
compatible(N, L1, L2) :-
  nonvar(N),
  var(L1),
  nonvar(L2),
  compatible_arg2(N, L1, L2).
 
 
 
compatible_arg2(N,L1,L2) :-
  maplist( m(N), L2, Prohibited),
  genList(N, [], L2, Prohibited, L1).
 
 
m(A,B,C) :-
  C is A-B.
 
 
 
 
genList(_, Gen, Diffs, _, Gen) :-
  checkAllDiffs(Gen, Diffs).
 
 
 
genList(Max, Gen, Diffs, Prohibited, R) :-
   between(0, Max, I),
   \+memberchk(I, Prohibited),
 
   checkDiffs(I, Gen, Diffs),
   genList(Max, [I|Gen], Diffs, Prohibited, R).
 
 
 
checkDiffs(I, Gen, Diffs) :-
  member(E, Gen),
  D1 is abs(E-I),
  \+ memberchk(D1, Diffs),
  !,
  fail.
 
 
checkDiffs(_, _, _).
 
 
 
 
checkAllDiffs(L, Diffs) :-
  checkAllDiffs(Diffs, L, L, L).
 
 
checkAllDiffs([], [], _, _) :- !.
 
checkAllDiffs(Diffs, [H1|Q1], [H2|Q2], L2) :- 
  !,
  D1 is H1-H2,
  D2 is H2-H1,
  delete(Diffs, D1, Tdiff),
  delete(Tdiff, D2, NDiffs),
  checkAllDiffs(NDiffs, [H1|Q1], Q2, L2).
 
 
checkAllDiffs(Diffs, [_|Q1], [], L2) :- 
  checkAllDiffs(Diffs, Q1, L2, L2).

Tests :

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
1 ?- compatible(5, L, [1]).
 
L = [1, 0] ;
 
L = [0, 1] ;
 
L = [2, 1] ;
 
L = [1, 2] ;
 
L = [3, 2] ;
 
L = [2, 3] ;
 
No
2 ?- compatible(5, L, [1,2]).
 
L = [2, 1, 0] ;
 
L = [1, 2, 0] ;
 
L = [2, 0, 1] ;
 
L = [0, 2, 1] ;
 
L = [1, 0, 2] ;
 
L = [0, 1, 2] ;
 
No

Après, si tu ne veux que les résultats triés, tu modifies juste un peu :

Code :

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

1
2
3
4
compatible_arg2(N,L1,L2) :-
  maplist( m(N), L2, Prohibited),
  genList(N, [], L2, Prohibited, L1),
  msort(L1, L1).

[gorgonite]

L=[7,8] ne respecte pas la condition N >= max L1.

en effet... faudra que je relise mieux la prochaine fois

Ah ouais ? T'es sûr ?

je fais jeter un coup d'oeil là-dessus

ps: quand le projet sera officiellement clos, à savoir en milieu de semaine prochaine, je pourrais vous mettre le sujet et ma "solution"... si jamais la rubrique manque de sources ou autres


[EDIT]ça marche... mais semblerait que mon analyse était fausse, car même avec tous les arguments inversibles, il ne reconstruit rien