:- use_module(library(lists)).
:- write('Hasznalat:   gen(L,K)').


gen(L,K):- rendez(L,Rend),
	   egytol(M),
           findall(Felosztas,feloszt(Rend,K,M,[],Felosztas),MFeloszt),
	   MFeloszt\=[],
	   !,
	   tell('out.pl'),
	   kiir(MFeloszt),
	   told.

egytol(1).
egytol(M):- egytol(M1), M is M1+1.

kiir([]).
kiir([L|Marad]):- write(L), nl, kiir(Marad).


% A korabbi, reszlista/3 helyett reszlista/4-et hasznalunk, mely annyival tud
% tobbet, hogy akkor sem generalja le ketszer ugyanazt a halmazt, ha vannak
% ismetlodo elemek. Az utolso parameterben ugyanis nyomon kovetjuk, mi volt az
% eddigi legnagyobb elem, amit kihagytunk - es kisebbet tobbet mar nem is rakunk
% a listaba.
reszlista(L,Resz,Marad):- reszlista(L,Resz,Marad,0).
reszlista([],[],[],_).
reszlista([E|L],[E|Resz],Marad,X):- E>X, reszlista(L,Resz,Marad,X).
reszlista([E|L],Resz,[E|Marad],_):- reszlista(L,Resz,Marad,E).


jolista([E],Ossz):- Ossz>=E.
jolista([E|L],Ossz1):- Ossz2 is Ossz1-E, jolista(L,Ossz2).


% A feloszt/4-et ugy modositjuk, hogy csak olyan feloszatasokat generaljunk 
% le, melyekben a listak lexikografikusan nem csokkeno sorozozatot alkotnak.
% Erre mar a generalas soran ugyelunk, igy eleg arra ugyelni, hogy mindig az
% utolsolent legeneralt listanal lexikografikusan nem kisebbet generaljunk le.
feloszt([],_,0,_,[]).
feloszt(L,K,M,Utolso,[Uj|Felosztas]):-
                        M>0,
                        reszlista(L,Uj,Marad),
                        jolista(Uj,K),
			kisebb(Utolso,Uj),
			M1 is M-1,
			feloszt(Marad,K,M1,Uj,Felosztas).


kisebb([],_).
kisebb([E1|_],[E2|_]):- E1<E2.
kisebb([E|L1],[E|L2]):- kisebb(L1,L2).

%---------------------------------------------------------------------------

rendez([],[]).
rendez([E|L],Rend):- szetoszt(E,L,L1,L2), 
                     rendez(L1,Rend1), 
		     rendez(L2,Rend2),
		     append(Rend1,[E|Rend2],Rend).

szetoszt(_,[],[],[]).
szetoszt(E,[X|L],S1,S2):- szetoszt(E,L,L1,L2), 
                          (E>X -> S1=[X|L1], S2=L2; S1=L1, S2=[X|L2]).
