Programme : combinatoires

[totio94]

Bonsoir,

Ne m'y connaissant pas trop en programmation et débutant en mathématique, je viens demander un peu d'aide concernant un court programme que j'aimerai me faire ! (Je ne demande pas une réponse toute faite, juste un peu d'aide pour comprendre comment m'y prendre, car je ferai le programme avec mon prof de math, c'est juste histoire de comprendre ! :-)).

Donc, j'ai récemment appris les combinatoires en math et j'en ai une utilisation particulière. Je prends des cours de math particulier pour m'améliorer en musique (oui oui, vraiment !) et je me sert de la formule de combinatoire pour connaître le nombre d'harmonisation de gamme possible.

J'aimerai un programme qui, quand j'entre une formule de combinatoire, admettons C9-4 (Ici pour faire des accords de 4 notes, avec une gamme de 9 notes), le programme me liste toute les possibilités, plutôt que simplement le nombre de possibilités.

Comment ça va se passer au niveau programmation ? N'hésitez pas à me poser des questions si vous comprenez pas trop ce que je veux dire.

Merci ! :-)

[fatal_error]

slt,

pour prendre 4 notes parmi 9, c'est simple.
Tu ordonnes tes notes
do re mi ...si (supposons que yen ai 9)

Tu fais :

Code: Tout sélectionner

pour i=1 à 9 //la premiere note
 pour j=i+1 a 9//la deuxieme note
  pour k=j+1 a 9//la troisieme note
   pour l=k+1 a 9 //la quatrieme note
     afficherAccord(i,j,k,l)
   finpour
 finpour
finpour

ca se complique un peu si tu veux faire C(n,k) au lieu de C(9,4), mais l'idée est la même

[fatal_error]

petit défi pour les enfermés du mauvais temps du weekend, la version récursive, est assez immédiate.

Quid de la version itérative?

[totio94]

Salut !
Merci pour ton aide Fatal Error !
Donc là, si je rentre ces lignes dans mon tableur, ça va me sortir une réponse pour un accord au hasard c'est bien ça ?
Quel va être la fonction qui va faire en sorte qu'il me liste toute les possibilités ?

Par contre pour ton défi, je ne serai répondre, qu'est-ce que la version récursive et la version itérative ? Désolé de mon ignorance et encore, merci beaucoup pour l'aide ! :-)

[fatal_error]

si tu écris une phrase en francais dans ton tableau, il n'en fera rien.

Il n'en fera pas plus avec le bout de pseudo code que je t'ai proposé.

Je t'ai simplement donné un algorithme permettant de lister toutes les combinaisons de 4 notes dans ta gamme à 9 notes.

Maintenant, il faut pas trop croire à la magie.

1) tu écris les algorithmes
2) tu les transcris dans un langage que peut comprendre ton tableur!

-------------------
Enfin, il n'était pas question de prendre un accord au hasard, mais de lister les accords possibles dans la gamme. C'est différent.

[totio94]

D'accord, je vais essayer de voir par rapport à ça ce que je peux en faire. Merci bien !

[LeJeu]

petit défi pour les enfermés du mauvais temps du weekend, la version récursive, est assez immédiate.

Quid de la version itérative?

J'étais au soleil ce week-end, j'ai attendu le retour dans le grand froid pour répondre, ci-joint un codage "itératif"
( sans variable globale , fatal-error !)

Code: Tout sélectionner


// Calcul de C(n,k) sans récursion
#define k 4
#define n 9
#define max_stack k+1

void main(void)

{
int indice[max_stack];
int i=0;

   // init
   for ( i = 0; i =0; i--)
         if (indice[i] < n -k +i)
            break;
      
      indice[i]++;

      //Réinitialisation de tous les chiffres à droite de i
      for (i++; i<=k; i++)
         indice[i]= indice[i-1]+1;
   }
}


quelqu'un a plus simple ? plus compact ?

[fatal_error]

intelligent cette numérotation!
moi je m'étais contenté de simuler "grossomodo" la pile du compilo.

[fatal_error]

en fait avec ta solution, c'est dommage de chercher à chaque fois le chiffre après chaque solution.

Avec la mienne, c'est dommage de tester à chaque fois si ya une solution.
(voici le code quand même (c'est du javascript)

Code: Tout sélectionner

function list(k, n , arr){
  if(k==1){
    for(var i=0;i o+1 _ | _
        var unpopped=false;
        while(!unpopped){
          stack.pop();//1 _ _ | _
          if(stack.length==0){//we popped everything, time to leave
            return;
          }
          var val = stack[stack.length-1];// o _ _ | _: 1
          var nbLeftIter = k - stack.length;
          if(nbLeftIter + val+1<n){//we add random number as well!
            stack[stack.length-1]++;
            unpopped = true;
          }
        }
      }
    }else{// _ | _: case of adding incremented
      //we can increment next stack: 1 2 _ | _
      stack.push(stack[stack.length-1]+1);
    }
  }
 
  console.log('fail to recurse '+increment);
}


)


j'intuite qu'on peut s'en sortir à coup de modulo/divisions!

[LeJeu]

en fait avec ta solution, c'est dommage de chercher à chaque fois le chiffre après chaque solution.

dans une premiere version j'avais codé
[CODE]
if (++indice[k] > n)
{
for (i=k-1; i>=0; i--)
if (indice[i] n)

[LeJeu]

j'intuite qu'on peut s'en sortir à coup de modulo/divisions!

J'ai un truc ... en base n - k + 1...

exemple : C (4,6) on cherche les combinaisons :
1 2 3 4
1 2 3 5
1 2 3 6
1 2 4 6
....
3 4 5 6

en retirant k à la kieme colonne on cherche :
0 0 0 0
0 0 0 1
0 0 0 2
0 0 1 1
...
2 2 2 2

ca ressemble beaucoup à la suite des nombres en bases 3
en sautant certains , cad en sautant ceux qui ont une suite de deux chiffres avec celui de droite supérieur à celui de gauche
exemple 0 0 1 0

on regarde donc l'écriture en base 3 des nombres inférieur à 3^4, et on retire les nombres non conformes....

ci dessous un implé en C

Code: Tout sélectionner

void main(void)
{
int indice[max_stack];
int i, max,nb, reste,chiffre,pos,base,ok;
   
   base = n-k+1;

   [COLOR=DarkGreen]// calcule de base ^k[/COLOR]
   for (max=1, i=0;i0 ; pos++,reste = reste /base )
      {
         chiffre = reste %base;
   
         if (pos>0 && (chiffre > indice[k-pos]))
         {
            ok =false;
            break;
         }
         else
            indice[k-1-pos]=chiffre;
      }   
      if ( ok)
      {
         [COLOR=DarkGreen]//impression  de la solution [/COLOR]
         for (i = 0; i< k;i++)
            printf("% d",indice[i] + i +1 );
         printf ("\n");
      }
   }
}

[joel76]

C'est quand même plus simple en Prolog (SWI-Prolog) :

Code: Tout sélectionner

:- use_module(library(clpfd)).

toutes_les_combi(M, N, L) :-
    bagof(Combi, combi(M, N, Combi), L).

 combi(M, N, Combi) :-
    length(Combi, N),
    Combi ins 1..M,
   chain(Combi, #<),
    label(Combi).

[Valentin03]

Bonjour tous,
Fatal Error si tu passe par là.
Ce serait super de pouvoir changer la taille de la combinaison depuis l'extérieur du prog.
Par deux belles variables...Sans doute ce que tu appelle: C(n,k)

Tu a l'air de dire que ce serait possible en récursif, je serais preneur du pseudo-code.
Ou le pseudo-code de vos versions itératives. (on est pas à quatre lignes près, c'est pas moi qui les executes).
Merci d'avance.
PS: Ton algo récursif est un plaisir.

[fatal_error]

hello Valentin03

Ce serait super de pouvoir changer la taille de la combinaison depuis l'extérieur du prog.

ben effectivement, c'est une fonction, donc les parametres sont modifiables. C'est egalement le cas des codes de lejeu.
Si tu veux l'appeler depuis lexterieur, ben il suffit de binder(argc,argv en C/C++, etc)

Tu a l'air de dire que ce serait possible en récursif, je serais preneur du pseudo-code

oui c'est trivial.
Dans les grandes lignes:

Code: Tout sélectionner

combi(k,n, depth, currentHand, beg)
 si depth==k
  //on a une solution
  afficher currentHand
 else
   for(int i=beg+1, i<n, i++){
     currentHand[depth] = i;
     combi(k,n, depth+1, currentHand, i);
   }
 finsi
finfunc

Code: Tout sélectionner

Ou le pseudo-code de vos versions itératives. (on est pas à quatre lignes près, c'est pas moi qui les executes).


la premiere version de leJeu est claire.
Mon code est pas trse comphensible a premiere vue, jessairai de le commenter plus tard

PS: Ton algo récursif est un plaisir.

on a propose des iteratifs :lol3:

[Valentin03]

Je te remercie. Je vais essayer vos deux productions. .
Mais pour la: "Le jeu", un pseudo-code serait plus parlant.
Je vois venir de la boucle infinie. ma pénitence régulière..

[fatal_error]

mm code commenté :

Code: Tout sélectionner

/**
 k: entier > 1
 n: entier > k
 arr: tableau de taille n

 affiche toutes les combinaisons de k elem pris dans arr
*/
function list(k, n , arr){
  if(k==1){
    for(var i=0;i 123x -> 124 ?
      stack.pop();
      if(stack[stack.length-1]+1  126x -> 127...
       
        //on cherche le premier digit en partant de la droite qu'on peut
        //incrémenter
        var unpopped=false;
        while(!unpopped){
          stack.pop();
          //si la pile est vide, c'est qu'on pouvait plus
          //rien incrémenter, on a fini, donc on quitte
          if(stack.length==0){
            return;
          }
         
          var val = stack[stack.length-1];
          var nbLeftIter = k - stack.length;
         
          //si on peut incrémenter le digit, alors on l'incrémente
          //et on boucle
          if(nbLeftIter + val+1123
      stack.push(stack[stack.length-1]+1);
    }
  }
 
  console.log('fail to recurse '+increment);
}

note: on peut optimiser la pile par un tableau de taille k, et une variable depth qu'on incremente quand on push dans le tableau et qu'on decremente quand on le pop.

Il n'y a pas non plus besoin de reinitialiser les chiffres "d'apres"

[fatal_error]

@lejeu,

apres coup je sais pas si on peut faire mieux que ce que tu as proposé comme premier code (ou avec le petit correctif). Si on considère qu'une boucle for c'est plein de if, en fait, avoir deux boucles for ou un gros while et un if, ca change pas grand chose!

Du coup, par exemple y aller a coup de modulo c'est ptet même plus couteux que des ifs!

Je pense que ta première version est meilleure que ta base n-k+1, ainsi que ce que je propose. Il faudrait mesurer, pe ce we je m'y attelerai.

[LeJeu]

@lejeu,

apres coup je sais pas si on peut faire mieux que ce que tu as proposé comme premier code (ou avec le petit correctif). Si on considère qu'une boucle for c'est plein de if, en fait, avoir deux boucles for ou un gros while et un if, ca change pas grand chose!

Du coup, par exemple y aller a coup de modulo c'est ptet même plus couteux que des ifs!

Je pense que ta première version est meilleure que ta base n-k+1, ainsi que ce que je propose. Il faudrait mesurer, pe ce we je m'y attelerai.

je suis d'accord, la base n-k+1 n'a pas donné tout ce que j'espèrais ....

sinon en passant, on doit avoir la propriété que tout programme récursif s'écrit de façon itérative, tu connais une façon formelle de transformer une écriture récursive en itérative ? c'est ce que tu as utilisé ? tu es partie d'une écriture récursive que tu as transformée , ou tu as "vu" direct ce que tu voulais pusher/poper?

je ne sais pas si ma question est très claire ....

[edit] par contre pour mesurer l'efficacité des trois programmes il va falloir taper loin dans les n pour avoir quelque chose de mesurable, ou bien alors demander à Dzilogic de nous prêter son vieil ordi 64k 1Hhtz

sinon je mise
1) ma version itérative
2) ta version push pop (mais match serré)
3) ma version base exotique

[fatal_error]

tu connais une façon formelle de transformer une écriture récursive en itérative

en cherchant sur le net, on trouve des papiers ou même ca peut s'énoncer en un paragraphe. Mais comme je suis bête, j'ai retenu que le résultat, pas la démo . chez stack elle était donnée.

tu es partie d'une écriture récursive que tu as transformée , ou tu as "vu" direct ce que tu voulais pusher/poper?

Je suis parti de l'algo récursif, et j'ai bidouillé avec les indices, c'est pas vraiment méthodique, c'est plus "guidé" par la notion de pile à utiliser.

[Valentin03]

Pfioou. L'itératif, ça crains.
Comme je n'ai besoin que de cinq valeurs de n
Je vais mettre cinq récursifs made by Fatal-Error avec les branchements qui vont bien.
Parce que vos algos de ouf me donnent des vapeurs.