probleme d'enumeration des parties d'un ensembleRésolu

Question

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

coucou747 · Accepted Answer

lol t'as un projet de combinatoire que tu vas rendre et qui ne fait que 10 lignes :D


let rec f n li =
  if n < 0 then failwith("f") else (* si n est inferieur a 0 c'est qu'on est alle trop loin. *)
  if n 0 then [[]] (* si n 0 alors c'est la combinaison vide*)
  else let rec f2 = function (* ici, on definit une nouvelle fonction pour pouvoir parcourrir la liste li *)
  | [] -> [] (* si on a fini le parcourt*)
  | hd::tl -> if hd > n (* si hd est superieur a n, alors on ne peut pas mettre hd dans la liste, on continue donc juste le parcourt. *)
    then f2 tl (* en me relisant, j'ai vu une erreur ici, en fait, on doit continuer le parcourt de la liste. *)
    else List.append (*ici, c'est une traduction de ton @ et de ta fonction ajouter.*)
      (List.map (fun x -> hd::x) (f (n - hd) li) )
      (f2 tl)
  in f2 li;; (* enfin, on appelle f2*)


clique sur reponse acceptee stp.

coucou747 · Answer

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.

martaniF · Answer

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,

coucou747 · Answer

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.

martaniF · Answer

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

coucou747 · Answer

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]]

martaniF · Answer

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

coucou747 · Answer

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...

martaniF · Answer

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

martaniF · Answer

merci , mais c juste la moitie du probleme
 voici la deuxieme question

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}}
les tailles des sous liste sont toujours un element de la liste l

apres je pense le truc de modeleser ce probleme a l'aide de la soustraction est un peu pas ok,
car dans cette question la ya plus de relation d'ordre sur les elements,
en tt cas je vais me débrouille pour celle la, 
mais dite ta utiliser OCAML ou, et comment ta pu te rendre en un PROGRAMMEUR FONCTIONNEL qui pense vraiment pas comme les mec impératifs?

ok sol accepter mais tu dois repondre  a è derniere question
salut

coucou747 · Answer

pour moi, programmer de facon imperative, objet ou fonctionelle, c'est pas du tout pareil, mais avec un peu d'entrainement, on y arrive tres bien.

si tu veux t'entrainer au fonctionnel en caml, la maniere la plus simple est de recoder List.ml
si tu veux t'entrainer au fonctionnel en lisp (ou scheme ou autre) alors lire le SICP et coder des choses marrantes (exos du SICP ou exos du projet euler, en utilisant les choses apprises dans le sicp) te fait un bon entrainement.

perso, avant, je n'avais fait que de l'imperatif et de l'objet, j'ai commence le caml l'an dernier (en janvier) et j'en ai fait pas mal :) apres, je me suis mis au lisp en debut d'annee en imprimant le SICP.

Bref, en caml apres avoir fait cet entrainement, tu dois apprendre a manipuler les types algebriques, et pour ca, t'as le choix. Tu peux faire un truc pour manipuler des expressions formelle par exemple. Perso, j'ai fait des choses pour manipuler des polynomes et pour manipuler un "AST" brainfuck, et un langage perso compilable en brainfuck (langage de macros)

apres, ocaml n'est pas seulement fonctionel, on peut aussi programmer objet ou imperatif en caml, mais je n'ai jamais fait ca (j'ai jamais utilise le caractere mutable des valeurs, ni les references non plus)

coucou747 · Answer

je ne vois pas pourquoi tu notes ca :
{{a},{b},{c}},{{a},{b,c}},{{b},{a,c}},{{c},{a,b}}

j'imaginerais plutot ca :

{{a},{b},{c}},{{a},{b,c}},{{a,b},{c}}

et toutes les permutations

coucou747 · Answer

type t = A | B | C | D | E | F;;

let rec split e li let rec f function
  | [] -> []
  | hd::tl -> 

let rec split_n n li if n List.length li then (li, [])::[]
  else if n = 0 then ([], li)::[]
  else match li with
  | [] -> failwith("taken")
  | hd::tl -> List.append
    (List.map (fun (a,b) -> ((hd::a), b)) (split_n (n-1) tl))
    (List.map (fun (a,b) -> (a, (hd::b))) (split_n n tl));;

let rec split e = function
| [] -> [[]]
| hd::tl -> let couples = split_n hd e
  in List.flatten ( List.map (fun (a,b) -> List.map (fun c -> a::c) (split b tl) ) couples );;

let e = A::B::C::[]
in let l = 1::2::[]
in split e l;;



ici j'ai la version ou tu decoupes e en un certain nombre de listes d'exactement l_i elements. (ici, t'auras une liste de taille 1 et une liste de taille 2)

martaniF · Answer

salut merci pour tes reponse je peux pas les verifier now mais pour les enumeration
ta dit {{a},{b},{c}},{{a},{b,c}},{{a,b},{c}}

mais ta oublier {{b},{a,c}}

enfin merci beacoup je pense que ça aide vraiment, mais ocaml c vraiment pas cool dans le sens du production, pour la mutabilité du langage en utilise ça le prochain semestre dans le genie logiciel, et c indispensable d'utiliser les mutable dedans,
anyway, moi je prefere F# c un tres bon lang qui partage tres nombreuses fonctionnalite avec ocaml mais c dans la plateforme .NET donc forcement plus productif,

merci beacoup coucou c tres sympa de ta part
bye

coucou747 · Answer

en fait, je concervais l'ordre

martaniF · Answer

salut,

b1 la dernière fonction est mal typé,

il m'indique synatx error, mais je vois rien erronné, svp revise la et dit moi ce qui ne marche pas?

ocaml est vraiment pauvre dans ces truc, pas de debugger ou pas a pas compilation
en tt cas,

et et, si tu peux exprime en français (pas par les appen et map, je c que tu metrise bien parler par ça lol) ce que vous applique dans tes fonctions, par exemple, pourquoi tu parcours la liste tel fois et.... tu c c totlement defficile a comprendre juste avec le code

martaniF · Answer

autre chose la premiere fonction enum est fausse, elle fonctionne pas avec 0 dans la liste per exemple enum 4 [0;1;2] boucle infiniment voici la version correcte let rec enum n p= if n<=0 then [[]] else match p with | [] -> [] | x::s -> if (x<=n) && (x<>0) then (ajout x (enum (n-x) p)) @ (enum n s) else enum n s;;

coucou747 · Answer

... il y a un debuger, et ocaml te souligne ce qu'il n'arrive pas a comprendre.

bageaco · Answer

salut,
juste pour vous demander la version C++ de ce code, j'aimerai l'utiliser dans un problème combinatoire.
Merci et a bientôt.

Probleme d'enumeration des parties d'un ensemble

19 réponses

Votre réponse

Discussions similaires