Lister tous les combinaisons de k elements

Signaler
Messages postés
2
Date d'inscription
dimanche 7 août 2005
Statut
Membre
Dernière intervention
4 août 2008
-
 manandpc -
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!

7 réponses

Messages postés
280
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
8 juillet 2014
5
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("\n");
}

int main() {
  int ens[] = {1,2,3,4,5,6};
  int combi[4];
  combinaison(ens,combi,6,4,0,0,afficher);
}
Messages postés
280
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
8 juillet 2014
5
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)
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
42
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
Messages postés
280
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
8 juillet 2014
5
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
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
42
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
Messages postés
280
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
8 juillet 2014
5
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+
Voici un programme de generation tres court et tres efficace :

#include <stdio.h>
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("\n");
} else { comb[++i] = comb[i - 1]; }
} else i--; } }