home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / lang / prolog / 2100 < prev    next >
Encoding:
Internet Message Format  |  1992-11-18  |  2.1 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!doc.ic.ac.uk!uknet!edcastle!aiai!ken
  2. From: ken@aiai.ed.ac.uk (Ken Johnson)
  3. Newsgroups: comp.lang.prolog
  4. Subject: Permutations and combinations
  5. Message-ID: <7931@skye.ed.ac.uk>
  6. Date: 18 Nov 92 12:15:13 GMT
  7. Followup-To: comp.lang.prolog
  8. Organization: William's Wonderful Wonky Widget Warehouse
  9. Lines: 58
  10.  
  11.  
  12.  
  13. Since getting permutations and combinations of N elements from a list is
  14. a fairly common homework question,  I thought I'd let the group in on the
  15. secret before they started to ask.
  16.  
  17.       Exercise for Teachers' Pets Everywhere: write code for
  18.       permute(-N, +L, +P) and combine(-N, +L, +P), e.g.  combine(N,
  19.       [u, v, w, x, y, z], [z, u, x]) should succeed and instantiate N
  20.       to 3.
  21.  
  22.  
  23. % Permutations and combinations
  24. % Ken Johnson,  18 November 1992
  25. % 
  26. % You may copy and distribute this code freely,  but please acknowledge the
  27. % source,  even if you only say `Actually I copied this code from Ken
  28. % Johnson although I'm quite sure anybody with half a brain could have
  29. % written it.' If you sell copies of my code at a profit,  I want a share. 
  30.  
  31. % permute(+N, +L, -C)
  32. % instantiates C to a permutation of N elements of the list L
  33.  
  34. permute(0,_,[]).
  35.  
  36. permute(N,List,[X|More]) :-
  37.     N > 0,
  38.     member(X,List,Rest),
  39.     N1 is N - 1,
  40.     permute(N1,Rest,More).
  41.  
  42.  
  43. member(H,[H|T],T).        % the usual member/3
  44.  
  45. member(X,[H|T],[H|U]) :-
  46.     member(X,T,U).
  47.  
  48. % combine(+N,+L,-C)
  49. % instantiates C to a combination of N elements of the list L
  50.  
  51. combine(0,_,[]).
  52.  
  53. combine(N,List,[X|More]) :-
  54.     N > 0,
  55.     combine_1(X,List,Rest),
  56.     N1 is N - 1,
  57.     combine(N1,Rest,More).
  58.  
  59. combine_1(X,[X|T],T).        % return an element of the list (X)
  60.                 % and the list (T) of those elements
  61. combine_1(X,[_|T],U) :-        % that follow X in the list
  62.     combine_1(X,T,U).
  63.  
  64. -- 
  65.                                    //// Ken Johnson, A I Applications Institute
  66. CNS server brain not responding   ////       80 South Bridge, EDINBURGH EH1 1HN
  67. ... still trying                 ////                  E-mail ken@aiai.ed.ac.uk
  68.                                 ////       Phone 031-650 2756  Fax 031-650 6513
  69.