%%%
% aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
%%%


%%%
% vynasob(+A,+B,-M) true, pokud M je matice vznikla vynasobenim matic A*B
%%%

%nejprve provedeme transpozici B, pak se vse odehrava po jednotlivych radcich.
vynasob(A,B,M):-transpozice(B,BTransp),vynasob_radky(A,BTransp,M).

%%%
% vynasob_radky(+A,+BTransp,-M) true, pokud M je matice vznikla vynasobenim matic A*(B^T) 
%%%

% konec rekurze
vynasob_radky([],_,[]).

% prvnim radkem matice A vynasobime vsechny radky BTransp (sloupce B), vysledkem je radek MRadek. rekurzivne pocitame to same pro zbyvajici radky matice A. 
vynasob_radky([ARadek|AZbytek],BTransp,[MRadek|MZbytek]):-vynasob_radek(ARadek,BTransp,MRadek),vynasob_radky(AZbytek,BTransp,MZbytek).

%%%
% vynasob_radek(+ARadek,+BTransp,-MRadek) vynasobi BTransp radkem ARadek a vysledek bude MRadek.
%%%

% konec rekurze
vynasob_radek(_,[],[]).

% provede skalarni soucin ARadek a BSloupec, ulozi do MPrvniPrvek a rekurzivne spocita pro zbyvajici sloupce BTransp 
vynasob_radek(ARadek,[BSloupec|BZbytek],[MPrvniPrvek|MZbytekRadku]):-skalarni_soucin(ARadek,BSloupec,MPrvniPrvek),vynasob_radek(ARadek,BZbytek,MZbytekRadku).

%%%
% skalarni_soucin(+Radek,+Sloupec,-Vysledek)
%%%

% pouzijeme pomocny 4-arni predikat
% konec rekurze.
skalarni_soucin([],[],X,X). 

% vynasobime prvni prvky, pricteme k mezivysledku a rekurzivne pocitame pro zbyvajici prvky. 
skalarni_soucin([Radek1|RadekZbytek],[Sloupec1|SloupecZbytek],Mezivysledek,Vysledek):-NovyMezivysledek is Mezivysledek+Radek1*Sloupec1,skalarni_soucin(RadekZbytek,SloupecZbytek,NovyMezivysledek,Vysledek).

% namapujeme na ternarni predikat
skalarni_soucin(Radek,Sloupec,Vysledek):-skalarni_soucin(Radek,Sloupec,0,Vysledek).

%%%
% transpozice(+Matice,-TransponovanaMatice)
%%%

% pouzijeme pomocny ternarni predikat
% konec rekurze
transpozice([[]|_],X,X).

% z Matice vybereme prvni sloupec, pridame ho na zacatek Akumulatoru a rekurzivne zpracujeme zbytek matice.
transpozice(Matice,TransponovanaMatice,Akumulator):-vyber_sloupec(Matice,PrvniSloupec,ZbytekMatice),transpozice(ZbytekMatice,TransponovanaMatice,[PrvniSloupec|Akumulator]).

% namapovani na ternarni predikat (a jeste potrebujeme otocit radky)
transpozice(Matice,TransponovanaMatice):-transpozice(Matice,Mezivysledek,[]),obrat(Mezivysledek,TransponovanaMatice).

%%%
% vyber_sloupec(+Matice,-PrvniSloupec,-ZbytekMatice)
%%%

% konec rekurze
vyber_sloupec([],[],[]).

% popravi prvni radek vstupni matice, hlavu prida na zacatek prvniho sloupce a telo na zacatek zbytkove matice. pak rekurzivne pocita pro zbytek.
vyber_sloupec([MaticePrvniRadek|MaticeZbytek],[PrvniPrvekPrvnihoSloupce|ZbytekPrvnihoSloupce],[ZbytekMaticePrvniRadek|ZbytekMaticeZbytek]):-poprav(MaticePrvniRadek,PrvniPrvekPrvnihoSloupce,ZbytekMaticePrvniRadek),vyber_sloupec(MaticeZbytek,ZbytekPrvnihoSloupce,ZbytekMaticeZbytek).

%%%
% poprav(?Seznam,?Hlava,?Telo). provede popravu seznamu (oddeli hlavu od tela)
%%%

poprav([Hlava|Telo],Hlava,Telo).

%%%
% obrat(+Matice,-ObracenaMatice) obrati poradi radku v matici
%%%

% pouzijeme pomocny ternarni predikat
obrat([],X,X).

obrat([MaticePrvniRadek|MaticeZbytek],Vysledek,Akumulator):-obrat(MaticeZbytek,Vysledek,[MaticePrvniRadek|Akumulator]).

obrat(Matice,ObracenaMatice):-obrat(Matice,ObracenaMatice,[]).

%%%
% bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
%%%

nextperm(Perm,NextPerm):-klesajici_suffix(Perm,Zacatek,Klesajici),posledni(Zacatek,X),nejblizsi_vyssi(X,Klesajici,N),vyber(Klesajici,N,Konec),conc(Zacatek,[N],C1),conc(C1,[X],C2),conc(C2,Konec,NextPerm).

% klesajici_suffix
% TENTO PREDIKÁT JE CHYBNİ
klesajici_suffix([P|PermR],[P,K|Konec]):- P > K, klesajici_suffix(PermR,[K|Konec]).
klesajici_suffix([P|PermR],[K|Konec]):- P =< K, klesajici_suffix(PermR,[K|Konec]).
klesajici_suffix([P|_],[P]).
klesajici_suffix(Perm,Zacatek,Konec):-otoc(Perm,PermR),klesajici_suffix(PermR,Konec),delka_seznamu(Konec,DelkaKonce),delka_seznamu(Perm,DelkaCelku),DelkaZacatku is DelkaCelku-DelkaKonce,zacatek(Perm,DelkaZacatku,Zacatek).

% posledni
posledni(X,[X]).
posledni(X,[_|L]):-posledni(X,L).

% nejblizsi_vyssi
nejblizsi_vyssi(Hodnota,Seznam,NejblizsiVyssi):-NejblizsiVyssi is Hodnota+1,prvek(NejblizsiVyssi,Seznam).
nejblizsi_vyssi(Hodnota,Seznam,NejblizsiVyssi):-Dalsi is Hodnota+1,nejblizsi_vyssi(Dalsi,Seznam,NejblizsiVyssi).

% vyber
vyber(X,[X|A],A).
vyber(X,[Y|A],[Y|Z]):-vyber(X,A,Z).

% conc
conc([],S,S).
conc([Y|S],T,[Y|U]):-conc(S,T,U).

% otoc
revconc([],V,V).
revconc([H|S],T,A):-revconc(S,[H|T],A).
otoc(S,L):-revconc(S,[],L).

% prvek
prvek(X,[X|_]).
prvek(X,[_|L]):-prvek(X,L).

% delka_seznamu
delka_seznamu([],0).
delka_seznamu([_|T],Delka):-delka_seznamu(T,DelkaKratsiho),Delka is DelkaKratsiho+1.

% zacatek
zacatek([X|T],Delka,[X|VystupZbytek]):- Delka>0,DelkaKratsi is Delka-1,zacatek(T,DelkaKratsi,VystupZbytek).
zacatek(_,0,[]).

%%%
% cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
%%%

% c1
pocet_vetsich_prvku([],_,0).
pocet_vetsich_prvku([H|T],N,Pocet):-H>N,pocet_vetsich_prvku(T,N,NovyPocet),Pocet is NovyPocet+1.
pocet_vetsich_prvku([H|T],N,Pocet):-H=<N,pocet_vetsich_prvku(T,N,Pocet).

perminv([],_,[]).
perminv([PermH|PermT],Aku,[InvH|InvT]):-pocet_vetsich_prvku(Aku,PermH,InvH),perminv(PermT,[PermH|Aku],InvT).
perminv([],[]).
perminv(Perm,Inv):-perminv(Perm,[],Inv).

% c2
na_pozici(0,[H|_],H).
na_pozici(Pozice,[_|T],Hodnota):-NovaPozice is Pozice-1,na_pozici(NovaPozice,T,Hodnota).

posloupnost(X,X,[X]).
posloupnost(Od,Do,[Od|Zbytek]):-OdZbytek is Od+1,posloupnost(OdZbytek,Do,Zbytek).

invperm([],_,X,X).
invperm([InvH|InvT],Buffer,Aku,Perm):-delka_seznamu(Buffer,DelkaBufferu),!,InvH<DelkaBufferu,na_pozici(InvH,Buffer,X),vyber(X,Buffer,NovyBuffer),invperm(InvT,NovyBuffer,[X|Aku],Perm).
invperm(Inv,Perm):-otoc(Inv,InvR),delka_seznamu(Inv,DelkaInv),posloupnost(1,DelkaInv,Posloupnost),otoc(Posloupnost,PosloupnostR),!,invperm(InvR,PosloupnostR,[],Perm).