Initiation à l'algorithmique

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}

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[].
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 Mostafa Sedoki
Computer science teacher and the founder of the e-learning platform "developpement-informatique.com", my mission is to provide high-quality courses for free to all computer science students and teachers

Cours Similaires :