Combinaison avec répétition - Définition
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
La liste des auteurs de cet article est disponible ici.
- Première approche - Nombre de combinaisons avec répétition - Une autre représentation - Approche moins "matheuse" des combinaisons avec répétitions - Une troisième démonstration (ensembliste) - Algorithme efficace de génération des Combinaisons avec répétition - Algorithme itératif de génération des Combinaisons avec répétition
Algorithme itératif de génération des Combinaisons avec répétition
generer_k_combinaison(n,k): // k objets pris parmi n objets sans ordre et avec répétition declarer tab[n] <-- {k,0,0......} tant que tab[n] != k: afficher (tab) si tab[n] != 0 tmp <-- tab[n] tab[n] <-- 0 i <-- indice de la derniere case non nulle de tab tab[i] <-- tab[i] - 1 tab[i+1] <-- tmp + 1 sinon i <-- indice de la derniere case non nulle de tab tab[i] <-- tab[i] - 1 tab[i+1] <-- 1 fin si fin tant que afficher (tab) fin Une implémentation en C:
#include#include #define MAX 1024 int NB; void afficher(int *t, int l) { int i,j; for (i = 0; i < l; ++i) printf("%d ",t[i]); printf("[ "); for (i = 0; i < l; ++i) { for (j = 0; j < t[i]; ++j) { printf("%d ", i); } } printf("]\n"); ++NB; } void kcombinaison(int *t, int n, int p, void (*func)(int*,int)) { int tmp,i; t[0] = p; memset(t+1,0, sizeof *t * (n - 1)); while(t[n-1] != p) { func(t,n); tmp = t[n-1]; t[n-1] = 0; i = n-1; while(t[i] == 0) --i; --t[i]; t[i+1] = tmp + 1; } func(t,n); } int main() { int tab[MAX]; int n = 3, p = 4; // 4 objets pris parmi 3 NB = 0; kcombinaison(tab,n,p,afficher); printf("Le NOMBRE de facon de prendre %d objets parmi %d sans ordre et avec repetition est: \n C(%d,%d) = %d\n", p, n, n+p-1, p, NB); return 0; }
- Première approche - Nombre de combinaisons avec répétition - Une autre représentation - Approche moins "matheuse" des combinaisons avec répétitions - Une troisième démonstration (ensembliste) - Algorithme efficace de génération des Combinaisons avec répétition - Algorithme itératif de génération des Combinaisons avec répétition
