Différences

Ci-dessous, les différences entre deux révisions de la page.

--- combinaisons [2010/01/09 08:57]
tyrtamos
+++ combinaisons [2010/01/10 07:31]
tyrtamos
@@ Ligne 3: / Ligne 3: @@
 **//En construction//**
-Voir pour la définition (entre autres): [[http://fr.wikipedia.org/wiki/Combinaison_%28math%C3%A9matiques%29]]
+===== Objectif =====
-Par exemple, on cherche les combinaisons de 3 objets pris 2 à 2: %%['A','B','C']%% => %%[['A', 'B'], ['A', 'C'], ['B', 'C']]%%
+Exemple pour des combinaisons de 3 objets pris 2 à 2. Soit une liste d'objets [1,2,3]:
-Contrairement aux permutations, on ne tient pas compte de l'ordre: ainsi, ['A','B'] et ['B','A'] ne compte que pour 1.
+  * on veut connaitre toutes les façons de les présenter 2 à 2, sans tenir compte de l'ordre: %%[[1, 2], [1, 3], [2, 3]]%%,
-==== Nombre de combinaisons de n objets pris k à k ====
+  * en tenant compte si nécessaires de répétitions
+  * et on veut savoir combien  il y en a.
+NB: Contrairement aux permutations et aux arrangements, on ne tient pas compte de l'ordre: ainsi, [1, 2] et [2, 1] ne compte que pour 1.
+\\
+Référence externe pour la définition: voir [[http://fr.wikipedia.org/wiki/Combinaison_%28math%C3%A9matiques%29]] et [[http://fr.wikipedia.org/wiki/Combinaison_avec_r%C3%A9p%C3%A9tition]]
+===== Nombre de combinaisons de n objets pris k à k =====
 Le calcul du nombre de combinaisons de n objets pris k à k est donnée par la formule:
@@ Ligne 19: / Ligne 28: @@
 Cnk = fact(n)/(fact(k)*fact(n-k)) = n*(n-1)*(n-2)*...*(n-k+1)/fact(k)
-=== Solution non-récursive ===
+==== Solution non-récursive ====
 Puisque nous sommes sous Python qui sait calculer des nombres entiers énormes, nous pouvons utiliser brutalement les factorielles en prenant la fonction fact(n) présentée ailleurs sur ce site:
@@ Ligne 68: / Ligne 77: @@
 </code>
-=== Solution récursive ===
+==== Solution récursive ====
 La solution récursive est particulièrement simple:
@@ Ligne 150: / Ligne 159: @@
 A ne conserver que pour des considérations théoriques.
-==== Liste des combinaisons d'une liste de n objets pris k à k ====
+===== Liste des combinaisons d'une liste de n objets pris k à k =====
+Nous savons maintenant calculer le **nombre** de combinaisons, nous voulons maintenant en établir la **liste**.
-Par exemple, nous voulons trouver la liste de toutes les combinaisons de de 3 objets pris 2 à 2, qui est: %%[1,2,3]%% => %%[[1,2], [1,3], [2,3]]%%
+Par exemple, nous voulons trouver la liste de toutes les combinaisons de de 3 objets %%[1,2,3]%% pris 2 à 2, qui est:  %%[[1,2], [1,3], [2,3]]%%
-Nous allons reprendre tout simplement le principe de "l'ensemble des parties d'un ensemble" traité plus haut. Mais en limitant notre résultat au nombre k d'éléments voulue dans chaque partie.
+Nous allons reprendre tout simplement le principe de "l'ensemble des parties d'un ensemble" traité dans une autre page de ce site, mais en limitant notre résultat au nombre k d'éléments voulue dans chaque partie.
 Cela donnera comme code:
@@ Ligne 184: / Ligne 195: @@
 Comme vu précédemment, ces listes trouvées peuvent être triées.
-==== Liste des combinaisons d'une chaine de n caractères pris k à k ====
+===== Liste des combinaisons d'une chaine de n caractères pris k à k =====
-C'est le même principe, à part que la donnée est une chaîne de caractères, et qu'on cherche toutes les combinaisons de k caractères de cette chaîne de longueur n.
+C'est le même principe, à part que la donnée est une chaîne de n caractères, et qu'on cherche toutes les combinaisons des n caractères pris k à k.
 La solution la plus simple est d'utiliser la fonction précédente:
@@ Ligne 202: / Ligne 213: @@
 </code>
-==== Combinaisons avec répétition ====
+===== Combinaisons avec répétition =====
-Jusqu'à présent, on a considéré que les objets dont on voulait les combinaisons, étaient tous **distincts**, c'est à dire qu'ils n'apparaissaient qu'une seul fois dans la liste (comme [1,2,3], mais pas comme [1,2,2]. Maintenant, on va voir ce qu'on peut faire avec des répétitions.
+Jusqu'à présent, on a considéré que les objets dont on voulait les combinaisons, étaient tous **distincts**, c'est à dire qu'ils n'apparaissaient qu'une seul fois dans la liste (comme [1,2,3], mais pas comme [1,2,2]). Maintenant, on va voir ce qu'on peut faire avec des répétitions.
 Quand l'un des éléments au moins apparait plusieurs fois dans la liste des objets, il y a deux effets dans la liste des combinaisons.
-Par exemple dans les combinaisons de [1,2,2] pris 2 à 2 qui donne [[1, 2], [1, 2], [2, 2]]:
+Par exemple dans les combinaisons de [1,2,2] pris 2 à 2 qui donne %%[[1, 2], [1, 2], [2, 2]]%%:
   * présence de séquences contenant des répétitions. Ici: [2,2]

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page