(*

  Pretendemos gerar todas as sublistas possíveis duma determinada listas.  Este
  exercício assemelha-se a geração do conjunto de todos os subconjuntos
  dum determinado conjunto com a particularidade de que a ordem dos elementos importa 
  (a lista [a;b] é diferente da lista [b;a] e pretendemos aqui considera-las ambas).

  Aqui vão uns exemplos:

  subbag de [] = [[]]
  subbag de [c] = [[]; [c]]
  subbag de [b;c] = [[]; [b]; [c]; [b;c] ; [c;b]]
  subbag de [a;b;c] = [[]; [a]; [b]; [c]; [a;b]; [a;c] ; [b;a] ; [b;c]
  ; [c;a] ; [c;b] ; [a;b;c]; [a;c;b] ; [b;a;c] ; [b;c;a]; [c;b;a] ;
  [c;a;b]]

  
*)

open List

(* mas antes, algumas funções auxiliares...*)

 (*
   Imagine que pretendemos calcular a lista de todas as sublistas de l 
   com os elementos na ordem presente na lista original (ou seja [a;c] é 
   sublista de [a;b;c] mas não [c;a]) .

   Estratégia para seguir: Dividir para conquistar.
   
   O objectivo é perceber como usar o resultado para uma solução
   pequena/menor para calcular a solução para um problema maior.

   Vamos aqui usar recursividade estrutural (atenção, nem todos os
   problemas se conseguem resolver com este tipo de recursividade) ou
   seja perceber como uma solução para [a1;a2;a3;...;an] pode
   contribuir para a solução de [a0;a1;a2;a3:...;an].


   Começemos assim por determinar o resultado para os casos de base:
   [], e depois para [c], para [b;c] e para [a;b;c]. 

   O objectivo é tentar perceber que padrão existe entre a solução dum
   caso para o caso imediatamente maior. Vamos assim tentar organizar o
   resultado por forma a facilitar o aparecimente deste padrão.

   Este padrão formará a resolução para o caso recursivo.


   sublista []     = [[]]
   sublista [c]    = [[];[c]]
   sublista [b;c]  = [[];[c];[b];[b;c]]
   sublista [a;b;c]= [[];[c];[b];[b;c];[a];[a;c];[a;b];[a;b;c]]
  
   Ou seja: 

   sublista el::li = 
   sublista li @ el::(todos os elementos de (sublista li))

 *)
  let rec sublists l = match l with
      []    -> [[]]
    | x::xs ->
	let subl = (sublists xs) in
        subl @  (map (fun l -> x::l) subl)



 (* calcular a lista de todas as listas possíveis que resultam da
    inserção de e em l.  

    val insertions e l : 'a -> 'a list -> 'a list list

    insertions e []      = [[e]]
    insertions e [c]     = [[e;c];[c;e]]
    insertions e [b;c]   = [[e;b;c];[b;e;c];[b;c;e]]
    insertions e [a;b;c] = [[e;a;b;c];[a;e;b;c];[a;b;e;c];[a;b;c;e]]


    logo:          

    insertions e el::li = 
    juntar e::el::li a (el::(todos os elementos de (insertion e li)))
    

 *)



  let rec insertions e l = match l with
      []    -> [[e]]
    | x::xs -> 	(e::l) :: (map (fun li -> x::li) (insertions e xs))



(*
  Calcular a lista de todas as permutações de l.


  permutation []      = [[]]
  permutation [c]     = [[c]]
  permutation [b;c]   = [[b;c]; [c;b]]
  permutation [a;b;c] = [[a;b;c];[b;a;c];[b;c;a];[a;c;b]; [c;a;b]; [c;b;a]]


  logo: (das várias soluções, mostramos duas...)

  1) permutation el::li = inserir el em todas as soluções de (permutation li)

  2) el::li --> seja v = inserir el em li + inverter as soluções
  encontradas (ou seja v). Em resumo: v@(map rev v)  excepto no caso em que |v|=1 (evita duplicados...)

*)
  let rec permutations l = match l with
      []    -> [[]]
 (* primeira solução*)  
    | x::xs ->  flatten (map (fun l -> (insertions x l)) (permutations xs))
(* segunda solução
    | x::xs -> let v = insertions x xs in if length v=1 then v else (v@(map rev v))
*)
;;	
 


 (*
    
    Função principal. Subbag =  a lista de todas as permutações de todas as
    sublistas de l.
    
  *)
  let subbag l =
    sort compare
    (flatten
      (map (permutations) (sublists l)));;

      
      
(** EXERCÍCIO 


    Não será possivel calcular *directamente* a função subbag
    sem usar todas as funções auxilares precedentes??

    Dica: tente reescrever os casos de base (para [], [c], [b;c]
    etc...) por forma a exibir um padrão facilmente aproveitável.


**)