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 ?

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

Fais le en prolog c'est plus facile à coder

 
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 dans quel langage ?

 
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 ?

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.

et un coca

 
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 ?

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

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

 
  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

g é t clair la ?

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.

 
  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

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

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

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!

vi c'est vrai. . 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.  

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

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.

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.

 
OK, je le fais à ta place alors   .
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".

 
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

 
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.
 

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 mais cet algorithme est parfaitement juste, et si on attend le temps qu'il faut il donne la solution : j'appelle ca marcher.

 
mdr !    
Bon alors le voyageur de commerce, on sait le résoudre théoriquement mais pas pratiquement alors ?   (qu'est ce qui faut pas entendre   )
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".

 
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.

 
J'ai pas attendu Ace17 pour me le dire implicitement. J'a v trouvé avt   . (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   . C'est stupide de dire ca . A quoi sert la montagne de chercheurs qui cherchent dans le domaine de la recherche operationnelle entre autre.  

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.

 
  Je ne vois pas ou je n'ai pas été courtois avec toi. C'est plutot mexx20 qui délire tout seul.   . 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  

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 !  

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.