(*perm*)

fun remove e [] = []
   |remove e (a::x) = if e=a then x else a::remove e x;
(* Remove the first occurance of e from the list (a::x) *)

fun add_and_remove x [] = [(x,[])]
   |add_and_remove x y = map (fn e => (e::x,remove e y)) y;
(* Given a list X and a list Y deliver a list of pairs 
   of list [(X1,Y1),(X2,Y2),...,(Xn,Yn)] such that the list Xi
   is X plus element Ei (where Ei is a member of Y) and Yi 
   is Y minus element Ei *)

add_and_remove [] [1,2,3];
   
fun perm x =
    let fun xperm [] = []
           |xperm ((x,[])::z) = x::xperm z
           |xperm ((x,y)::z) = xperm ((add_and_remove x y)@z)
    in xperm [([],x)] end;
(* Given a list, generate all permutations of that list.
   (Note how this differs from Reade page 101, and Wikstrom
    page 224 and 431). The "inner" function xperm does all the
   work, and exists to hide the "ugliness" of its arguments 
   from the outside world. xperm takes as arguments a list 
   of pairs of lists [(X1,Y1),...,(Xn,Yn)]. A pair (Xi,Yi) 
   are the arguments for "add_and_remove", and the list of pairs
   is also the result of a call to "add_and_remove". That is 
   function "xperm" feeds "add_and_remove" its own output.
   This "eating output" stops on a pair (Xi,[]), that is Xi is
   now a permutation of X.

   (1) Is permx going "depth" or "breadth" first? If it is one of 
       these then can you do the other? 
   (2) Could you terminate it when it has produced the first n 
       permutations?
   (3) Modify it such that it produces all combinations, that is
       all 1-tuples, all 2-tuples, ..., all n-tuples 
   (4) *)

val x = perm [1,2,3,4];