/* De Brujin */

comp :- consult('DeBrujin.pl').

:- consult('lib.pl').

:- nl,write('***********************************************************'),nl,nl,
   write('Dieses Programm generiert "De Brujin - Zyklen" und zwar'),nl,
   write('fuer k=2 bis etwa k=10 (fuer groessere Werte von k muss'),nl,
   write('man entsprechend lange warten).'),nl,nl,
   write('Um einen De Brujin-Zyklus "Cycle" fuer z.B. k=7 zu gene-,'),nl,
   write('rieren gibt man "de_brujin(7,Cycle)." ein.'),nl,nl,
   write('Wenn man mit "de_brujin(k,Cycle)." schon einen De Brujin'),nl,
   write('Zyklus bzgl. k  generiert hat, so kann man mit '),nl,
   write('"count(de_brujin(k),N)." testen, ob die Anzahl der vom'),nl,
   write('Programm gefundenen Zyklen stimmt (mit akzeptablem Zeit-'),nl,
   write('aufwand geht dies nur bis k=5).'),nl,nl,
   write('***********************************************************'),nl,nl.          

created(0).
create(M):- created(M),!.
create(M):- nit(created(M)),createV(M),createE(M),asserta(created(M)).

createV(M):- makelist_of_M(List,[],M),
             assertz(v(List,M)),fail.
createV(_).

makelist_of_M(List,List,0):- !.
makelist_of_M(List,Stack,M):- MM is M-1,
                              in_list(A,[0,1]),
                              NewStack=[A|Stack],
                              makelist_of_M(List,NewStack,MM).

createE(M):- v(L1,M),v(L2,M),
             L1=[_|Rest1],
             append_list(Rest1,_,L2),
             assertz(e(L1,L2,M)),fail.
createE(_).

null([0],1):- !.
null(Null,K):- M is K-1, null(NullM,M), Null=[0|NullM].

teste(N):- integer(N), N>1.
teste(N):- nit(integer(N)),
           nl,write('sorry, das kann ich nicht :-('),nl,fail.
teste(N):- integer(N), N<2,
           nl,write('sorry, das kann ich nicht :-('),nl,fail.

add_to_Elist_N(List,1,List,_).
add_to_Elist_N(List,N,Cycle,M):- List=[[V1,_]|_],
                                 e(V2,V1,M), nit(in_list([V2,V1],List)),
                                 NewList=[[V2,V1]|List],
                                 NN is N-1,
                                 add_to_Elist_N(NewList,NN,Cycle,M).

de_brujin(N,Cycle):- M is N-1,
                     teste(M),
                     create(M),
                     null(Null,M), power(2,N,P),
                     add_to_Elist_N([[Null,Null]],P,C,M),
                     cycle(C,Cycle),nl.

write_de_brujin(N):- M is N-1,
                     teste(M),
                     create(M),
                     null(Null,M), power(2,N,P),
                     add_to_Elist_N([[Null,Null]],P,C,M),
                     cycle(C,Cycle),write(Cycle),nl.

de_brujin(N):- M is N-1,
               null(Null,M), power(2,N,P),
               add_to_Elist_N([[Null,Null]],P,_,M).

cycle(L,C):- L=[[V1,_]|Rest], V1=[A|_], cycle(Rest,C,[A]).
cycle(L,C,C1):- L=[[V1,_]|Rest], V1=[A|_], append_list(C1,[A],C2), 
                cycle(Rest,C,C2).
cycle([],C,C).

/* ************************************************************* */ 

/* Das zweistellige Praedikat "count(Q,N)" ist genau dann wahr, 
   wenn Q auf N Arten erfuellt werden kann                       */

count(Q,N):- nonvar(Q), asserta(kaunterQ(0)), count_Q(Q,N).
count_Q(Q,_):- Q, 
               kaunterQ(M), MM is M+1,
               retract(kaunterQ(M)), asserta(kaunterQ(MM)),
               schreibe_jedes(MM,50),
               fail.
count_Q(_,N):- kaunterQ(N),retract(kaunterQ(N)),!.

/* Im Praedikat "counter" kommt das Praedikat "schreibe_jedes"
   vor, das jede x-te Erfuellbarkeit von Q auf den Bildschirm
   schreibt, d.h. auf den Bildschirm wird jeweils ein Vielfaches 
   der Zahl x geschrieben                                             */

schreibe_jedes(M,J):- K is (M/J), integer(K), write(M),nl.
schreibe_jedes(_,_):- !.

/* ************************************************************* */ 

/* End of De Brujin */