probleme d'enumeration des parties d'un ensemble

bonjour a tous, j'ai un serieux probleme le voila

pour n entier donné on cherche les solutions de a1+a2+....=n avec les a dans un ensemble l et l'ordre des a compte
par exemple si

l={1,2} et n=4
donc les solutions:
2+2;
2+1+1
1+2+1
1+1+2
1+1+1+1

et l'autre probleme c
on a un ensemble E a n element on cherche les ensemble des parties deux a deux disjoints et de taille dans la liste l et dont l'union et E.
exemple

E={a,b,c} et l={2,1}
donc la solution c
{{a},{b},{c}},{{a},{b,c}},{{b},{a,c}},{{c},{a,b}}

j'espere que vous pouvez m'aider en plus si les sol sont dans un language fonctionnel ça serai mieux


salut a tous voici l'algo su premier probleme mais il compte pas l'ordre c implementer en OCAML

let rec ajout a l=
  match l with
  []->[]
  |x::s->[a::x]@(ajout a s);;
    
let rec enum n p=
    if n<=0 then [[]]
    else
        begin
        if p=[] then []
        else
            begin
                let x::s=p in
                    if x<=n then (ajout x (enum (n-x) p))@(enum n s)
                    else enum n s
            end
        end;;

enum 4 [1;2]
donne
[[2;2];[1;1;1;1];[1;1;2]];;

et meme c vous connaissez pas la programmation fonctionnel c pas grave juste des solution meme logique dans n'importe quel language, et s'il vous plait pas de programme qui faire exploser la pile , je c que c'est tres difficile a le faire meme avec la theorie des graphe.

anyway have greate times every one w8in for ur help

merci d'avance

salut

moi je vais juste commenter ton code ocaml :

pourquoi tu mets des begin et des end ?
pourquoi utilises tu l'operateur @ ? (il est super lent...)

a la place de :

let rec ajout a l=
  match l with
  []->[]
  |x::s->[a::x]@(ajout a s);;

tu peux mettre :

let rec ajout a = function
  | [] ->[]
  | x::s ->a::x::(ajout a s);;

ce qui est plus court, plus simple, et plus rapide (mais c'est pas tail-rec, donc ca peut faire sauter la pile).

bon ta fonction ajout, elle ajoute a entre chaque element de la liste passee en parametre... je ne saisis pas bien l'utilite de la chose.

bonjour merci beacoup pour ta reponse,
premierement ta fonction est fausse, elle est pas bien typé, car OCAML quand il rencontre le :: il pense que c'est un element et pas une liste a concaténer,
et voici un exemple du code qui fonctionne pas:
ajout 1 [[12];[4]];;
Characters 9-13:
  ajout 1 [[12];[4]];;
           ^^^^
This expression has type 'a list but is here used with type int

et meme un autre qui fonctionne mais donne des resultats fausses:

ajout 1 [1;2;3];;
- : int list = [1; 1; 1; 2; 1; 3]

en tt cas
pour l'utilisation des begin et des end c parceque OCAML est comme dans les autre language par exemple C++
dans une boucle ou un bloc if si tu met pas les accolades {} il va just associer la prochaine instruction juste apres le if avec ce if et il va continuer normalement,
par exemple
if a=b then doThing1 ; DoThing2
ici OCAML va executer doThing1 juste si a=b mais doThing2 va s'executer toujours, alors pour les arranger vous ajouter les begin et les end
if a=b then begin doThing1 ; doTing2 end

anyway
le programme il procede comme suit,
ajout elle accepte une int -> int list list -> int list list
et ejoute a chaque liste un entier a l'entete de chaque element (qui est une liste encore)
ex:
ajout 1 [[3;4];[4;5;7]];; donne
[[1;3;4];[1;4;5;7]]

ok la fonction enum elle precede comme suit,
pour enumere un entier n sur un ensemble on procede comme suit
si l'ensemble et vide en renvoit simplement la liste vide
sinon
on prend le premier element de la liste x des partie et on enumere recursivement l'entier (n-x) sur la liste qui reste s tout en ajoutant a la fin ce x a l'ensemble des partie qu'on obtient
et apres en enumere encore n sur la liste restante s,
c ça
i hope that helps,

hum... j'avais pas compris ta fonction :
let ajout a li = List.map (fun x -> a::x) li;;

et je persiste... pour une seule instruction, begin et end ca ne sert a rien.

ok donc 100 euros si le begin end compte ok

voila essaye de taper cette fonction en OCAML

let rec fn a =
  if a=5 then print_int a
  else print_int 0 ;fn (a-1);;

apparemment elle va faire la reccurence jusqu'a 5 c ça? ok essaye par exemple

fn 10;; et voir ce qui donne

ici on veut appeler la fonction jusqu'a 5 si ce n'est 5 encore en affiche 0 et on appele la fonction pour a -1 ok
d'accord le probleme c que la fonction boucle infiniment comme ça car l'appel récursif se fait toujours car il y a acune condition pour arreter
donc plutot pour arreter en 5 en ajout les begin et end dans la branche else voir ça

let rec fn a =
  if a=5 then print_int a
  else begin print_int 0 ;fn (a-1) end;;

essaye fn 10;;
waw elle affiche 0 0 0 0 0 5 et arrete c cool ha,
j'espere que ta compris l'utilité de begin et end,
ok tu prepare les 100 euro je vais te communiquer mon compte pour les envoyer lol
salut
je veux des reponse pas de debogage de code svp, le compilateur c faire ça mieux
salut

quand t'as deux instructions, tu peux faire comme ca :

let rec fn a =
  if a=5 then print_int a
  else let _ = print_int 0 in fn (a-1);;

bon, pour resumer, ajout c'etait ca :

let ajout a li = List.map (fun x -> a::x) li;;

et enum ca donne ceci :

let rec enum n p=
    if n<=0 then [[]]
    else match p with
    | [] -> []
    | x::s -> if x<=n
      then (ajout x (enum (n-x) p)) @ (enum n s)
      else enum n s;;

avoue, c'est beaucoup plus court :)

chez moi ca concerve l'ordre :)

# enum 4 [1;2];;
- : int list list = [[1; 1; 1; 1]; [1; 1; 2]; [2; 2]]

a oui j'ai compris ce que tu veux dire aujourdhui, ok c cool
je sais faire comme ça mais il dise t'aura 5 sur la lisibilité du code donc... tu c en tt cas
mon probleme comme g dit c l'ordre
# enum 4 [1;2];;
- : int list list = [[1; 1; 1; 1]; [1; 1; 2]; [2; 2]]

ton affichage et tt a fait correcte mais je veux plutot ça moi

# enum 4 [1;2];;
- : int list list = [[1; 1; 1; 1]; [1; 1; 2]; [1; 2; 1]; [2; 1; 1]; [2; 2]]
veut dire toutes les combainisons possibles avec l'ordre qui compte donc [2;1;1] c diff de [1;2;1]
j'espere que c clair aujourdhui
merci pour tes reponse

si c'est un exercice de cours, alors il est debile..

let rec f n li =
  if n < 0 then failwith("f") else
  if n = 0 then [[]]
  else let rec f2 = function
  | [] -> []
  | hd::tl -> if hd > n
    then f n tl
    else List.append
      (List.map (fun x -> hd::x) (f (n - hd) li) )
      (f2 tl)
  in f2 li;;

f 5 [1;2;3];;


# f 4 [1;2];;
- : int list list = [[1; 1; 1; 1]; [1; 1; 2]; [1; 2; 1]; [2; 1; 1]; [2; 2]]

ton probleme, c'est que tu listais ca sur le reste de la liste, et pas sur la liste en entier

Bon, sinon, c'est pas DU TOUT tail-rec, donc ca va faire sauter la stack. malheureusement, mettre un accumulateur pour faire ca en tail-rec, ca risque de le rendre moins lisible et plus lent...

waw c tres rapide!!!!!!!!!!!!!
dite, comment ta fait pour trouver la solution? c vraiment geneale ça! et en plus ta utiliser OCAML ou, c ma premiere année et je trouve vraiment de difficulte pour migrer de la prog impérative (c# vb.net asp.net)  vers les trucs fonctionnels,

anyway
le code foncionne tres bien mais, je te dis la verite, j'ai pas bien compris ce qui ce passe en plus, le faite de difinir une fonction dans une autre et toutes les deux s'appelle comment ça ce passe dedans? est ce que a chaque appele recursif de f2 le compilateur creer une nouvelle fonctin et reserve un espace dans la pile?

et c pas un exercice de cours mais un projet de combinatoire informatique,

je te tire le chapeau c tres cooooooooooooooool
merci beaucoup