Afficher toutes les combinaisons possibles de k éléments dans un tableau donné de taille n
Afficher toutes les combinaisons possibles de k éléments dans un tableau donné de taille n
Étant donné un tableau de taille n, générer et afficher toutes les combinaisons possibles de k éléments.
Exemple :
tab[] = {1, 2, 3, 4} ; k=2
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} et{3, 4}
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4} et{3, 4}
Nous créons un tableau temporaire de "donnees[]" qui stocke toutes les sorties une par une.
L'idée est de commencer à partir du premier index (index = 0) dans donnees [], fixez l'éléments de cet index et répétons pour les index restants.
Soit le tableau en entrée {1, 2, 3, 4, 5} et k=3
Fixé 1 à l'index 0 dans donnees[], après remplire les indices restantes dans donnees[] puis fixé 2 à l'indice 0 dans donnees[] et remplire les indices restantes
finalement fixé 3.
Lorsque le nombre d'éléments dans les donnees[] devient égal à k (taille d'une combinaison), afficher donnees[].
L'idée est de commencer à partir du premier index (index = 0) dans donnees [], fixez l'éléments de cet index et répétons pour les index restants.
Soit le tableau en entrée {1, 2, 3, 4, 5} et k=3
Fixé 1 à l'index 0 dans donnees[], après remplire les indices restantes dans donnees[] puis fixé 2 à l'indice 0 dans donnees[] et remplire les indices restantes
finalement fixé 3.
Lorsque le nombre d'éléments dans les donnees[] devient égal à k (taille d'une combinaison), afficher donnees[].
def Combinaison(tab, donnees, debut, fin, courant, k): if (courant == k): for j in range(k): print(donnees[j], end=" ") print() return # la condition fin-i+1 >=k-courant s'assure que # l'inclusion d'un élément au "courant" # fera une combinaison avec les éléments restants # aux positions restantes i = debut while(i <= fin and fin - i + 1 >= k - courant): donnees[courant] = tab[i] Combinaison(tab, donnees, i + 1, fin, courant + 1, k) i += 1 tab = [1, 2, 3, 4, 5] k = 3 n = len(tab) donnees = [0]*k Combinaison(tab, donnees, 0, n - 1, 0, k)
Comment gérer les doublons?
Notez que la méthode ci-dessus ne gère pas les doublons. Par exemple, si le tableau d'entrée est {1, 2, 1} et k est égal à 2, le programme affiche {1, 2} et {2, 1} selon deux combinaisons différentes.
Nous pouvons éviter les doublons en ajoutant les deux éléments suivants au code ci-dessus.
- trier le tableau avant d'appeler Combinaison()
- Ajouter les lignes suivantes avant la fin de la boucle while dans Combinaison()
while tab[i] == tab[i+1] i++;
def Combinaison(tab, donnees, debut, fin, courant, k): if (courant == k): for j in range(k): print(donnees[j], end=" ") print() return # la condition fin-i+1 >=k-courant s'assure que # l'inclusion d'un élément au "courant" # fera une combinaison avec les éléments restants # aux positions restantes i = debut while(i <= fin and fin - i + 1 >= k - courant): donnees[courant] = tab[i] Combinaison(tab, donnees, i + 1, fin, courant + 1, k) while tab[i]==tab[i+1] i += 1
Partager ce cours avec tes amis :
Rédigé par
ESSADDOUKI
Mostafa