%%%%% Séance 7 : solution, avec commentaires explicatifs

%%% 1 - Sous-ensembles

% solution 1 : fonction simple qui retourne toutes les sous-listes mais pas dans l ordre souhaité 
sous_ensembles1([],[[]]) :- !.  % la seule sous-liste [] est []
sous_ensembles1([X|XS],P) :- 
    sous_ensembles1(XS,S),  % S = la liste des sous-listes de XS
    findall([X|P1], member(P1,S), PS),  % PS = la liste des [X|P1] pour tout P1 dans S
    append(S,PS,P).  % P est la concaténation de S et PS
    
% solution demandée : fonction qui retourne les sous-listes en ordre radix (par longueur, puis dans ordre alphabétique si même longueur)
% se : fonction auxiliaire définie plus bas
% ligne 17 : on prend toutes les sous-listes P2 de L de longueur N, pour N allant de 0 à N0 (inclus), et on les met dans P
sous_ensembles([],[[]]) :- !.
sous_ensembles(L,P) :- 
    length(L,N0),  % N0 = longueur de L
    findall(P2, (between(0,N0,N), se(L,P1,N), member(P2,P1)), P). 
    
% fonction auxiliaire se qui retourne toutes les sous-listes de longueur N
se(_,[[]],0) :- !.  % la seule sous-liste de longueur 0 est []
se(L,[],N) :- length(L,N0), N0 < N, !.  % aucune sous-liste si N est plus grand que la longueur de L
se(L,P,1) :- findall([X], member(X,L), P), !.  % les sous-listes de longueur 1 sont les [X] pour les éléments X de L
se([X|XS],P,N) :- 
    N1 is N-1,
    se(XS,S,N1),  % S = liste des sous-listes de XS de longueur N-1
    findall([X|P1], member(P1,S), PS),  % PS = la liste des [X|P1] pour tout P1 dans S
    se(XS,PSN,N),  % PSN = liste des sous-listes de XS de longueur N
    append(PS,PSN,P).  % P est la concaténation de PS et PSN
    
  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  
%%% 2 - Coupures

%% 2.1 - Optimisation

signe(N, plus) :- N > 0, !.
signe(0, zero) :- !.
signe(N, moins) :- N < 0.

%% 2.2 - Séparation

separer(L, P, N) :-
    findall(X, (member(X,L), X < 0), N),
    findall(X, (member(X,L), X > 0), P).
  
  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
%%% 3 - Minimum d une liste de structures

% note : 0-[3,2] et 4-[1] sont des paires cle-valeurs comme dans la documentation : https://www.swi-prolog.org/pldoc/man?section=pairs
% le prédicat keysort/2 permet de trier la liste selon les cles. 

minimum(L, M) :- keysort(L,S), S = [M|_].  % M est le premier élément de la liste triée
  
  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    
%%% 4 - Énumération de chemins

% À préparer pour le TP2 !
