Algo

Afficher tous les sous-ensembles de 1 a N

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Afficher tous les sous-ensembles de 1 a N

pinpoy

Bonjour,jai un tit probleme dalgorithmique à résoudre qui consiste a afficher tous les sous ensemble dentiers de 1 a N....

par exemble si je choisis N=3 ca donne

{}, {1}, {2} ,{3}, {1, 2}, {2, 3}, {1,3}, {1, 2 ,3}

il faut bien sur que ca marche pour nimporte quel entier posistif....et jai beau réfléchir je ne vois pas comment faire...

donc si vous avez une idée qui pourrait marcher ou un indice sur la facon de procéder ou meme la solution... je suis preneur ^^

merci davance

Message édité par pinpoy le 14-10-2006 à 17:46:39

Publicité

0x90

→

fait du récursif.

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.

Taz

bisounours-codeur

commence déjà par calculer combien il existe d'ensemble distincts pour N

Trap D

Celà se fait plutôt avec une file.
Il y aussi une possibilité amusante avec le nombre de sous ensembles possibles écrit en base 2.

Message édité par Trap D le 14-10-2006 à 23:45:44

Taz

bisounours-codeur

y a pas de récursion, il suffit d'énumérer en comptant en Base N de 0 à N**N

0x90

→

Bha tu peut considérer que tout les sous ensembles pour N=x sont tout les sous ensembles pour N=x-1 union ces même ensembles auquel tu a ajouté x.

Et, heu, si je compte en base N de 0 à N**N je tombe pour n = 3 sur:
0
1
2
10
11
12
t'interprète comment 11 ?

j'aurais plutot pensé énumerer les représentations binaires des entiers de 0 à 2^N pour faire dans l'itératif.

Message édité par 0x90 le 14-10-2006 à 23:47:45

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.

Taz

bisounours-codeur

J'interprète pas 11 parce que c'est n'est pas un ensemble.

c'est pas la peine de passer en binaire ...

0x90

→

Y'a des fois t'es tellement clair qu'on croirait que tu nous parle d'à travers ton cul

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.

Taz

bisounours-codeur

avec N = 3

1 -> ,,1
2 -> ,,2
3 -> ,,3
11 -> doublon, pas un ensemble
12 -> ,1,2
13 -> ,1,3
21 -> on a déjà
22 -> doublon, pas un ensemble
23 -> ,2,3
31 -> on a déjà
32 -> on a déjà
33 -> pas un ensemble
111-> pas un ensemble
etc ...

y a sans doute des tas de méthodes pour faire ces différentes combinaisons, plus ou moins efficace, mais c'est pas sorcier. Il y a "somme( pour k de 1 à n: C(k, n))" ensembles, si je ne me vautre pas. Pour n = 3, ça fait 3 + 3 + 1 = 7

0x90

→

Ok, ca fait quand même beaucoup de doublons / on a déja à éliminer

Et pour le nombre de solutions, tu prends chaque élément, tu leur assigne à chacun un bit d'un nombre binaire qui signifie ou non leur présence dans l'ensemble, et tu énumère les nombres binaires de longueur n, y'en a 2^n.

( mais passer par une représentation binaire qu'on incrémente puis ou on teste tout les bits est pas forcément efficace, par contre un algo genre code de gray directement sur l'ensemble est très envisageable )

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.

Publicité

pinpoy

merci bcp a taz ....................(et aux autres aussi :whistle: )

je vais coder ca et je vous tiendrais au courant sur la maniere voulu par le prof au cas ou ca vs intéresse :hello:

Giz

Tiens, un bout de code qui trainait sur mon dur, il devrait répondre à tes besoins :

Code :

/**
* -return all nCp subsets (with nCp = n!/(p!(n-p)!))
* -The algorithm uses a depth-first search technic with limited depth
* the limit is p value.
* -At final, each data in the LinkedList contains a subset
*/
protected LinkedList generateAllSubSets (int n, int p)
{
Node root, node;
LinkedList subSets;
int[] subSet;
int i;
Stack stack;
root = new Node (0, 0, null);
subSets = new LinkedList ();
stack = new Stack ();
stack.push (root);
//depth-first search algorithm
while (!stack.empty ())
{
node = (Node) stack.pop ();
//the limited depth has been reached
if (node.depth == p)
{
//construct the new subset
subSet = new int[p];
i = p-1;
while (node.parent != null)
{
subSet[i--] = node.value-1;
node = node.parent;
}
//add the subset
subSets.addFirst (subSet);
}
//we continue to explore the tree
else if (node.depth < p)
for (i = node.value + 1; i <= n; i++)
stack.push (new Node (i, node.depth + 1, node));
}
return subSets;
}

et la classe Node associée :

Code :

/**
* Define a subSet of population contructs from the reference set
*/
class Node
{
public int value;
public int depth;
public Node parent;
public Node (int value, int depth, Node parent)
{
this.value = value;
this.depth = depth;
this.parent = parent;
}
}

Bon tu es sur la bonne piste avec ça...(suffit de faire des appels avec des valeurs différentes de p)

Message édité par Giz le 17-10-2006 à 22:17:37

---------------
Asus P5Q Pro | C2D E8400 3GHz@4GHz + Noctua NH-C12P | 2x2Go Patriot Extreme PC-8500 | GeForce GTX 460@Stock 1Go GLH | Crucial SSD M4 64Go Sata3

darkoli

Le Petit Dinosaure Bleu

J'avais fais un truc similaire en C il y a pas mal de temps. J'avais utilisé une fonction récursive.

Spoiler :

int sous_ensembles(int N, int n, int tab[])
{
int i=0;
int nb_elements=0;
int debut=0;

if (N < 1) {fprintf(stderr, "sous_ensembles : paramètre \"N\" non valide.\n" );return ERREUR;}
if (n < 0) {fprintf(stderr, "sous_ensembles : paramètre \"n\" non valide.\n" );return ERREUR;}

/* Un sous-ensemble a été trouvé ! */
if (n >= N)
{
Affichage; décompte, ...
return OK;
}

/* Recherche */
debut=0;
if ( (n > 0) && (tab[n-1] > 0) ) debut=tab[n-1]+1;
for (i=debut;i<=N;i++)
{
tab[n]=i;
ensembles(N, n+1, tab);
}

/* Fin */
return OK;
}

Avec l'appel de la fonction récursive :

Spoiler :

ensembles(N, 0, tab);

---------------
Le site de l'année :D (XHTML 1.0 strict) : http://darkoli.free.fr/index.html

MEI

|DarthPingoo(tm)|

En Java, perso, sans limite de perf, et sans vouloir me faire chier, je coderais une classe ensemble avec des methodes Add/Remove/CompareTo/Contains.

Je genererais tout les ensembles possibles avec des boucles, en les metant dans un Vecteur d'ensemble. Et apres je filtrerais les mauvais grace au methodes ecritent avant.

Rapide a code je pense, pas besoin d'etre un fou en maths... Mais sans doute tres lent

---------------
| AMD Ryzen 7 7700X 8C/16T @ 4.5-5.4GHz - 64GB DDR5-6000 30-40-40 1T - AMD Radeon RX 7900 XTX 24GB @ 2680MHz/20Gbps |

0x90

→

Bon ben puisque c'est la fête aux algos :

Code :

void sets(size_t n)
{
    size_t i=0,j;
    char *t = calloc(sizeof(*t), n);
    while (i!=n) {
        for (i=0; i<n; i++) {
            if (t[i]==1) {
                t[i]=0;
            } else {
                t[i]=1;
                break;
            }
        }
        for (j=0; j<n; j++) {
            if (t[j]) {
                printf("%i ", j+1);
            }
        }
        putchar('\n');
    }
    free(t);
}

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.

pinpoy

Code :

#include <iostream.h>
#include <math.h>
//decomposition d'un entier n en base 2 dans un tableau de taille m
void decomp(int n, int m){
bool virg=0; //pour avoir un affichage correct
int t[m];
int last;
for (int i=0; i<m; i++){//T contiendra n coder en binaire
t[i] = n % 2;
n /= 2;
}
for (int i=0; i<m; i++){
if(t[i]==1){
if(virg==0){
cout<<i+1;
virg=true;
}
else
{
cout<<","<<i+1;
}
}
}
}
int main(){
cout<<"Valeur de n:";
int m;
cin>>m;
for (int j=0; j<pow(2,m); j++){ //pour un entier m => affichage des (2^m) -1 //1ers entiers en base2
cout<<"{";
decomp(j,m);
//ci dessous juste pour avoir un affichage correct
if(j<pow(2,m)-1){
cout<<"} ,";
}
else
{
cout<<"} ";
}
}
return 0;
}

le principe est le suivant :
on va stocker chaque nombre entre 0 et N en binaire dans un tableau int t[m];

par exemple pour N=3, on obtiendra les tableaux suivants

000 pour 0
001 pour 1
010 pour 2
011 pour 3
100 pour 4
101 pour 5
110 pour 6
111 pour 7

on a donc toutes les possibilité d'ensemble a 3 éléments si l'on considere l'indice de chaque élément + 1

000 --> {}
001 --> {3}
010 --> {2}
011 --> {2, 3}
100 --> {1}
101 --> {1, 3}
110 --> {1, 2}
111 --> {1, 2, 3}

cest sur fallait y penser :ouch:

Message édité par pinpoy le 20-10-2006 à 12:17:34

0x90

→

Ca serait bien de lire des fois, c'est exactement ce que j'ai dit et fait, en plus efficace...

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.

pinpoy

jai lu mais jai pas compris

nyrk

Pour répondre à la question de départ, n'ayant pas vraiment vu de description simple de l'algorithme :

Il y a deux sortes de parties de l'ensemble {1, 2, ..., N}, celles qui contiennent N et celles qui ne le contiennent pas. Lister l'ensemble des parties qui ne contiennent pas N revient à résoudre le problème pour N-1 et donc pour résoudre le problème pour N, il suffit de lister en plus les parties qui contiennent N qui sont tout simplement les parties de {1, ..., N-1} auxquelles on a ajouté N. Une implémentation en Caml pourrait être :

let rec parties = function
| 0 -> [[]]
| n -> let ps = parties (n-1) in ps @ (List.map (fun p -> n::p) ps)

Élégante mais cependant non récursive terminale donc seulement valable pour un devoir (:D) ou si les performances ne sont pas importante.

pwang

Voici une version récursive terminale* :

let parties =
let rec parties res = function
| 0 -> res
| n ->
parties (res @ List.map (fun p -> n::p) res) (n-1)
in parties [[]]

* c'est-à-dire que les appels récursifs n'ont pas besoin d'adresse de retour, et que le compilateur sait dérouler ce genre de fonctions pour les rendre de même efficacité que l'écriture impérative avec des boucles for ou while. Attention : le compilateur n'est pas capable de détecter tous les cas de recursion dont on souhaiterait qu'elle soit terminale... mais la plupart du temps c'est fait ! Et bien sûr, l'intérêt de la récursion est la concision...

Message édité par pwang le 22-10-2006 à 17:48:05

---------------
étudiant en master de recherche en informatique - algorithmique et programmation - langages : ocaml, etc.

nyrk

Ta version est bien récursive terminale mais étrangement elle plante chez moi pour n >= 16 avec l'exception "Stack overflow during evaluation (looping recursion?).". J'ai essayé de remplacer la fonction "@" par "List.rev_append" qui est récursive terminale, mais ça ne change rien. Je ne vois pas où est le problème... :heink:

pwang

List.map n'est pas récursive terminale...

Et... étant donné que la liste finale est de longueur 2^16... euh... ça fait peut-être beaucoup sur la pile...

pwang

Voici une version totalement récursive terminale (enfin j'espère ) :

let parties =
let rec parties res = function
| 0 -> res
| n ->
parties
(List.rev_append
res
(List.rev_map (fun p -> n::p) res))
(n-1)
in parties [[]]

(en tout cas il fait passer parties 17 - et même 18... - alors que sinon à 16 il refuse)

Message édité par pwang le 22-10-2006 à 20:08:51

---------------
étudiant en master de recherche en informatique - algorithmique et programmation - langages : ocaml, etc.

nyrk

Je suis bête d'avoir pensé à @ mais pas à List.map.

Edit: grillé pour la version complètement récursive terminale.

Message cité 1 fois
Message édité par nyrk le 22-10-2006 à 20:08:52

pwang

nyrk a écrit :

Edit: grillé pour la version complètement récursive terminale.

Message édité par pwang le 22-10-2006 à 20:09:51

---------------
étudiant en master de recherche en informatique - algorithmique et programmation - langages : ocaml, etc.

Publicité

FORUM HardWare.fr

Programmation

Algo

Afficher tous les sous-ensembles de 1 a N

Sujets relatifs
[Opengl] afficher un texte	DOM/XSLT n'est pas afficher dans mon phpinfo()
parcourir, Stocker image ds bd mysql et l'afficher !!	[.Net C# 2.0]Afficher les categories / sous-categories d'un forum
[RESOLU]Afficher date la plus récente et heure en conséquence	[C#.NET] Afficher une zone d'un fichier PDF dans une fenetre ?
Résolu - Afficher dans ma page une valeur pointée par une URL	[Resolu][C#NET] Mettre le focus sur un onglet (pour le faire afficher)
[PHP] Afficher derniere ligne d'un fichier texte	Afficher/télécharger une image provenant du Web (LWP et Tk)
Plus de sujets relatifs à : Afficher tous les sous-ensembles de 1 a N

Page générée en 0.092 secondes