Génération de toutes les combinaisons possibles de k éléments
Une combinaison est une sélection d'éléments sans tenir compte de l'ordre. Étant donné un tableau de taille n, nous souhaitons générer et afficher toutes les combinaisons possibles de k éléments.
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.
tab = [1, 2, 3, 4] k = 2
{1, 2}
{1, 3}
{1, 4}
{2, 3}
{2, 4}
{3, 4}Nous créons un tableau temporaire "donnees[]" qui stocke toutes les combinaisons une par une.
L'idée est de commencer à partir du premier index (index = 0) dans donnees[], fixer l'élément de cet index et répéter pour les index restants.
- Fixer 1 à l'index 0 dans donnees[], puis remplir les indices restants dans donnees[]
- Fixer 2 à l'index 0 dans donnees[], puis remplir les indices restants
- Fixer 3 à l'index 0 dans donnees[], puis remplir les indices restants
- Lorsque le nombre d'éléments dans donnees[] devient égal à k (taille d'une combinaison), afficher donnees[].
fonction Combinaison(tab, donnees, debut, fin, courant, k):
si courant == k:
afficher(donnees)
retourner
i = debut
tant que i <= fin ET (fin - i + 1) >= (k - courant):
donnees[courant] = tab[i]
Combinaison(tab, donnees, i + 1, fin, courant + 1, k)
i = i + 1La condition fin - i + 1 >= k - courant s'assure que l'inclusion de l'élément à la position "courant" permettra de former une combinaison avec les éléments restants.
def Combinaison(tab, donnees, debut, fin, courant, k):
"""
Génère récursivement toutes les combinaisons de k éléments
Paramètres:
tab: tableau d'entrée
donnees: tableau temporaire pour stocker une combinaison
debut: index de départ dans tab
fin: dernier index dans tab
courant: index courant dans donnees
k: taille des combinaisons recherchées
"""
if courant == k:
# Afficher la combinaison courante
for j in range(k):
print(donnees[j], end=" ")
print()
return
i = debut
# La condition fin - i + 1 >= k - courant s'assure qu'il reste assez d'éléments
# pour compléter la combinaison
while i <= fin and fin - i + 1 >= k - courant:
donnees[courant] = tab[i]
Combinaison(tab, donnees, i + 1, fin, courant + 1, k)
i += 1
# Exemple d'utilisation
tab = [1, 2, 3, 4, 5]
k = 3
n = len(tab)
donnees = [0] * k
print(f"Toutes les combinaisons de {k} éléments dans {tab} :")
Combinaison(tab, donnees, 0, n - 1, 0, k)1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
Gestion des doublons dans les combinaisons
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} comme deux combinaisons différentes, alors qu'elles sont identiques.
tab = [1, 2, 1] k = 2
{1, 2}
{2, 1}Nous pouvons éviter les doublons en ajoutant deux améliorations au code précédent :
- Trier le tableau avant d'appeler Combinaison()
- Sauter les éléments dupliqués dans la boucle while
Pour éviter les doublons, on ajoute une boucle qui saute les éléments identiques :
fonction Combinaison(tab, donnees, debut, fin, courant, k):
si courant == k:
afficher(donnees)
retourner
i = debut
tant que i <= fin ET (fin - i + 1) >= (k - courant):
donnees[courant] = tab[i]
Combinaison(tab, donnees, i + 1, fin, courant + 1, k)
tant que i < fin ET tab[i] == tab[i+1]:
i = i + 1 # sauter les éléments dupliqués
i = i + 1def Combinaison_sans_doublons(tab, donnees, debut, fin, courant, k):
"""
Génère toutes les combinaisons de k éléments sans doublons
"""
if courant == k:
for j in range(k):
print(donnees[j], end=" ")
print()
return
i = debut
while i <= fin and fin - i + 1 >= k - courant:
donnees[courant] = tab[i]
Combinaison_sans_doublons(tab, donnees, i + 1, fin, courant + 1, k)
# Sauter les éléments dupliqués
while i < fin and tab[i] == tab[i + 1]:
i += 1
i += 1
# Exemple avec doublons
tab = [1, 2, 1, 2]
k = 2
n = len(tab)
donnees = [0] * k
# Étape 1: Trier le tableau
tab.sort()
print(f"Toutes les combinaisons uniques de {k} éléments dans {tab} :")
Combinaison_sans_doublons(tab, donnees, 0, n - 1, 0, k)1 2 1 2 1 2
- Une combinaison est une sélection d'éléments sans considération d'ordre.
- La génération de combinaisons se fait naturellement par récursivité.
- On utilise un tableau temporaire pour construire chaque combinaison.
- La condition
fin - i + 1 >= k - courantoptimise la recherche en évitant les branches impossibles. - Pour éviter les doublons, il faut :
- Trier le tableau initial
- Sauter les éléments identiques lors de la récursion
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.