home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 5 / DATAFILE_PDCD5.iso / utilities / b / binprolog / !BinPro330 / progs / allperms < prev    next >
Encoding:
Text File  |  1994-02-11  |  1.4 KB  |  62 lines
  1. all_permutations([],[[]]).
  2. all_permutations([X|Xs],Perms2):-
  3.            all_permutations(Xs,Perms1),
  4.         extend_permutations(Perms1,X,Perms2).
  5.  
  6. extend_permutations([],_,[]).
  7. extend_permutations([Perm|Perms1],X,[[X|Perm]|Perms3]):-
  8.     extend_permutations(Perms1,X,Perms2),
  9.     insert_item(Perm,X,[],Perms2,Perms3).
  10.  
  11. insert_item([],_,_,Perms,Perms).
  12. insert_item([Y|Ys],X,Acc,Perms1,[Zs|Perms2]):-
  13.            reverse_and_append(Acc,[Y,X|Ys],Zs),
  14.         insert_item(Ys,X,[Y|Acc],Perms1,Perms2).
  15.  
  16. reverse_and_append([],Acc,Acc).
  17. reverse_and_append([X|Xs],Acc,Zs):-
  18.        reverse_and_append(Xs,[X|Acc],Zs).
  19.  
  20. nats(Max,Max,[Max]):-!.
  21. nats(Curr,Max,[Curr|Ns]):-
  22.     Curr<Max,
  23.     Curr1 is Curr+1,
  24.     nats(Curr1,Max,Ns).
  25.  
  26. perm([],[]).
  27. perm([X|Xs],Zs):-
  28.     perm(Xs,Ys),
  29.     insert(X,Ys,Zs).
  30.  
  31. insert(X,Ys,[X|Ys]).
  32. insert(X,[Y|Ys],[Y|Zs]):-
  33.     insert(X,Ys,Zs).
  34.  
  35. g0(N):-nats(1,N,Ns),perm(Ns,_),fail.
  36. g0(_).
  37.  
  38. g1(N,Ps):-nats(1,N,Ns),all_permutations(Ns,Ps).
  39. g2(N,Ps):-nats(1,N,Ns),findall(P,perm(Ns,P),Ps).
  40.  
  41. test(Mes,LocalMes,X):-
  42.     statistics(global_stack,[H1,_]),
  43.     statistics(runtime,_),
  44.     X,
  45.     statistics(runtime,[_,T]),
  46.     statistics(global_stack,[H2,_]),H is H2-H1,
  47.     write([Mes,LocalMes]=[time=T,heap=H]),nl.
  48.  
  49. t0(Mes):-test(Mes,nondet,g0(8)).
  50.  
  51. t1(Mes):-test(Mes,determ,g1(8,_)).
  52.  
  53. t2(Mes):-test(Mes,with_findall,g2(8,_)).
  54.  
  55. go(Mes):-
  56.   write('execute with -h20000 option'),nl,
  57.   t0(Mes),fail;t1(Mes),fail;t2(Mes),fail.
  58.  
  59. go:-go('BMARK_allperms').
  60.  
  61. p:-[allperms].
  62.