C++

[resolu] renvoyer les termes de combinaison des C(n,k)

Recherche :

Mot : Pseudo : Filtrer
Page : 1 2 Page Suivante Page Précédente Bas de page
Auteur	Sujet : [resolu] renvoyer les termes de combinaison des C(n,k)

nicolasm

Salut,je cherche a renvoyer les combinaisons des C(n,k)
exemple je passe n et k en parametre et je veux

les n et les k pouvant etre de l ordre de 100 ou 200

si n=2 et k=4
1,2 1,3 1,4
2,3 2,4
3,4

kelkun aurait une idee de la facon de traiter le probleme
(est-ce que je dois calculer d abord le nombre de termes?)

Merci!

PS: un code ou un morceau serait le bien venu!

bonne journee a tous et a toutes!

Message édité par nicolasm le 23-09-2002 à 15:31:35

Publicité

JeSuisPasUnNumero

interessé

LetoII

Le dormeur doit se réveiller

je vois aps trop ce que tu essaye de faire :??:

---------------
Le Tyran

nicolasm

letoII a écrit a écrit :

je vois aps trop ce que tu essaye de faire :??:

je cherche a obtenir tout les couples des combinaisons
nouvel exemple
j ai n=3 et p=5
je veux toutes les combinaisons de trois elements
soit 1,2,3
1,2,4
1,2,5

1,3,4
1,3,5

1,4,5

2,3,4
2,3,5

2,4,5

3,4,5

C plus clair?

LetoII

Le dormeur doit se réveiller

Ha oui comme ça c plus clair.

---------------
Le Tyran

nicolasm

JeSuisPasUnNumero a écrit a écrit :

http://forum.hardware.fr/icones/flag1.gif interessé

Si tu trouves de ton cote merci de me l envoyer!
niko

JPA

t'as un gros disque j'espère pour stocker les valeurs car pour n=200 et k=200 tu as 200!/(100!*100!) possibilités.
(200! = factorielle(200) = 200 * 199 *198 * .... * 2 * 1)

Bleuarff

pouet

Soit g rien compris, soit tu veux le triangle de pascal :??:

---------------
©2008 Bleuarff Corp.

nicolasm

Bleuarff a écrit a écrit :

Soit g rien compris, soit tu veux le triangle de pascal :??:

Non,ce que je veux c les combinaisons de N parmi P
mais pas leur valeur ,ce que je veux ce sont tout les tuples
soit l ensemble E ={a,b,c} C(2,3)={a,b}{a,c}{b,c}

et moi ce que je veux c est recuperer {a,b} puis {a,c} puis {b,c}
voila

nicolasm

JPA a écrit a écrit :

t'as un gros disque j'espère pour stocker les valeurs car pour n=200 et k=200 tu as 200!/(100!*100!) possibilités.
(200! = factorielle(200) = 200 * 199 *198 * .... * 2 * 1)

en fait on a revu a la baisse, seul les p sont tres gros et les n
ne depassent pas 20 pour le stockage ca sera dans un fichier au pire, si t as une idee hesite pas!

niko

Publicité

smaragdus

whores, drugs & J.S. Bach

nicolasm a écrit a écrit :

Non,ce que je veux c les combinaisons de N parmi P
mais pas leur valeur ,ce que je veux ce sont tout les tuples
soit l ensemble E ={a,b,c} C(2,3)={a,b}{a,c}{b,c}

et moi ce que je veux c est recuperer {a,b} puis {a,c} puis {b,c}
voila

En gros il faut que tu imbriques k boucles parmi les n elements mais en évitant les doublets et en eliminant les permutations. Je pense que la solution se situe dans un algo recursif.

Bleuarff

pouet

M'enfin cptet une conneire, je suis pas certain d'avoir compris ce que yu veux donc voila...

soit E l'ensemble

Code :

procedure cnk_ens(n,p:integer);
var i,j:integer;
begin
for i:=0 to high(E) do
for j:=i+1 to high(E) do
writeln('{',E[i],',',E[j],'}');
end;

fo vraiment qe je m'emmerde a mon stage pour arriver a faire du code pour d'autres...

---------------
©2008 Bleuarff Corp.

nicolasm

Bleuarff a écrit a écrit :

M'enfin cptet une conneire, je suis pas certain d'avoir compris ce que yu veux donc voila...

soit E l'ensemble

Code :

procedure cnk_ens(n,p:integer);
var i,j:integer;
begin
for i:=0 to high(E) do
for j:=i+1 to high(E) do
writeln('{',E[i],',',E[j],'}');
end;

fo vraiment qe je m'emmerde a mon stage pour arriver a faire du code pour d'autres...

C presque ca mais ca fait que les combinaisons de deux variables moi il me les faut toutes C(3,9) ne marchent pas par ex !
merci qd meme de ton aide et bon stage

PS c koi ton langage la c du pseudo code?

Message édité par nicolasm le 22-07-2002 à 16:52:57

Bleuarff

pouet

C du pascal ça, je sais pas faire grand-chose d'autre pour le moment

Sinon je vois pas pkoi ça te va pas...tu veux ausis touts les combinaisons qui te vont pas ? tu remplaces le

Code :

for j:=i+1 to high(E)...

par

Code :

for j:=1 to high(E)

---------------
©2008 Bleuarff Corp.

nicolasm

Bleuarff a écrit a écrit :

C du pascal ça, je sais pas faire grand-chose d'autre pour le moment

Sinon je vois pas pkoi ça te va pas...tu veux ausis touts les combinaisons qui te vont pas ? tu remplaces le

Code :

for j:=i+1 to high(E)...

par

Code :

for j:=1 to high(E)

En fait ce que tu me propose n est valable que pour les
C(2,p) et pas pour les C(n,p) car ton algo n est pas recursif c ca le probleme!mais merci quan meme

Bleuarff

pouet

putain je viens de comprendre le truc... :ouch: en effet me recursif semble obligatoire...g rien a foutre je vais voir ce que je peux faire...

---------------
©2008 Bleuarff Corp.

LeGreg

Bon c'est assez facile en fait:

bon faudrait essayer de le modifier pour le rendre recursif terminal

resultat:

#1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5
- : unit = ()

LeGreg

Bleuarff

pouet

c quoi ça, du C++ ? Je comprends rien...

---------------
©2008 Bleuarff Corp.

LeGreg

ca marche aussi pour autre chose que des nombres

combirec 3 ["rouge";"jaune";"vert";"bleu";"indigo";"violet"] "";;

resultat:

#rouge,jaune,vert
rouge,jaune,bleu
rouge,jaune,indigo
rouge,jaune,violet
rouge,vert,bleu
rouge,vert,indigo
rouge,vert,violet
rouge,bleu,indigo
rouge,bleu,violet
rouge,indigo,violet
jaune,vert,bleu
jaune,vert,indigo
jaune,vert,violet
jaune,bleu,indigo
jaune,bleu,violet
jaune,indigo,violet
vert,bleu,indigo
vert,bleu,violet
vert,indigo,violet
bleu,indigo,violet
- : unit = ()

A+
LeGreg

LeGreg

oops on est dans le forum "C, c++"..
desole j'avais pas vu
enfin c'est adaptable en C++ mais c'est moins compact..

LeGreg

LeGreg

Voila une traduction a peu pres litterale du code caml
donc c'est peut-etre moins performant:

Code :

#include <string>
#include <iostream>
using namespace std;
typedef char* lpstrz ;
void combirec(int k, lpstrz l[], const string &s) {
if (k==0) {
cout << s << endl;
return;
}
if (*l==0) return;
if (s.empty())
{
combirec(k-1, l+1, *l);
}
else
{
combirec(k-1, l+1, s+","+*l);
}
combirec(k, l+1, s);
}
int main() {
lpstrz tableau[] = {"1", "2", "3", "4", "5", 0};
combirec(3, tableau, "" );
return 0;
}

et la sortie:

1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5

LeGreg

Message édité par LeGreg le 23-07-2002 à 14:02:42

nicolasm

legreg a écrit a écrit :

Voila une traduction a peu pres litterale du code caml
donc c'est peut-etre moins performant:

Code :

#include <string>
#include <iostream>
using namespace std;
typedef char* lpstrz ;
void combirec(int k, lpstrz l[], const string &s) {
if (k==0) {
cout << s << endl;
return;
}
if (*l==0) return;
if (s.empty())
{
combirec(k-1, l+1, *l);
}
else
{
combirec(k-1, l+1, s+","+*l);
}
combirec(k, l+1, s);
}
int main() {
lpstrz tableau[] = {"1", "2", "3", "4", "5", 0};
combirec(3, tableau, "" );
return 0;
}

et la sortie:

1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5

LeGreg

MERCI BCP y a un peu de C++ MAIS JE L ADAPTERAI EN C ET PUIS C SYMPA DE TA PART
PS:C KOI LE LANGAGE ZARBI AVANT?

LeGreg

euh le langage precedent c'est du Caml
c'est un des langages de choix des algorithmiciens
a cause de sa simplicité et de son efficacité.
C'est un langage moitié fonctionnel/moitié impératif.

C++ essaie de copier certaines features des langages
fonctionnels (par les templates, pointeurs de fonctions, recursivité) mais n'y arrive pas aussi bien.

Caml n'est plus maintenu sauf dans la version qui est utilisée
par l'éducation nationale, il y a une version orientée objet qui est mise a jour ( http://www.ocaml.org/ ).

Par exemple, il m'a fallu reflechir un moment avant
de sortir la bonne version en C++ du programme, alors que c'est assez naturel en CAML (une fois qu'on connait la syntaxe).

A+
LeGReg

Musaran

Cerveaulté

Le problème étant horrible...
...ma solution est horrible ! (mais elle marche)
Exemple pour un ensemble de caractères:

Code :

//////////////
//Combiner.h//
//////////////
#include <malloc.h>
#define dimof(a) ( sizeof(a)/sizeof(a[0]) )
#define CombinerM(n,ae) Combiner(n, alloca(n*sizeof(int)), dimof(ae), ae##Callback )
typedef void (*pvf)() ; //pvf: pointeur de fonction sans arguments ne retournant rien
void Combiner(int numCases, int* tabCases, int numElm, pvf callback) ;
//////////////
//Combiner.c//
//////////////
#include "Combiner.h"
//éléments privés
static int ni ; //nombre d'indices
static int* ai ; //tableau d'indices de combinaisons
static int ne ; //nombre d'éléments
static pvf fn ; //pointeur sur la fonction de rappel
//partie récursive (à usage interne)
static void CombinerRec(int ii, int vali){
if(ii==ni) //profondeur de récursion maximum
fn(); //appel pour combinaison prête
else
for( ai[ii]=vali ; ai[ii]<ne ; ++ai[ii] ){ //compter avec cet indice
CombinerRec(ii+1, ai[ii]+1) ; //récursion avec l'indice suivant commençant à 1 de plus
}
}
//élément public
void Combiner(int numCases, int* tabCases, int numElm, pvf callback){
if(numElm<numCases || numCases<1) //si pas assez d'éléments ou pas de cases...
return ; //...erreur, ne rien faire
ni=numCases ;
ai=(int*)alloca(ni*sizeof(int)) ;
ne=numElm ;
fn=callback ;
CombinerRec(0,0) ;
}
/////////////////
//utilisateur.c//
/////////////////
#include <stdio.h>
#include "Combiner.h"
//exemple de tableau d'éléments
char tabElems[] = {'a','b','c','d','e'} ;
//exemple de fonction de rappel correspondante
void tabElemsCallback(){ //à chaque passage ici, une nouvelle combinaison valide est dans ai[]...
int i;
for(i=0 ; i<ni ; ++i)
printf( "%c,",tabElems[ ai[i] ] ) ;//affiche l'élément n° i
printf("\b.\n" ) ; //effacer la dernière virgule, nouvelle ligne
}
//exemple de test
int main() {
//appel normal
int tabIndices[3] ; //recevra les combinaisons
Combiner(dimof(tabIndices), tabIndices, dimof(tabElems), tabElemsCallback) ;
printf("\n" ) ;
//appel simplifié via une macro
CombinerM(3,tabElems) ;
return 0;
}

Cela dit, ce serait beucoup plus propre avec les classes et patrons du C++.

---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone

LeGreg

Citation :

Le problème étant horrible...
...ma solution est horrible ! (mais elle marche)

Elle te plaisait pas ma solution?

LeGreg

Musaran

Cerveaulté

legreg a écrit a écrit :

Elle te plaisait pas ma solution?

Le string n'existant pas en C, fallait bien y remédier... et c'est pas simple !
J'ai également aménagé la possibilité de combiner n'importe quoi, et de faire autre chose que afficher.

A noter que je me suis concentré sur les performances, d'où une certaine "obfuscation".

---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone

bjone

Insert booze to continue

legreg a écrit a écrit :

Bon c'est assez facile en fait:

bon faudrait essayer de le modifier pour le rendre recursif terminal

resultat:

#1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5
- : unit = ()

LeGreg

waou....

ça c'est du language limpide [:sisicaivrai]

LeGreg

bjone a écrit a écrit :

waou....
ça c'est du language limpide [:sisicaivrai]

Ah la version en C est tout de suite plus claire .

LeGreg

LeGreg

petit test:
pour calculer les 13983816 combinaisons du loto:
391 millisecondes
(la recursivité n'est pas un probleme)

par contre pour les afficher: 1heure..
(il faudrait presque les afficher sous Dos,
la console windows est vraiment trop lente)

LeGreg

bjone

Insert booze to continue

c plus simple de les foutre dans un fichier et attrapper notepad

Musaran

Cerveaulté

J'ai déjà eu le problème.
Je voulais chronométrer le calcul de nombres premiers, je me retrouvais à mesurer la vitesse d'affichage :pt1cable: .

Il est loin le premier test en Basic interprété sur un Apple II qui prenait 1 mn pour atteindre 1000...

---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone

CorranHorn

0.300 GFlops/s

legreg a écrit a écrit :

Ah la version en C est tout de suite plus claire

.

LeGreg

:non: pas si on a déja fait du caml :sol:

En prolog ça doit être plus clair pour les non initié

---------------
A suivre

Musaran

Cerveaulté

Même quand on a l'algorithme correctement décrit, il reste encore à faire des choix d'implémentation.
La solution dépend des points fort et faibles du langage choisi...

Je rêves parfois d'un langage de description d'algorithmes capable de générer le code correspondant dans des langages différents, en choisissant au mieux entre récusion/boucles pointeurs/indices pré-allocation/dynamisme tests avant/après ect...

Je dis que le problème des combinaisons est horrible parce que:

Le nombre de "cases" n'est pas connu à la compilation: récursion obligée.
La dernière récursion doît connaître l'état des précédentes: mémorisation indispensable (dynamique puisque nombre pas connu à la compilation)
La mémorisation exige une initialisation à la première récursion: récursion contrariée.

---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone

LeGreg

Citation :

Je dis que le problème des combinaisons est horrible parce que:

Le nombre de "cases" n'est pas connu à la compilation: récursion obligée.
La dernière récursion doît connaître l'état des précédentes: mémorisation indispensable (dynamique puisque nombre pas connu à la compilation)
La mémorisation exige une initialisation à la première récursion: récursion contrariée.

tu n'exageres pas un peu ?

LeGreg

Musaran

Cerveaulté

Je trouves pas.
Ça fait partie de ces problèmes très simples à énoncer mais compliqués à résoudre (la solution dépend beaucoup du langage).

J'oubliais:

Renvoi à l'appelant d'un grand nombre de valeurs.

---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone

LeGreg

ca m'a l'air tout de meme assez fortement lineaire
=> l'enoncé déboule directement sur la solution optimale.

Je pensais a un probleme dérivé:
trouver l'ensemble E minimal de combinaisons a 6 chiffres parmi 49 telles que l'on ait au moins une combinaison gagnante a 5 chiffres. (pour toute combinaison c de C(5,49), il existe une combinaison c' de E telle que c est inclue dans c'.
Quelqu'un a une idée un peu fine?

LeGreg

nicolasm

legreg a écrit a écrit :

ca m'a l'air tout de meme assez fortement lineaire
=> l'enoncé déboule directement sur la solution optimale.

Je pensais a un probleme dérivé:
trouver l'ensemble E minimal de combinaisons a 6 chiffres parmi 49 telles que l'on ait au moins une combinaison gagnante a 5 chiffres. (pour toute combinaison c de C(5,49), il existe une combinaison c' de E telle que c est inclue dans c'

.
Quelqu'un a une idée un peu fine?

LeGreg

Y en a qu on deja essaye de calculer des probas en integrant les 5000 dernieres sorties du loto mais ca marche pas au mieux tu gagnes 20f pour 18 depenser et pour un travail de ouf!!!

En tout cas je vois que mon probleme vous a bien fait reflechir

Musaran

Cerveaulté

Euh...

Les probabilités n'aident en rien pour un jeu de hasard pur comme le Loto.
Les statistiques sur les nombres joués peuvent servir.

Ce sujet a déjà été beaucoup débattu...

---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone

LeGreg

il ne s'agit pas de proba pour gagner au loto
il s'agit d'un bete probleme d'algo

LeGreg

Musaran

Cerveaulté

nicolasm a écrit a écrit :

Y en a qu on deja essaye de calculer des probas en integrant les 5000 dernieres sorties du loto mais ca marche pas au mieux tu gagnes 20f pour 18 depenser et pour un travail de ouf!!!

Il parle bien de probabilités pour gagner au Loto, non ?

Sinon je vais chercher pour le problème des ensembles gagnants.

Message édité par Musaran le 03-08-2002 à 00:35:20

---------------
Bricocheap: Montage de ventilo sur paté de mastic silicone

Publicité

Page : 1 2

Page Suivante

Page Précédente

Haut de page

FORUM HardWare.fr

Programmation

C++

[resolu] renvoyer les termes de combinaison des C(n,k)

Sujets relatifs
[HTML, JS]Eviter l'effet mosaique sur une petite image ? [resolu]	[MySQL] Requete de fou qui bugge - résolu
[MySQL] le même champs, 2 fois dans la même requête - résolu	[applet java] ouvrir une connexion http et renvoyer le code .... ?
prob d'insertion d'enregistrement dans une DB access 97 [ Résolu ! ]	[JAVA RESOLU] Pb avec une applet
Lire/écrire du Little Endian en Java [resolu]	Tag personalisés dans PHP (résolu)
window.open, mais dans la même page?? (résolu)	[PHP] Peut-on créer une constante de type tableau? (résolu)
Plus de sujets relatifs à : [resolu] renvoyer les termes de combinaison des C(n,k)

Page générée en 0.107 secondes