/***** A definition of making change for $1: 
   change(Q,N,D,P)  holds true if the sum of the monetary values of
   the Q quarters, D dimes, N nickels, and P pennies totals $1.  
*/
change(Q,D,N,P) :-
    /* First, define the universe of individuals (atoms) we use:
       (these are like the "data types" of the param names) */
        member(Q,[0,1,2,3,4]),                  /* quarters     */
        member(D,[0,1,2,3,4,5,6,7,8,9,10]) ,    /* dimes        */
        member(N,[0,1,2,3,4,5,6,7,8,9,10,       /* nickels      */
                   11,12,13,14,15,16,17,18,19,20]),
        /* Next, define the constraints on the solution: */
        Sum is 25*Q +10*D + 5*N,
        Sum =< 100,
        P is 100-Sum.



/***** Making change for  HowMuch:  changeFor(HowMuch, Q,N,D,P)
   holds true if the sum of the monetary values of the Q quarters,
   D dimes, N nickels, and P pennies totals  HowMuch
*/
changeFor(HowMuch, Q,D,N,P) :-
        /* we list the atoms in order of preference for use: */
        member(Q,[5,4,3,2,1,0]),     /* quarters     */
        member(D,[5,4,3,2,1,0]),     /* dimes        */
        member(N,[4,3,2,1,0]),       /* nickels      */
        member(P,[4,3,2,1,0]),       /* pennies      */
        HowMuch is 25*Q +10*D + 5*N + P.




/***** Defining sorting as an ordered permutation of a list: */

/* select(X, HasAnX, HasOneLessX)  "extracts" X from  HasAnX,
   giving HasOneLessX.  (That is,  [X|HasOneLessX]  is a permutation
   of  HasAnX.)  The definition is built into Prolog, but here it is, anyway:

select(X, [X|Rest], Rest).
select(X, [Y|Ys], [Y|Zs]) :- select(X, Ys, Zs).
*/

/* permutation(Xs, Zs)  holds true if Zs is a reordering of Xs */
permutation([], []).
permutation(Xs, [Z|Zs]) :- select(Z, Xs, Ys),  permutation(Ys, Zs).

/* ordered(Xs) holds true if the elements in Xs are ordered by < */
ordered([]).
ordered([X]).
ordered([X,Y|Rest]) :- X =< Y,  ordered([Y|Rest]).

/* sorted(Xs, Ys)  holds when  Ys  is the sorted variant of Xs */
sorted(Xs, Ys) :- permutation(Xs, Ys), ordered(Ys).




/***** Refining the definition of  select,  yielding selection sort: */

/* selectLeast(X, Ys, Zs)  if  X  is the least element in list Ys  and  [X|Zs]  is a permutation of  Ys,  that is,  Zs  is  Ys  with  X  removed. 
*/
selectLeast(X, [X], []).
selectLeast(X, [Y|Ys], [Y|Zs]) :-  selectLeast(X, Ys, Zs), X < Y.
selectLeast(Y, [Y|Ys], [X|Zs]) :-  selectLeast(X, Ys, Zs), Y =< X.

/* permutation  stays the same, as does  ordered  and  sorted: 
   (but note use of  selectLeast)  */
permutationL([], []).
permutationL(Xs, [Z|Zs]) :- 
                    selectLeast(Z, Xs, Ys),  permutationL(Ys, Zs).

sortedL(Xs, Ys) :- permutationL(Xs, Ys), ordered(Ys).




/***** Refining the definition of  permutation,  giving insertion sort: */

/* insert(X, L, LwithX)  inserts element X into ordered list L, generating ordered list,  LwithX */
insert(X, [], [X]).
insert(X, [Y|Ys], [X, Y | Ys]) :-  X =< Y.
insert(X, [Y|Ys], [Y|Zs]) :-  X > Y,  insert(X, Ys, Zs).

/* permuationI(Xs, Ys)  uses  insert  to generate list Ys as a permutation of list Xs:  */
permutationI([], []).
permutationI([X|Xs], Ys) :-  
                 permutationI(Xs, Zs), insert(X, Zs, Ys).

sortedI(Xs, Ys) :- permutationI(Xs, Ys), ordered(Ys).