prolog.pl

first(X,[X|T]).
%one_before_last(X,A) - A is one before last of of X
one_before_last([A,_],A).
one_before_last([_|X], A):- one_before_last(X,A).

%elem(A,X) A is an element of X
elem(A,[A|_]).
elem(B,[_|X]):-elem(B,X).

%concat(X,Y,Z): Z is concatenation of X and Y
concat([],Y,Y).
concat([A|X],Y,[A|Z]):- concat(X,Y,Z).

%sorted(X) checks if X is sorted array
sorted(X):- not((concat(_,[A,B|_],X), A>B)).

%perm(X,Y): Y is permutation of X
perm([],[]).
perm([A|X],Z):- perm(X,Y), insert(A,Y,Z).

perm2([],[]).
perm2([A|X],Z):-  insert(A,Y,Z),perm2(X,Y).

%insert(A,X,Y) - A is inserted into X and the result is Y
insert(A,X,[A|X]).
insert(A,[B|X],[B|Y]):-insert(A,X,Y).

%remove(A,X,Y): A is removed from Y and results in X
remove(A,X,[A|X]).
remove(B,[A|X],[A|Y]):- remove(B,X,Y).

%subset(X,L) - X is a subset of L
subset([],L).
subset([H|T],L):-remove(H,M,L), subset(T,M).

%sort1(X,Y) Y is sorted X
sort1(X,Y):- perm(X,Y), sorted(Y).

%sum(X,A): A is a sum of the elements of X
sum([],0).
sum([A|X],N):- sum(X,K), N is A + K.

%fibodo(N,A,B):- A and B are fibonacci numbers both lower than N
fibodo(N,0,1):- 0 =<N, 1 =< N.
fibodo(N,B,C):- fibodo(N,A,B),C is A + B,A=<N,B=<N,C =<N.

rev([],[]).
rev([A|X],Z):-rev(X,Y),concat(Y,[A],Z).

%btw(N,A,B):- N is an integer between A and B
btw(A,A,B):- A =< B.
btw(N,A,B):- A < B, A1 is A + 1, btw(N,A1,B).

%p(N,K):- given interger N  generates in K all exact divisors which are in the form 2^m + l^3 for m and l in N
p(N,K) :- divisors(N,K), btw(M,0,K), btw(L,0,K), K  is 2 ** M + L ** 3.

%divisor(A,B) -  B is divisor of A
divisors(A,B):-btw(B,1,A), 0 is (A mod B).

%nat(X) generator for natural numbers
nat(0).
nat(X) :- nat(Y), X is Y + 1.

%q(N) N is a natural number in the from 2^m + l^3
q(N):- nat(K), btw(M,1,K), btw(L,1,K),N  is 2 ** M + L ** 3.

%int(N) generator of integers
int(N):-nat(L), (N=L; N is -L).



%%Graphs
%[[1,2,3,4,5],[[1,2],[2,3],[3,4],[4,5]]]
%fromto(X,A,B,G):- X is a path from A to B in the graph G
fromto([C],C,C,[V,E]):- elem(C,V).
fromto([A|X],A,B,[V,E]):- elem([A,C],E),fromto(X,C,B,[V,E]).


fromto2(X,A,B,[V,E]):-not((concat(_,[V1,V2|_],X),not((elem([V1,V2],E))))),X = [A|_], concat(_,[B],X).

simplepath([C],C,C,[V,E]):- elem(C,V).
simplepath([A|X],A,B,[V,E]):- elem([A,C],E),simplepath(X,C,B,[V,E]),not((elem(A,X))).

hamilton([V,E],X):-perm(V,X), simplepath(X,A,B,[V,E])