Accueil / Combinatoire / Combinatoire Permutations / Algorithmes

Combinaisons de k éléments d'un ensemble fini de n éléments
Exemples d'algorithmes et de programmes C

sous-ensemble

Définition et propriétés

1) On appelle combinaison de k éléments d'un ensemble fini E de n éléments, tout sous-ensemble A de k éléments de E.
Pour les ensembles ayant un nombre fini d'éléments, "combinaison" est donc synonyme de sous-ensemble et aussi de partie.
2) Le nombre de combinaisons de p éléments d'un ensemble de n éléments est , il se trouve à la ligne n et à la colonne p du triangle de Pascal, il est le coefficient de x^p dans le développement de et pour cette raison est souvent noté binomial(n, p). Certaines calculatrices le notent nCp. La notation mathématique est , (après avoir écrit \[\binom n p\] en LaTeX afin d'obtenir l'image).

Quelques algorithmes et programmes C

Ensemble des combinaisons de p éléments parmi n

Algorithme récursif.
fonction combinaisons(Liste L, Liste F, k) {
   si k supérieur au nombre d'éléments de F {
        quitter
   } sinon si k est égal à 0, {
        afficher  L
   } sinon {
        pour tous les éléments x de l'ensemble F  {
             Liste G = les éléments de F placés après x dans L
             Liste L2  = L plus x
                         (on a concaténé x à la droite de la liste L)
             combinaisons(L2, G , k-1)
        }
}

combinaisons("", (1,2,3,4,5,6), 3);

Un programme comb.c écrit en C calcule toutes les combinaisons dans un tableau d'entiers de taille Cnp × p pour qu'on puisse en faire ce qu'on veut ensuite. Toutefois, si on veut juste afficher les combinaisons ou les envoyer à un autre programme au fur et à mesure de leur création, le programme simplifié comb2.c suffira.
exemple :
    aven:~/comb\> comb 6 3
    {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 2, 6}, {1, 3, 4}, {1, 3, 5}, {1, 3, 6}, {1, 4, 5}, 
    {1, 4, 6}, {1, 5, 6}, {2, 3, 4}, {2, 3, 5}, {2, 3, 6}, {2, 4, 5}, {2, 4, 6}, {2, 5, 6}, 
    {3, 4, 5}, {3, 4, 6}, {3, 5, 6}, {4, 5, 6},
    aven:~/comb\>


Construction d'une ou de plusieurs combinaisons à la fois

Choix aléatoires

L'application javascript ci-dessous permet d'obtenir au hasard une combinaison de k éléments de [1 n], à chaque tirage toutes les combinaisons ont même probabilité d'apparition.
Le programme C alea2comb.c permet d'obtenir au hasard (équiprobabilité) une ou plusieurs combinaisons de k éléments de [1 n]. Les combinaisons obtenues successivement sont toutes indépendantes les unes des autres, (dans les limites du bon vouloir du générateur de nombres pseudo-aléatoires).
alea2comb 12 6 3
2 5 7 8 9 10
2 3 6 9 11 12
1 4 7 8 10 11
L'algorithme récursif utilisé par le programme C est le suivant
fonction combinaisonAleatoire(n, p)   
   si (n ≤ 0 ou p ≤ 0 ou n < p ) { 
	quitter
   }
   si (alea < p/n) {        // alea est un nbre aléatoire entre 0 et 1
   	combinaisonAleatoire(n - 1, p - 1);
        écrire  n
   } sinon {
   	combinaisonAleatoire(n - 1, p);
   }
}
L'algorithme non récursif
fonction combinaisonAleatoire(n, p)
  tant que n ≥ p et p ≥ 0   {
          si (alea < p/n) {
              écrire n
              p = p-1
          }
          n = n-1
  }
}

Combinaisons repérées par des numéros

Combinaison de rang donné

Les combinaisons de k éléments de [1 n] peuvent être mises en bijection avec les entiers naturels de 0 à binomial(n, k)-1.
L'application javascript ci-dessous vous donne la combinaison connaissant n, k et le numéro.
De même le programme C index2comb.c permet d'obtenir les combinaisons qui correspondent aux numéros (précédés par les valeurs de n et de k)
index2comb 12 6  5 6 7
12 11 10 9 8 2
12 11 10 9 8 1
12 11 10 9 7 6
L'algorithme est très proche du précédent, la version récursive est la suivante
fonction combinaison(n, p, rang) {
        Si (rang<0 ou n<=0 ou p<=0) quitter
        b = binomial(n-1, p-1);
        si (rang < b) {
                combinaison(n-1, p-1, rang);
		écrire n;
        } sinon {
                combinaison(n-1, p, rang-b);
        }
}
La version non récursive est aussi simple (lire le programme C).

Index ou rang d'une combinaison

Le programme C comb2index.c vous permet inversement de retrouver le numéro de la combinaison. (Donner les valeurs de n puis de la combinaison, on obtient n k et le numéro).
Les programmes C de cette page sont sous licence GPL de The GNU Operating System.
comb2index 12  7 5 4 2 1
12 5 783
L'algorithme (non récursif) est le suivant
fonction rangDeLaCombinaison(n, combinaison) {
	p=0
	rang = 0
        Pour tout x de 1 à n { 
               si x est élément de la combinaison  
			p = p+1
               sinon 
			rang  = rang + binomial(x-1, p-1)
        }
        retourner le rang
}

Application javascript


n k         

        



Sous-ensembles finis de N*

Les exemples précédents concernaient les sous-ensembles d'un ensemble fini.
Cette fois on va construire très simplement une bijection entre l'ensemble des sous-ensembles finis de N* = {1, 2, 3, 4, ...} et l'ensemble N. (N et N* ne sont pas finis).

Dans la première application, vous fournissez un entier naturel quelconque et vous obtenez en retour un sous-ensemble fini de N*.
Inversement, dans la seconde application, vous fournissez un sous-ensemble fini de N* et vous obtenez un nombre entier naturel.
Ces deux bijections sont réciproques.
Sous-ensembles finis de N*
1) Un entier naturel :   n =         



2) Un sous-ensemble de N* :   E =         





L'algorithme utilisé est très simple : il suffit de considérer les bijections entre 1) un nombre entier et son écriture binaire 2) une écriture binaire et un sous-ensemble de N*.
Un exemple suffira, je crois, à tout expliquer :
n=57 (base dix) <---> n=111001 (base deux) <---> E={1, 4, 5, 6} (qui sont les rangs des chiffres 1 de 111001 en partant de la droite)

Pour éviter toute confusion : ci-dessus l'ensemble des parties finies de N* est mis en bijection avec N, on aurait de même pu mettre en bijection l'ensemble des parties finies de N avec N. Mais il n'existe pas de bijection entre N et l'ensemble des parties (finies ou infinies) de N (ni non plus avec celles de N*).

Combinaisons

Voir la page Combinaisons.


D'autres pages sont consacrées aux nombres de permutations, combinaisons et arrangements aux nombres de Catalan ainsi qu'à d'autres suites de nombres entiers naturels.

Accueil / Combinatoire / Combinatoire Permutations / Algorithmes

















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014