Algo

parties d un ensemble

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : parties d un ensemble

xara

Salut,
Je dispose d'un ensemble à n éléments ( les éléments étant placés dans une liste) et je voudrai avoir un algo qui me retourne les 2^n parties de cet ensemble dans une liste.

Si vous pouviez m'éclairer un peu.. merci d'avance

Publicité

Ace17

Soit x un élément de E. L'ensemble des parties de E, c'est la réunion disjointe de F et G
F : l'ensemble des parties qui ne contiennent pas x
G : l'ensemble des parties qui contiennent x

Bon, c'est juste un début. J'espere que tu n'as rien contre la récursivité

Pour calculer F, tu fais ca récursivement sur E, apres lui avoir oté un x arbitraire. Il n'y aura donc pas de x dans les sous ensembles de F.
Pour calculer G, tu prends F et tu ajoutes un x a chaque sous ensemble.

Message édité par Ace17 le 11-06-2004 à 18:43:23

xara

oui, j'avais cette idée la en tête, mais je dois alors mal le transcrire dans le language que j'utilise, c'est à dire caml.
Je pense que j'appliquais la récurrence à chaque sous partie F et G comme tu le dis , mais ça ne marche pas et je vois pas le probleme.
Car je dois ensuite récupérer tous les ensembles trouver et c'est la que ça coince

Ace17

Du Caml, excellent!
Poste ton code, si y'en a pas trop...

Joel F

Real men use unique_ptr

xara a écrit :

oui, j'avais cette idée la en tête, mais je dois alors mal le transcrire dans le language que j'utilise, c'est à dire caml.

:love:

poste poste !

Ace17

Bon allez, j'ai pas pu m'empecher...

Code :

let rec rajoute liste x =
match(liste) with
| [] -> [[x]];
| h::t -> (x::h)::rajoute t x;
;;
let rec parties liste =
match(liste) with
| [] -> [];
| x::t -> let sans_x = parties t in
let avec_x = rajoute sans_x x in
sans_x@avec_x;;

xara

ok merci pour l'aide.

(moi j'avais fait un truc du style

let rec parties liste=
match liste with
[]->[[]]
|t::q->(t:parties q))@(parties q);;

mais en effet ça marchait pas trop )

Il me reste plus qu'à faire la fonction totale ( celle ci étant juste une fonctin auxiliaire)

Ace17

Ben t'étais pas loin sauf que quand tu fais

Code :

t::(parties q)

tu lui demandes d'ajouter un élément (qui n'est pas une liste) a une liste de listes. Normal que ca passe pas

Message édité par Ace17 le 12-06-2004 à 12:58:36

FORUM HardWare.fr

Programmation

Algo

parties d un ensemble

Sujets relatifs
2 Javascripts ne fonctionnant pas ensemble	[HTML/Php] Formulaires en plusieurs parties?
Date + Heure en JS / DHTML : impossible les 2 ensemble !	Surcharge d operateur = et virtual , ca va ensemble ?
opengl parties cachées	Ouvrir/fermer l'ensemble des noeuds
cherche requete permettant de connaitre l'ensemble des tables	CSS : Appliquer propriété à un ensemble de td dans UNE table précise.
Challenge: Lister toutes les parties d'un ensemble a N elements	[algo] Ensemble des parties
Plus de sujets relatifs à : parties d un ensemble

Page générée en 0.045 secondes