Discussion :

[lachose]

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

[Trap D]

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.

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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?

[ToTo13]

Bonjour,

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

[billynirvana]

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

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

[Nemerle]

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

[Trap D]

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

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

Ton algo peut maintenant s'écrire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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é
[/edit]

[ToTo13]

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.

[Trap D]

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

[ronan99999]

soit A un ensemble et ai un element de celuici.

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

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.

[lachose]

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