Afficher toutes les combinaisons possibles de k éléments dans un tableau donné de taille n

Do you want to read our courses in English? please visit our new website cs-teachers.com Click here

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 M. ESSADDOUKI

Many people realize their hearts desires late in life. Continue learning, never stop striving and keep your curiosity sharp, and you will never become too old to appreciate life.

0 Commentaire(s)

Pour laisser un commentaire vous devez avoir un compte Inscription, ou Se connecter