Fonction combinatoire (C(n,p))

Fonction combinatoire (C(n,p)) - Algo - Programmation

Marsh Posté le 20-10-2003 à 18:45:19    

je voudrais ecrire une fonction (je ne sais pas si c possible) de prototype par exemple :
combinatoire (entier: n, entier: p) : renvoi tableau
 
cette fonction renvoi TOUTES les combinaisons possibles (dans un tableau, 1 ligne = 1 combinaison) tel que le nombre de combinaison sera
entier x = 0
tq (p) {
 faire x = x + (C(n,p));
 p = p-1;
}
 
x represente alors le nombre TOTAL de combinaison. ces combinaison doivent etre enumeree et apparente (elles seront stockee ds le tableau renvoye)
 
exemple :
 
combinatoire (entier: 10, entier: 3) : renvoi tableau
{
entier x=0;
tant que (p) {
 x = x+C(10,p)
 p = p-1
}
 
au final x = C(10,3) + C(10,2) + C(10,1) + C(10,0)
 
le tableau resultat contiendra : toutes les facon de placer 3 chiffres 1 parmi 10 chiffres 0 + toutes les facon de placer 2 chiffres 1 parmi 10 chiffres 0 + toutes les facon de placer 1 chiffres 1 parmi 10 chiffres 0 + toutes les facon de placer 0 chiffres 1 parmi 10 chiffres 0
 
 
vous avez compris ?

Reply

Marsh Posté le 20-10-2003 à 18:45:19   

Reply

Marsh Posté le 20-10-2003 à 19:11:18    

oui, on a compris, et donc, ta question c'est ? :D

Reply

Marsh Posté le 20-10-2003 à 20:48:53    

Fais le en prolog c'est plus facile à coder [:sweet purple]

Reply

Marsh Posté le 21-10-2003 à 19:02:31    

tetedeiench a écrit :

oui, on a compris, et donc, ta question c'est ? :D


 
ben de recuperer le tableau en sortie contenant toutes les combinaisons.
Par exemple :
C(3,1) + C(3,0) donnera le tableau suivant (retourner par la fonction) :
 
100
010
001
000
 
 
Compris ?

Reply

Marsh Posté le 21-10-2003 à 20:20:48    

et dans quel langage ?

Reply

Marsh Posté le 21-10-2003 à 21:17:10    

giz a écrit :


 
ben de recuperer le tableau en sortie contenant toutes les combinaisons.
Par exemple :
C(3,1) + C(3,0) donnera le tableau suivant (retourner par la fonction) :
 
100
010
001
000
 
 
Compris ?


 
Et on doit répondre quoi ?
 
C'est une jolie tâche ?
 
c'est beau ?
 
Le chat de ta soeur a été soigné pour le choriza ?

Reply

Marsh Posté le 21-10-2003 à 21:25:20    

pour quand ?
tu veux des commentaires javadoc, doxygen ou egal ?

Reply

Marsh Posté le 21-10-2003 à 23:41:54    

chrisbk a écrit :

pour quand ?
tu veux des commentaires javadoc, doxygen ou egal ?
 


 
Avec multithreading il me semble, afin d'optimiser les performances, et si possible en assembleur, histoire de s'executer en un minimum de temps.
 
Bien évidemment, il faudra une release windows et linux ainsi que solaris et DOS 1.0 tournant sur 8088 svp.

Reply

Marsh Posté le 22-10-2003 à 11:20:02    

et un coca

Reply

Marsh Posté le 22-10-2003 à 13:23:30    

tetedeiench a écrit :


 
Et on doit répondre quoi ?
 
C'est une jolie tâche ?
 
c'est beau ?
 
Le chat de ta soeur a été soigné pour le choriza ?


 
ben j'appelle la fonction comme ca :
 
conbinatoire (3,1)
 
et elle me retourne le tableau (un tableau representant les combinaisons en binaires fera bien l'affaire)
100
010
001
000
 
...ecrire l'algorithme, c ce que je ve. Jusque la j'ai essaié de me faire comprendre au niveau du probleme a resoudre c tout, j'ai rien resolu.
 
compris ?

Reply

Marsh Posté le 22-10-2003 à 13:23:30   

Reply

Marsh Posté le 22-10-2003 à 13:27:59    

ben montre nous ce que t'as fait/essayé :O

Reply

Marsh Posté le 22-10-2003 à 15:01:43    

giz a écrit :


 
ben j'appelle la fonction comme ca :
 
conbinatoire (3,1)
 
et elle me retourne le tableau (un tableau representant les combinaisons en binaires fera bien l'affaire)
100
010
001
000
 
...ecrire l'algorithme, c ce que je ve. Jusque la j'ai essaié de me faire comprendre au niveau du probleme a resoudre c tout, j'ai rien resolu.
 
compris ?


 
oui et ben, tu sais, la catégorie algo, c'est pas des algos sur demande, c'est de l'aide dans l'algorithmique, et si tu es pas plus explicite, on t'aidera pas.
 
La, l'algorithme est quand même completement trivial... trois boucles imbriquées et voilà.

Reply

Marsh Posté le 22-10-2003 à 15:09:58    

tetedeiench a écrit :


 
oui et ben, tu sais, la catégorie algo, c'est pas des algos sur demande, c'est de l'aide dans l'algorithmique, et si tu es pas plus explicite, on t'aidera pas.
 
La, l'algorithme est quand même completement trivial... trois boucles imbriquées et voilà.


 
 :lol: vas-y j'attends ! alors OUI j'y suis arrive pour n et p FIXES ! mais n'oublie pas que la c une fonction qui recoit n et p (2 inconnues). Voilà. Je demande de l'aide pour un algo general donc !
Merci

Reply

Marsh Posté le 22-10-2003 à 19:15:25    

g é t clair la ? :??:

Reply

Marsh Posté le 22-10-2003 à 19:40:35    

Récursivité dans ce cas la mon ami, récursivité !
 
J'ai mal au crâne donc je ne vais pas pondre l'algo ici. Mais tu connait plusiurs propriétés pour décomposer les combinaisons. Code uniquement les cas d'arret et arrange tes cas successifs et ca passera comme une lettre a la poste.
 
Pour une telle tâche, je te conseille un langage de type LISP ( scheme quoi ) qui va te générer une liste avec tout ton bonheur.
 
Avec des boucles, effectivement, c'est difficilement réalisable. Pas en récursif.

Reply

Marsh Posté le 23-10-2003 à 13:14:40    

tetedeiench a écrit :

Récursivité dans ce cas la mon ami, récursivité !
 
J'ai mal au crâne donc je ne vais pas pondre l'algo ici. Mais tu connait plusiurs propriétés pour décomposer les combinaisons. Code uniquement les cas d'arret et arrange tes cas successifs et ca passera comme une lettre a la poste.
 
Pour une telle tâche, je te conseille un langage de type LISP ( scheme quoi ) qui va te générer une liste avec tout ton bonheur.
 
Avec des boucles, effectivement, c'est difficilement réalisable. Pas en récursif.


 
 :jap: effectivement je pense que la récursivité est inévitable ds ce cas la :/
...mais la tache n'est pas facile pour autant (jvé tenter de résoudre le problème

Reply

Marsh Posté le 09-08-2004 à 19:27:50    

longtemps apres, je reviens sur mon algo (j'en ai besoin pour mon prog actuel).
Je viens d'y reflechir plus profondément et...ne serait-ce pas un probleme NP-Complet ?  :heink: de resoudre cela.
 
Le prototype de la fonction nCp est :
int[][] combinatoire (n, p);
le tableau a deux dimensions renvoie tous les ensembles possibles de former
 

Tetedeiench a écrit :

La, l'algorithme est quand même completement trivial... trois boucles imbriquées et voilà.


 
 :lol:


Message édité par Giz le 09-08-2004 à 19:33:24

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

Marsh Posté le 10-08-2004 à 09:55:59    

Ben c'est sur que si tu lui demandes de te renvoyer toutes les combinaisons possibles et imaginables, la taille de ton tableau va rapidement devenir énorme, et le temps mis a le remplir aussi.  
 
Maintenant, c'est un peu con de se foutre de la gueule de Tetedeiench car c'est toi qui comprends mal : résoudre un probleme NP-Complet EST trivial. Il suffit de parcourir l'arbre!
 
C'est le résoudre en un temps raisonnable ( polynomial ) qui ne l'est pas. Or il se trouve que dans ton cas, il n'est tout simplement pas possible de réduire ce temps, puisque ce qui t'intéresse, justement, c'est les combinaisons et qu'il y en a beaucoup (!).

Reply

Marsh Posté le 10-08-2004 à 10:01:33    

Et j'ajoute que ton probleme n'est pas NP-complet, en fait c'est meme pas un probleme, puisque tu ne cherches pas de solution dans ton arbre, mais l'arbre lui meme!

Reply

Marsh Posté le 10-08-2004 à 10:29:53    

vi c'est vrai. :jap:. T1 c'est la merde en fait :/ ... c'est pas vraiment un arbre le truc parce que les sequences :
 
1-2-4
et 2-1-4
 
sont deux chemins differents pour l'arbre alors qu'en fait c'est une meme solution.  [:figti]


Message édité par Giz le 10-08-2004 à 11:44:23

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

Marsh Posté le 10-08-2004 à 17:47:59    

Ace17 a écrit :

Ben c'est sur que si tu lui demandes de te renvoyer toutes les combinaisons possibles et imaginables, la taille de ton tableau va rapidement devenir énorme, et le temps mis a le remplir aussi.  
 
Maintenant, c'est un peu con de se foutre de la gueule de Tetedeiench car c'est toi qui comprends mal : résoudre un probleme NP-Complet EST trivial. Il suffit de parcourir l'arbre!
 
C'est le résoudre en un temps raisonnable ( polynomial ) qui ne l'est pas. Or il se trouve que dans ton cas, il n'est tout simplement pas possible de réduire ce temps, puisque ce qui t'intéresse, justement, c'est les combinaisons et qu'il y en a beaucoup (!).


 
Je rajouterais : pour des problèmes de PETITE taille.


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

Marsh Posté le 10-08-2004 à 19:57:55    

J'ai dit :  
"résoudre un probleme NP-Complet EST trivial. Il suffit de parcourir l'arbre!
C'est le résoudre en un temps raisonnable ( polynomial ) qui ne l'est pas"
Il ne me semble pas avoir oublié quoi que ce soit.

Reply

Marsh Posté le 10-08-2004 à 20:00:50    

Giz a écrit :

c'est pas vraiment un arbre le truc parce que les sequences :
 
1-2-4
et 2-1-4
 
sont deux chemins differents pour l'arbre alors qu'en fait c'est une meme solution.  [:figti]


Ben parce que tu t'y prends mal, mais imagine un arbre binaire, dont la racine aurait pour étiquette "1". A gauche de la racine, les sous arbres des solutions qui contiennent "1", a droite, ceux qui ne le contiennent pas.

Reply

Marsh Posté le 10-08-2004 à 20:02:34    

Ace17 a écrit :

J'ai dit :  
"résoudre un probleme NP-Complet EST trivial pour des problèmes de petite taille. Il suffit de parcourir l'arbre!
C'est le résoudre en un temps raisonnable ( polynomial ) qui ne l'est pas"
Il ne me semble pas avoir oublié quoi que ce soit.


 
OK, je le fais à ta place alors  :p .
Parce que chercher à résoudre en parcourant l'arbre entièrement, tu peux attendre des siècles...on ne peut plus dire que l'algorithme trivial "marche".


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

Marsh Posté le 10-08-2004 à 20:04:42    

Ace17 a écrit :

Ben parce que tu t'y prends mal, mais imagine un arbre binaire, dont la racine aurait pour étiquette "1". A gauche de la racine, les sous arbres des solutions qui contiennent "1", a droite, ceux qui ne le contiennent pas.


 
C'est bon, j'ai trouvé : en fait suffit de parcourir les fils dont leur valeur est supérieur a celle du pere, ainsi on trouve parfaitement tous les ensembles ;)


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

Marsh Posté le 10-08-2004 à 20:16:40    

Giz a écrit :

OK, je le fais à ta place alors  :p


 
Mais je parle ici de la résolution théorique voyons! Pourquoi crois tu que j'ajoute la remarque sur le temps raisonnable...  
Et stp, évite de me citer en modifiant ce que je dis, je déteste ca.
Je maintiens ce que j'ai dit, je sais parfaitement que la résolution pratique naive d'un probleme NP complet peut facilement prendre des millions d'années pour peu qu'on ait des problemes de grande taille, cependant si tu disposes de ces millions d'années, eh bien le probleme n'en est plus un, et tu as ta solution. Evidemment, dans la pratique personne ne s'intéresse a des algorithmes aussi lents, mais ca ne change pas que c'est un probleme qu'on a les moyens de résoudre dans la théorie.
 

Giz a écrit :


Parce que chercher à résoudre en parcourant l'arbre entièrement, tu peux attendre des siècles...on ne peut plus dire que l'algorithme trivial "marche".


Si, il marche. C'est juste une histoire de mots, mais pour moi un algorithme dont le fonctionnement est démontré, "marche". Il se trouve que ca n'intéressera personne, car ce qui nous intéresse en tant qu'humains, c'est d'avoir la solution, au moins de notre vivant :D mais cet algorithme est parfaitement juste, et si on attend le temps qu'il faut il donne la solution : j'appelle ca marcher.


Message édité par Ace17 le 10-08-2004 à 20:23:32
Reply

Marsh Posté le 10-08-2004 à 20:26:50    

Ace17 a écrit :

Mais je parle ici de la résolution théorique voyons! Pourquoi crois tu que j'ajoute la remarque sur le temps raisonnable...  
Et stp, évite de me citer en modifiant ce que je dis, je déteste ca.
Je maintiens ce que j'ai dit, je sais parfaitement que la résolution pratique naive d'un probleme NP complet peut facilement prendre des millions d'années pour peu qu'on ait des problemes de grande taille, cependant si tu disposes de ces millions d'années, eh bien le probleme n'en est plus un, et tu as ta solution. Evidemment, dans la pratique personne ne s'intéresse a des algorithmes aussi lents, mais ca ne change pas que c'est un probleme qu'on a les moyens de résoudre dans la théorie.


 
mdr !  :lol:  
Bon alors le voyageur de commerce, on sait le résoudre théoriquement mais pas pratiquement alors ?  :lol: (qu'est ce qui faut pas entendre  :pt1cable: )
On s'interesse a la difficulté d'un problème par rapport a la puissance des machines avant tout (on vit dans un monde limité, il faut tout relativiser!)


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

Marsh Posté le 10-08-2004 à 22:49:59    

Giz a écrit :

mdr !  :lol:  
Bon alors le voyageur de commerce, on sait le résoudre théoriquement mais pas pratiquement alors ?  :lol: (qu'est ce qui faut pas entendre  :pt1cable: )
On s'interesse a la difficulté d'un problème par rapport a la puissance des machines avant tout (on vit dans un monde limité, il faut tout relativiser!)


 
Ne devient pas méprisant pour une histoire de mots, c'est juste qu'on n'a pas la meme définition de "résoudre".

Reply

Marsh Posté le 11-08-2004 à 02:17:30    

Giz a écrit :

C'est bon, j'ai trouvé : en fait suffit de parcourir les fils dont leur valeur est supérieur a celle du pere, ainsi on trouve parfaitement tous les ensembles ;)


 
Quel génie magicien ce Giz. C'est ce que ton maitre Ace17 te disait implicitement plus haut. Il faut lire (et comprendre). Et puis arrête de limiter la créativité de l'esprit des êtres humains à la puissance des ordinateurs. Comme si on devait relativiser pour s'y conformer. Tu délires mon pauvre Giz. Pour te faire bander, les ordinateurs quantiques arrivent.


Message édité par mexx20 le 11-08-2004 à 15:09:12
Reply

Marsh Posté le 11-08-2004 à 09:58:57    

mexx20 a écrit :

Quel génie magicien ce Giz. C'est ce que ton maitre Ace17 te disait implicitement plus haut. Il faut lire (et comprendre). Et puis arrête de limiter la créativité de l'esprit des êtres humains à la puissance des ordinateurs. Comme si ont devait relativiser pour s'y conformer. Tu délires mon pauvre Giz. Pour te faire bander, les ordinateurs quantiques arrivent.


 
J'ai pas attendu Ace17 pour me le dire implicitement. J'a v trouvé avt  :o . (de plus je ne le résouds pas avec un arbre binaire mais n-aire).
Sinon tu me fais bien marrer quand meme en disant qu'il n'y a pas besoin de relativiser  :lol: . C'est stupide de dire ca :pfff: . A quoi sert la montagne de chercheurs qui cherchent dans le domaine de la recherche operationnelle entre autre.  :pfff:

Reply

Marsh Posté le 11-08-2004 à 10:59:33    

Bon écoute, Giz, on va pas s'enerver pour une connerie, ok, tu avais trouvé avant que je te donne une solution ( ce que je n'ai jamais démenti, et d'ailleurs, les techniques qu'on utilise sont différentes, car j'utilise bien un arbre binaire ) c'est pas une raison pour te moquer des autres ( Moi et mexx20 entre autres ), de plus on est tous d'accord sur le fond, sache que le PVC je me suis penché dessus cette année, donc tu peux te douter que ce n'est pas moi qui vais dire que la montagne de chercheurs dont tu parles ne sert a rien, et d'ailleurs je doute que quelqu'un puisse penser une chose pareille, et ca m'étonne que tu puisses imaginer que quelqu'un d'autre le pense.
 
Bien sur, celui qui concoit un programme ne s'intéresse dans la pratique qu'a des algorithmes de complexité raisonnable lorsqu'il s'agit de manipuler beaucoup de données. Mais il n'y a pas que les concepteurs de programmes dans la vie, il y a aussi des mathématiciens. Le fait de savoir qu'il existe déja une voie sure qui nous mene a la solution est important.
 
Dans le cas du parcours d'un arbre, on a déja un moyen, meme s'il est beaucoup trop long, de calculer la solution. Alors que si je te donne une équation de degré 18 a résoudre, tu ne pourras pas me donner la solution exacte en un temps fini. Tu vois la nuance?  
 
Ainsi le temps est un probleme, mais c'est loin d'etre le seul.
 
PS : Je suis venu sur ce topic de mon plein gré pour t'aider, et je suis resté courtois jusqu'ici, je te prierais d'en faire autant s'il te plait.


Message édité par Ace17 le 11-08-2004 à 11:01:44
Reply

Marsh Posté le 11-08-2004 à 11:21:11    

Ace17 a écrit :

Bon écoute, Giz, on va pas s'enerver pour une connerie, ok, tu avais trouvé avant que je te donne une solution ( ce que je n'ai jamais démenti, et d'ailleurs, les techniques qu'on utilise sont différentes, car j'utilise bien un arbre binaire ) c'est pas une raison pour te moquer des autres ( Moi et mexx20 entre autres ), de plus on est tous d'accord sur le fond, sache que le PVC je me suis penché dessus cette année, donc tu peux te douter que ce n'est pas moi qui vais dire que la montagne de chercheurs dont tu parles ne sert a rien, et d'ailleurs je doute que quelqu'un puisse penser une chose pareille, et ca m'étonne que tu puisses imaginer que quelqu'un d'autre le pense.
 
Bien sur, celui qui concoit un programme ne s'intéresse dans la pratique qu'a des algorithmes de complexité raisonnable lorsqu'il s'agit de manipuler beaucoup de données. Mais il n'y a pas que les concepteurs de programmes dans la vie, il y a aussi des mathématiciens. Le fait de savoir qu'il existe déja une voie sure qui nous mene a la solution est important.
 
Dans le cas du parcours d'un arbre, on a déja un moyen, meme s'il est beaucoup trop long, de calculer la solution. Alors que si je te donne une équation de degré 18 a résoudre, tu ne pourras pas me donner la solution exacte en un temps fini. Tu vois la nuance?  
 
Ainsi le temps est un probleme, mais c'est loin d'etre le seul.
 
PS : Je suis venu sur ce topic de mon plein gré pour t'aider, et je suis resté courtois jusqu'ici, je te prierais d'en faire autant s'il te plait.


 
 [:darkmavis tt] Je ne vois pas ou je n'ai pas été courtois avec toi. C'est plutot mexx20 qui délire tout seul.  :pt1cable: . Si c'est sur la définition du mot résoudre qui t'a vexée, pardonne moi mais en général les mots on les prend dans leur 1er sens, sinon faut expliquer un peu plus c'est tout.
En gros tu voulais dire :
-En info (pratique) on s'interesse au problème de temps/mémoire.
-En math (théorie) on s'interesse au problème de savoir résoudre le problème.
Mais ici je parle bien d'informatique  ;)


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

Marsh Posté le 11-08-2004 à 14:36:52    

Deux choses à dire :  
 
1. un arbre n-aire est un arbre binaire (il peut être "vu" et "traité" comme tel).
2. l'informatique, c'est bien plus que des conneries d'implémentations sur un PC, qu'une syntaxe pourrie. C'est la sciences de l'information mon ami.
 
Lis un peu et arrête de croire que tout t'es acquit.


Message édité par mexx20 le 11-08-2004 à 14:39:16
Reply

Marsh Posté le 11-08-2004 à 16:10:12    

mexx20 a écrit :

Deux choses à dire :  
 
1. un arbre n-aire est un arbre binaire (il peut être "vu" et "traité" comme tel).
2. l'informatique, c'est bien plus que des conneries d'implémentations sur un PC, qu'une syntaxe pourrie. C'est la sciences de l'information mon ami.
 
Lis un peu et arrête de croire que tout t'es acquit.


 
Dans l'autre topic tu me dis d'areter de lire les bouquins parce que c'est "static".
et arrete de te la peter a chaque fois que tu dis kkchose avec tes remarques débiles c'est vraiment reloud !  :o


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

Marsh Posté le 11-08-2004 à 16:16:34    

Giz a écrit :

Dans l'autre topic tu me dis d'areter de lire les bouquins parce que c'est "static".

On peut lire autre chose que des bouquins... et mexx20 t'a dit :
 
"Et puis arrête de te cacher derrière Floyd et Sedgewick, les choses évoluent, la théorie des graphes est étudiée massivement de part le monde et tes bouquins sont statiques."
 
Ca veut pas dire que les bouquins ne valent rien. Ca veut juste dire qu'il faut se mettre a jour, et donc ne pas avoir de bible dans le domaine de la théorie des graphes.


Message édité par Ace17 le 11-08-2004 à 16:20:04
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed