lister tous les combinaisons de k elements

Question

bonjour,
j'ai besoin d'un programme qui liste toute les combinaisons possibles de taille  k  dans un ensemble de taille n.
Cnp {l'ensemble peut etre {1,2,...,n}}.
j'ai bessoin de ce code pour mon projet.
Merci d'avance pour l'aide!

acx01b · Accepted Answer

salut

j'espère que cette version récursive te plaira

void combinaisons(int *ens, int *combinaison, int n, int p, int i, int t, void (*func)(int*,int)) {
    if (i<p) {
        int k;
        for (k=t; k<n; k++) {
            combinaison[i] = ens[k];
            combinaisons(ens,combinaison,n,p,i+1,k+1,func);
        }
    }
    else {
        func(combinaison,p);
    }
}

void afficher( int *p, int n) {
  int i;
  for (i = 0; i < n; i++) printf("%d ", p[i]);
  printf("
");
}

int main() {
  int ens[] = {1,2,3,4,5,6};
  int combi[4];
  combinaison(ens,combi,6,4,0,0,afficher);
}

acx01b · Answer

sinon la plus jolie version serait plutôt celle ci:

void combi2(int *ens, int *cmb, int n, int p , int i, int k, void (*func)(int*,int)) {
    if (k == p) func(cmb,p);
    else if (i < n) {
        combi2(ens,cmb,n,p,i+1,k,func);
        cmb[k] = ens[i];
        combi2(ens,cmb,n,p,i+1,k+1,func);
    }
}

qui implémente la formule C(n+1,p+1) = C(n,p) + C(n,p+1)

coucou747 · Answer

Salut

C(n+1,p+1) = C(n,p) + C(n,p+1) //pascal ?

sinon, t'as le droit de sortir plusieurs fois la meme lettre ?

(si le code precedent convient, merci de le valider, histoire que je ne le fasse pas pour rien...)

<hr />une recherche sur exalead vous aurait peut-etre evite de poser cette question

In a dream, I saw me, drop dead...
U were there, U cried...
It was just a dream,
if I die, U won't cry, maybe, U'll be happy

acx01b · Answer

salut coucou47

oui mon code convient pour les combinaisons :)

par définition l'ensemble (int * ens) ne contient pas de répétition

la combinaison n'en contiendra pas non plus

coucou747 · Answer

Salut

ce que je veux dire, c'est que les mots de 3 lettres faisables avec a b c, t'as pas que :

abc
acb
bac
cab
cba
bca

t'as aussi :
aab
aba
baa
...

il veut peut-etre recuperer aussi ceux la... ou peut-etre au contraire, ne pas lister deux mots qui contiennent les memes lettres
alors pour des mots de 2 lettres pour a, b, c t'aurais

ab
ac
bc

<hr />une recherche sur exalead vous aurait peut-etre evite de poser cette question

In a dream, I saw me, drop dead...
U were there, U cried...
It was just a dream,
if I die, U won't cry, maybe, U'll be happy

acx01b · Answer

salut

en combinatoire:

mot (liste)
arrangement 
combinaison 
combinaison avec répétition (k-combinaison, sélection, distribution)
partition
partage
permutation

ont tous des sens bien précis

a+

manandpc · Answer

Voici un programme de generation tres court et tres efficace : #include void main(int argc, char *argv[]) { const int n 5; const int k 3; int comb[40] = {0}; int i = 0; while (i >= 0) { if (comb[i] < n + i - k + 1) { comb[i]++; if (i == k - 1) { for (int j = 0; j < k; j++) printf("%d ", comb[j]); printf(" "); } else { comb[++i] = comb[i - 1]; } } else i--; } }

Lister tous les combinaisons de k elements

7 réponses

Votre réponse

Discussions similaires