(*
   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 - dita 
   estrutural) 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çamos 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 (se existir...) 
   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))

 *)

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

This document was generated using caml2html