Je sais que le nombre des parties d'un ensemble a N éléments est:
2^N Mais je voudrais faire un programme listant toutes les combinaisons .Je pense que l'on ne peut pas sans tirer sans les fonctions récursives et ça ne parait pas si simple.Si quelqu'un trouve, ça m'interresse.

tu veux toutes les parties ?
sioui , ta complexite ne peux pas descendre en dessoius de 2^N.
En effet meme si tu calcule un element en o(1) tu arrivera a 2^n au boiut.
c'est donc de l'algo bourrin , qui meme optimisé a mort , ne te permettra pas de calculer des ensemble correct (N>100, N>1000..)

 
Il se peut que les temps de calculs soit longs mais je pense  
qu'il est possible de faire un code relativement compacte
et c'est ce qui m'interresse.

 
heu c pour quoi faire sans indiscrétions ?

minusplus a écrit a écrit :   heu c pour quoi faire sans indiscrétions ?

 
l'interet pratique n'est pas essentiel c'est juste un petit  
défi que je me suis lançé car la programmation d'un tel bidule  
me parait assez ardu bien que le problème soit simple.

remarque n°1: on peut TOUJOURS défaire du récursif, et la solution non récursive sera TOUJOURS meilleur, tant en terme de place mémoire, qu'en terme de rapidité.
remarque n°2: pour faire simple considère ta suite délément comme une série de 1 et 0 (pris, pas pris) tu verras, l'algo coule de source. (je vais pas te le donner vu que c'est TON défi )

C'est vraiment debile comme probleme.
En fait lister les parties d'un ensemble a N elements
ca consiste juste a enumerer les nombres de 0 a 2^n-1.
Ca n'a rien d'ardu, il suffit de savoir compter
(et d'avoir du temps si n est grand..)
 
LEGREG

legreg a écrit a écrit : C'est vraiment debile comme probleme. En fait lister les parties d'un ensemble a N elements ca consiste juste a enumerer les nombres de 0 a 2^n-1. Ca n'a rien d'ardu, il suffit de savoir compter (et d'avoir du temps si n est grand..)   LEGREG

Et bien moi je pense que c'est interessant au contraire
il ne suffit pas d'enumerer les nombres
de 0 a 2^N mais tu dois donner
toutes les combinaisons de 1 elément (ça c'est facile)
de 2 elements ... de N-1 elements
si tu veux faire un code compacte c'est coton .
essaye deja de donner toutes les combinaisons de 5 elements parmis 10.
Je vais essayer de pondre un code en VB .

Oui mais tu remarques que  
ce n'est deja plus le meme probleme :-).
Celui de l'enumeration  
.. ce n'est pas un probleme (et c'etait le sens de mon
message).
les combinaisons de 5 elements parmi 10  
il y en C(5,10) et pour les enumerer
tu comptes de 0 a 2^10-1  
en n'affichant que les nombres ou 5 bits sont mis .
A peine plus complique. C'est compact
mais un peu lent, je reconnais.
 
Rien a voir mais ca me rappelle aussi des trucs sur les codes correcteurs
un code etant une sous partie de l'ensemble
des parties de l'ensemble a N elements..  
(ca va vous suivez ?)
et on definit des distances dans cet espace
par exemple en comptant le nombre d'elements qui
different d'une sous partie a l'autre .
 
A+
LEGREG

legreg a écrit a écrit :   les combinaisons de 5 elements parmi 10   il y en C(5,10) et pour les enumerer tu comptes de 0 a 2^10-1   en n'affichant que les nombres ou 5 bits sont mis . A peine plus complique. C'est compact mais un peu lent, je reconnais.     A+ LEGREG

 
 
Je ne pense pas que cette methode donne quelque chose
mais ce que j'aimerais c'est un code ou a defaut un algorytme
sinon, il y a des personnes qui disent (ou font croire que
c'est facile) mais ils ne donnent Jamais la solution ,ils se
contentent de donner de vagues indications qui ne permettent  
aucunes vérifications

 
je n'ai pas donne une vague indication !!
j'ai donne la solution parce que ton probleme se reduit a ca !
Si tu veux que je compte pour toi :
0000011111
0000101111
0000110111
0000111011
..
0000111101
0000111110
0001001110
..
bon la j'arrete parce qu'il y en a un paquet
(10!)/(5!*5!) exactement..
 
Si tu veux simplement enumerer l'ensemble des sous parties
sans ordre particulier je te donne le code:
for i = 0 to 2^n-1 do print i;
 
Voila tu reecris ca dans le langage que tu veux .
 
C'est pas bo la vie ?
 
LEGREG
ps: fo pas m'en vouloir si c'est aussi simple tout
de meme. tu t'etais lance un defi, ben voila felicitations tu l'as reussi .

[edtdd]--Message édité par legreg--[/edtdd]

 
c'est drole, mais dis comme ca, j'ai de plus en plus l'impression que tu essayes de nous faire faire un de tes projets a ta place.

voila ce que j'ai fait:
et effectivement si on prend la peine de décortiquer  
un peu ce programme c'etait pas si simple
la difficulté etait de creer une procédure recursive  
generant le nombre de boucles "FOR" voulues
sans cela la longueur du code aurait ete proportionnelle
au nombre d'elements
le programme liste toutes les parties d'un ensemble
a 10 elements dans un fichier texte.
 
 
 
 
 
Dim combi(10) 'variable globale
 
 
Sub Partie()
'AVEC N=10
grandn = 10
Dim j As Integer
 
Open "parties.txt" For Output As #1    ' Ouvre le fichier en écriture.
For j = 1 To grandn
Call boucle(1, grandn, j, j)
Next
Close #1
End Sub
 
 
 
 
 
Sub boucle(deb, fini, n, Gn)
Dim tt(10)
 
If n = 0 Then GoTo sortie
For tt(n) = deb To fini - n + 1
    combi(Gn - n) = tt(n)
   If n = 1 Then
     For i = 0 To Gn - 1
       Print #1, combi(i)
     Next
     Print #1,
   End If
   Call boucle(tt(n) + 1, fini, n - 1, Gn)
 
Next
sortie:
End Sub

-->legreg ce que tu donne(avec une pointe d'ironie) n'apporte rien du tout:
je sais trés bien faire "a la main" toutes les parties d'un ensembles les ensembles a 1 element,2 elements,...10 elements
exemple les parties a 2 elements parmis 10 sont:
1.2  1.3 1.4 ....1.9
2.3 2.4 2.5  ... 2.9
...................
 
Mais pour faire le code ou l'algo c'est une
autre paire de manche
 
-->Penseur  ça au moins c'est du concret! je teste ça
tout de suite.

--> Penseur Fou
Fantastique! ça marche Impec!
Toi tu n'es pas si fou que ça.
Balaize ton programme.
En fait je m'etais orienté vers la meme direction que toi
mais je me débattais avec la récursivité.
Trop Fort.
A+ et merci.

eheh  
 
le meme programme en C:
 
#include <stdlib.h>
#include <stdio.h>
 
void main()
{
   char buffer[20];
   int  i;
   // Note ici je fais pour n=10 et 2^n = 1024
   for (i=0; i<1024; i++) {
     // attention _itoa est specifique a Microsoft
     // mais un equivalent doit exister sur d'autres plateformes
     _itoa( i, buffer, 2 );
     printf( "%s\n", buffer );
   };
}
 
le plus complique doit probablement etre la conversion
entre mon entier et son ecriture binaire.
(mais puisque c'est une fonction de librairie
c'est pas un probleme..)
 
Attention, je te precise tout de meme que dans ton sujet
tu n'as pas precise que tu desirais une sortie triee
ce qui complique evidemment le probleme.
(et le programme de penseur doit surement bien
le faire meme si j'ai pas visual basic pour tester).
 
A+
LEGREG
ps pourquoi moi on m'ecoute jamais :-/

legreg,
 
heu, t'aurais pas oulié un morceau du programme

-->legreg  
Effectivement on s'etait mal compris
je voulais les elements tries (et en décimal)c'est pour ça  
qu'il fallait employer une procedure récursive.
Sinon pour ton programme il manque juste la partie qui
convertie les positions des bits en  elements.
C'est pas dur a faire, exemple:tu as 65 en binaire ça donne:
1000001 on doit obtenir la combinaison (7,1).
Si tu as excel tu peux tester le programme du Penseur
C'est ça que je voulais.
A+

on vous le répète,
 
on peut faire cette fonction sans récursivité, c'est la théorie qui veut ça. Tout système récursif peut être linéarisé.

[edtdd]--Message édité par barbarella--[/edtdd]

 
OUI en theorie ,mais selon moi il y a des
cas ou linéariser est beaucoup plus compliqué ,voir  
plus long ,que d'employer la récursivité et dans ce cas précis ça ne me paraissait pas faisable (voir mon topic).

Et puis si vous programmez en caml
et que vos fonctions sont toutes
recursives terminales
vous n'aurez pas de pb
 
LEGREG

oui,
 
ça peut sembler plus compliqué et des fois ça l'est. Mais bon on peut utiliser la recursivité pour faire un logiciel de compta, mais pour programmer un moteur 3D, mieux vaut pas