partition d'un ensemble finie

je cherche a crée l'ensemble des partitions d'un ensemble qui contient des entiers de 0 a n.
je n'ai aucune idée de fonction ou même d'algorithme alors si vous pensée a quoi que ça soit dit le ;).
MERCI BIEN

Eh bien, réfléchis à ce que tu ferais si tu devais le faire à la main. C'est déjà un bon début.
Il y a des méthodes numériques, mais un bon algo pour un débutant ce n'est pas mal non plus.

je pense a crée les ensemble de cardinal n-1 puis n-2 ... mais la encore ça génère beaucoup de possibilité que je ne peut pas géré :
par exemple pour crée les partition de cardinal 3 il faut :
Code:

1 2 3 4 5 6 7 8 9 10 11 int *t; int *s; for(i=0;i<n-2;i++) for(j=i+1;j<n-1;j++) for(k=j+1;k<n;k++) { t={i,j,k} s[k+(n-(j+1))*j+((n-1)-(i+1))*i]=t;//je suis pas aussi sur de //cette afféctation }
a la fin j'aurai toute les partition de cardinal 3 (j'espère que ne me trompe pas).
mais comment faire pour les autres partitions?

Bonjour,

est ce que tu as des critères particulier pour créer ta partition ???

En Prolog, cela se fait en 4 cuillères à pots avec 2 prédicats.

Dans ce cas, la récursivité est ton ami.

Citation:

Envoyé par lachose

je pense a crée les ensemble de cardinal n-1 puis n-2 ... mais la encore ça génère beaucoup de possibilité que je ne peut pas géré :
par exemple pour crée les partition de cardinal 3 il faut :
[CODE]
int *t;
int *s;
for(i=0;i<n-2;i++)
for(j=i+1;j<n-1;j++)
for(k=j+1;k<n;k++)
{
t={i,j,k}
s[k+(n-(j+1))*j+((n-1)-(i+1))*i]=t;//je suis pas aussi sur de
//cette afféctation
}
/CODE]
a la fin j'aurai toute les partition de cardinal 3 (j'espère que ne me trompe pas).
mais comment faire pour les autres partitions?

Le problème ici est que du code en dur :arrow: tu utilises 3 variables i,j,k pour générer tes sous-ensembles à 3 élements. D'où le problème si tu veux générer les sous-ensembles à n éléments (il te faudrait "n" variables).

Essaie de penser différement: prend une variable l allant de 1 à n et trouve un truc pour générer les sous-ensembles de taille l. N'utilise pas de for, mais des while, avec "d'autres" variables pour t'aider...

Ou bien alors, comme l'a suggérer mon précédeur, pense à la récursivité (mais cela n'est pas obligatoire, surtout si tu veux un temps de réponse rapide).

D'abord une remarque simple, un élément est dans une partition ou n'y est pas !
Maintenant, si tu connais toutes les partitions de l'ensemble 1 .. n , pour connaître toutes les partitions de l'ensemble 1 .. n+1 tu passes en revue celles de 1..n et à chaque fois tu en obtiens deux celle avec n+1 et celle sans n + 1.
A partir de là l'algo est simple.
On sait que le nombre de partitions de 1..n et 2^n.
Tu as besoin d'un tableau de 2^n lignes dont chaque ligne est un tableau de n entiers.
Au début ce tableau ne contient qu'un seul élément, l'ensemble vide qui sera symbolisé par une ligne vide (ne contenant que des zéros).
On va boucler sur le nombre n et à chaque tour de boucle on va maintenir

un index sur le nombre de lignes du tableau à parcourir
un index sur la ligne où insérer une nouvelle partition

Ton algo peut maintenant s'écrire
Code:

1 2 3 4 5 6 7 8 9 nb_lignes <- 1 nb_insertion <- 2 pour tous les nombres i de 1 à n faire pour toutes les lignes j de 1 à nb_lignes du tableau faire recopier au rang nb_insertion la ligne d'index j auquel on a ajouté i nb_insertion <- nb_insertion + 1 fin pour nb_lignes <- nb_insertion - 1 fin pour
Ce qui te donnes à la fin dans le tableau pour n = 3
Code:

1 2 3 4 5 6 7 8 9 vide <== initialisation 1 <== fin premier tour 2 1 2 <== fin deuxième tour 3 1 3 2 3 1 2 3 <== fin troisième tour
[edit] ce ne sont pas les partitions, ce sont les sous-ensembles, désolé :oops:
[/edit]

Citation:

Envoyé par billynirvana

En Prolog, cela se fait en 4 cuillères à pots avec 2 prédicats.Dans ce cas, la récursivité est ton ami.

Je suis entièrement d'accord avec ça, à condition que le problème soit bien définit.
Mais pour avoir fait du prolog, je pense qu'il n'est pas indiqué si ce problème s'inscrit dans le cadre d'un projet plus important.

Et pourquoi pas ?
On peut appeler SWI Prolog dans un prog C et récupérer le résultat ensuite, ça pourrait être intéressant (mais peut-être un peu lourd pour "si peu").

soit A un ensemble et ai un element de celuici.

A = U{ai} | i E [1,n];

Citation:

PARTITION(A: ENSEMBLE): PARTITION
//{0} ensemble vide (Weil que Weil)
Si card(A) = 0 alors PARITION(A) := {{0}}
sinon
//a un element de A
PARTITION(A) := {{a} U* PARTITION(A-{a}),PARTITION(A-{a})}
finsi

U* :union distribuée sur tout les ensembles de la partition.

ben merci a vous tous (spécialement TrapD ;) ) pour votre aide vos proposition ils étaient de très grand utilité pour moi MERCI BIEN.

pour répondre a ToTo13 qui a demandé si le problème s'inscrit dans le cadre d'un projet plus important. ben j'essaie d'implémenter un algorithme que nous avons fait au cours de théorie des langages qui consiste a déterminiser un automate non déterministe
je vous pris de resté au contact avec cette discussion car j'aurais besoin de vous :D