% randperm.pl - permute a list randomly, or select randomly from a list
% Version 0.2
% Copyright (C) 2006 Matthew Skala

% This program is free software; you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation; either version 2 of the License, or
% (at your option) any later version.

% This program is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
% GNU General Public License for more details.

% You should have received a copy of the GNU General Public License
% along with this program; if not, write to the Free Software
% Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% I've used this code in many different projects, most notably Caves of
% Golorp.  It's not a module because it's so small, though it would be easy to
% put it in one.

% The API is:
%
%   random_element(+L,-E)
%   return a randomly selected element from the list L.
%
%   randomly_permute(+I,-O)
%   randomly permute the elements, like shuffling a deck of cards.
%
%   Both predicates are "deterministic" in Prolog's sense of only succeeding
%   once, though they succeed in a random fashion.  If you want to build a
%   failure-driven loop that iterates through the elements of a list in a
%   random order (useful, for instance, if you want to use random variable
%   or value selection in a Davis-Putnam constraint solving algorithm), then
%   do something like:
%      randomly_permute(L,X),member(E,X),...

insert_after_nth([],_,X,[X]):-!.
insert_after_nth(L,0,X,[X|L]):-!.
insert_after_nth([H|T],P,X,[H|NT]):-
   succ(NP,P),!,insert_after_nth(T,NP,X,NT).

random_element([],_,E,E):-!.
random_element([H|T],N,P,E):-
   succ(N,NN),
   (random(NN)=:=0->PP=H;PP=P),
   !,random_element(T,NN,PP,E).
random_element(L,E):-
   random_element(L,0,nothing,E).

% improved, O(n log n) algorithm
randomly_permute([],[]):-!.
randomly_permute([X],[X]):-!.
randomly_permute([X,Y],[X,Y]):-random(2)=:=0,!.
randomly_permute([X,Y],[Y,X]):-!.
randomly_permute(A,B):-
   random_split(A,C,D),randomly_permute(C,E),randomly_permute(D,F),
   (random(2)=:=0->append(E,F,B);append(F,E,B)).

random_split([],[],[]).
random_split([H|A],[H|B],C):-random(2)=:=0,!,random_split(A,B,C).
random_split([H|A],B,[H|C]):-random_split(A,B,C).