🚀 go-pugleaf

Since getting permutations and combinations of N elements from a list is
a fairly common homework question,  I thought I'd let the group in on the
secret before they started to ask.

      Exercise for Teachers' Pets Everywhere: write code for
      permute(-N, +L, +P) and combine(-N, +L, +P), e.g.  combine(N,
      [u, v, w, x, y, z], [z, u, x]) should succeed and instantiate N
      to 3.


% Permutations and combinations
% Ken Johnson,  18 November 1992
% 
% You may copy and distribute this code freely,  but please acknowledge the
% source,  even if you only say `Actually I copied this code from Ken
% Johnson although I'm quite sure anybody with half a brain could have
% written it.' If you sell copies of my code at a profit,  I want a share. 

% permute(+N, +L, -C)
% instantiates C to a permutation of N elements of the list L

permute(0,_,[]).

permute(N,List,[X|More]) :-
	N > 0,
	member(X,List,Rest),
	N1 is N - 1,
	permute(N1,Rest,More).


member(H,[H|T],T).		% the usual member/3

member(X,[H|T],[H|U]) :-
	member(X,T,U).

% combine(+N,+L,-C)
% instantiates C to a combination of N elements of the list L

combine(0,_,[]).

combine(N,List,[X|More]) :-
	N > 0,
	combine_1(X,List,Rest),
	N1 is N - 1,
	combine(N1,Rest,More).

combine_1(X,[X|T],T).		% return an element of the list (X)
				% and the list (T) of those elements
combine_1(X,[_|T],U) :-		% that follow X in the list
	combine_1(X,T,U).

-- 
                                   //// Ken Johnson, A I Applications Institute
CNS server brain not responding   ////       80 South Bridge, EDINBURGH EH1 1HN
... still trying                 ////                  E-mail ken@aiai.ed.ac.uk
                                ////       Phone 031-650 2756  Fax 031-650 6513