Challenge: Lister toutes les parties d'un ensemble a N elements

Recherche :

Dernière réponse
Sujet : Challenge: Lister toutes les parties d'un ensemble a N elements
barbarella	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 :D

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

barbarella

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

LeGreg

Le Penseur Fou a écrit a écrit :

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

LEGREG

le penseur fou

barbarella a écrit a écrit :

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

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

barbarella

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]

nur

-->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+

barbarella

legreg,

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

LeGreg

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

le penseur fou

nur a écrit a écrit :

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

:bounce: :love: :crazy: :crazy: :crazy:

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

nur

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

le penseur fou

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

gizmo

nur a écrit a écrit :

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

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.

LeGreg

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]

nur

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 :D.
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

LeGreg

Le Penseur Fou a écrit a écrit :

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 :D.
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 :D.

A+
LEGREG

le penseur fou

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 :D
(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 .

LeGreg

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 :D
(et d'avoir du temps si n est grand..)

LEGREG

gizmo

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 :D)

nur

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.

minusplus

:??:

heu c pour quoi faire sans indiscrétions ?

nur

flo850 a écrit a écrit :

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.

flo850

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

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