(* 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