Initiation à l'algorithmique

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

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

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :