Algorithme de combinaison : imprimer toutes les combinaisons possibles de R

Quelle est la combinaison ?

La combinaison est une sorte d’arrangement de certains objets donnés. En termes mathématiques, la combinaison est un ensemble de choix/sélection d’éléments parmi un ensemble unique d’éléments/objets. Ici, l’ordre des éléments n’a pas d’importance. Cette méthode est également connue pour calculer le résultat total d'un événement, où l'ordre du résultat n'a pas d'importance.

Par exemple, on vous donne un sac avec 5 couleurs différentes et on vous demande de générer un motif avec 3 couleurs au choix. Vous pouvez également choisir 3 couleurs parmi 4, puis les disposer dans des ordres différents.

Supposons que les couleurs soient RGYBI (R= Rouge, G= Vert, Y= Jaune, B= Bleu, I= Indigo). Ainsi, le motif possible peut être RVB, RGY, etc.

Regardons la figure suivante :

Explication:

• Prenez 4 couleurs sur 5 et listez-les
• Dans chaque bloc de 4 couleurs, choisissez-en 3 et listez-les toutes. Par exemple, nous avons uniquement choisi « RGBI » dans la figure et présenté 4 combinaisons.
• Il y a une théorie derrière cela pour calculer le nombre total de combinaisons que nous pouvons faire. Une combinaison de r éléments sur n peut être mathématiquement présentée comme :

Le signe "!" signifie le factoriel. Par exemple,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Dis, 5 ! = 5*4*3*2*1 = 120

Donc, pour notre problème ci-dessus, nous avons 5 couleurs signifiant n = 5, et à tout moment, nous devons en choisir 3. Donc, r = 3. Après le calcul, nous obtenons,

Un total de 10 combinaisons de couleurs est possible pour le scénario ci-dessus.

L'analyse de complexité temporelle pour la combinaison

Maintenant, disons que, étant donné un tableau de taille n, on nous demande de prendre r éléments du tableau et d'effectuer des combinaisons de r éléments.

Si un tableau de taille n est donné, alors il faudra O(n²) le temps d'effectuer la tâche. De plus, si nous voulons supprimer l'entrée en double, alors,

Nous devons effectuer les étapes suivantes :

Étape 1) Triez les données du tableau d’entrée par ordre croissant. La complexité temporelle du tri est O(n*log(n)).

Étape 2) Créez un autre tableau contenant un élément unique à partir des données du tableau temporaire données.

Étape 3) Ensuite, exécutez la fonction de combinaison.

Ainsi, la complexité temporelle totale devient = Sur²) + O(nLog(n)). On peut le considérer O(n²), comme n² est beaucoup plus grand que n*log(n).

Méthode 1 : élément fixe avec récursivité

Dans cette méthode, nous choisirons un élément puis trouverons une combinaison d’éléments r-1. Lorsque nous sélectionnons un élément dans le reste de l'élément, nous le faisons de manière récursive, et c'est pourquoi cela est appelé élément fixe et récursion.

Montrons l'algorithme étape par étape avec un diagramme :

Les étapes sont indiquées ci-dessous :

Étape 1) Dans la première couche, prenez n-r+1 éléments. Cela signifie que nous avons pris 3 éléments.

Étape 2) Choisissez un élément de la 2ème couche et montez-le au n°. Donc, si nous prenons « R », alors avec R, nous pouvons prendre G, Y et B.

Étape 3) Choisissez un élément de la 3ème couche et amenez-le jusqu'au nième élément, et formez des blocs contenant 3 éléments chacun.

Le chiffre ci-dessus est la valeur de retour de la récursion. Seule la dernière couche sera imprimée.

Faux Code

function combination:
pass in: inputArray, combinationArray, start, end, index, r
if index is equal to r:
for each element in combinationArray:
print each element
return
for i = start:
if i <=end and end -i+1 > r-index:
combinationArray[index] = inputArray[i]
call combination function again with updated parameter

Implémentation en C/C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int start, int end, int index, int r) {
  if (index == r) {
    for (int i = 0; i < r; i++) {
      printf("%c", combinationArray[i]);
    }
    printf("\n");
    return;
  }
  for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
    combinationArray[index] = inputArray[i];
    Combination(inputArray, combinationArray, i + 1, end, index + 1, r);
  }
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, 0, n - 1, 0, r);
}

Sortie :

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

Mise en œuvre dans Python

def Combination(inputArray, combinationArray, start, end, index, r):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
i = start
while (i <= end and end - i + 1 >= r - index):
    combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, i + 1, end, index + 1, r)
i += 1
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [0] * r
Combination(inputArray, combinationArray, 0, n - 1, 0, r)

Sortie :

R G Y
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

Méthode 2 (inclure et exclure chaque élément)

Cette méthode est basée sur l'identité de Pascal. Auparavant, nous utilisions la récursivité pour calculer le nCr. Ici, la méthode est simplement divisée au lieu d’une boucle complexe.

D'après l'identité de Pascal,

nCr = (n-1)Cr + (n-1)C(r-1)

Ainsi, il y aura 2 logiques récursives pour que l'algorithme récursif trouve une combinaison de r éléments d'un tableau donné de taille n.

1. L'élément est inclus dans la combinaison actuelle
2. L'élément est exclu de la combinaison actuelle

Faux Code

function combination:
pass in: inputArray, combinationArray, n, r, index, i
if the index is equal to r:
for each element in combination array:
print each element
if i>=n:
return
  combinationArray[index] = inputArray[i]
  combination(inputArray, combinationArray, n, r, index+1, i+1)
  combination(inputArray, combinationArray, n, r, index, i+1)

Implémentation en C/C++

#include<bits/stdc++.h>
#include<stdio.h>
void Combination(char inputArray[], char combinationArray[], int n, int r, int index, int i) {
  if (index == r) {
    for (int j = 0; j < r; j++) {
      printf("%c", combinationArray[j]);
    }
    printf("\n");
    return;
  }
  if (i >= n)
    return;
  combinationArray[index] = inputArray[i];
  Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
  Combination(inputArray, combinationArray, n, r, index, i + 1);
}
int main() {
  char inputArray[] = {'R','G','Y','B','I'};
  int n = sizeof(inputArray) / sizeof(inputArray[0]);
  int r = 3;
  char combinationArray[r];
  printf("Combinations:\n");
  Combination(inputArray, combinationArray, n, r, 0, 0);
}

Sortie :

Combinations:
RGY
RGB
RGI
RYB
RYI
RBI
GYB
GYI
GBI
YBI

Mise en œuvre dans Python

def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
if i >= n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBI"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)

Sortie :

R G Y
R G B
R G I
R Y B
R Y I
R B I
G Y B
G Y I
G B I
Y B I

Gestion des combinaisons en double

Parfois, il peut y avoir des éléments en double dans le tableau d'entrée.

Par exemple,

• Le tableau d'entrée contient n = {5, 2, 3, 1, 5}.
• Ici, nous pouvons voir que 5 est présent 2 fois.
• Maintenant, si nous voulons exécuter le code de ce tableau, certaines combinaisons seront répétées.
• Nous trouverons {5, 2, 5}, {5, 2, 3} etc. ou toute combinaison contenant 5 sera répétée.

Nous pouvons utiliser ces deux méthodes :

• Triez le tableau d'entrée. Le tri prendra un temps O(nlog(n)).
• Augmentez ensuite la valeur de i, tandis que la valeur i et la valeur i+1 sont identiques. Fondamentalement, mettez les deux lignes de code suivantes dans la fonction Combinaison.

// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

# for python
  while inputArray[i]==inputArray[i+1]:
    i+=1

Utiliser un dictionnaire ou une carte non ordonnée pour track combinaisons en double

Donc, si nous ne voulons pas trier les éléments pour tracPour obtenir le doublon, nous pouvons suivre les étapes indiquées.

Étape 1) Déclarez un dictionnaire global ou une hashmap.
Étape 2) Poussez la combinaison générée vers la table de hachage et augmentez la valeur de un. La combinaison est la clé et leurs occurrences sont des valeurs.
Étape 3) lorsque la fonction aura fini de s'exécuter, nous imprimerons simplement toutes les clés du hashmap ou du dictionnaire.

Voici l'implémentation en python

unique_combination = dict()
def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    temp_combination = ""
for item in combinationArray:
    temp_combination += item
unique_combination[temp_combination] = unique_combination.get(temp_combination, 0) + 1
return
if i >= n:
    return
combinationArray[index] = inputArray[i]
Combination(inputArray, combinationArray, n, r, index + 1, i + 1);
Combination(inputArray, combinationArray, n, r, index, i + 1);
inputArray = "RGYBIB"
n = len(inputArray)
r = 3
combinationArray = [""] * r
Combination(inputArray, combinationArray, n, r, 0, 0)
for item in unique_combination.keys():
    print(item)

Sortie :

RGY
RGB
RGI
RYB
RYI
RBI
RBB
RIB
GYB
GYI
GBI
GBB
GIB
YBI
YBB
YIB
BIB

Ici, vous pouvez voir que l'entrée était « RGYBIB ». En général, il devrait y avoir des combinaisons en double. Mais comme nous avons utilisé un dictionnaire et traité chaque combinaison comme la clé, nous ne pouvons imprimer que la combinaison unique.

Maintenant, si vous écrivez « print(unique_combination) », vous pouvez voir la fréquence de chaque combinaison. Cela s'affichera comme ceci :

{'RGY': 1, 'RGB': 2, 'RGI': 1, 'RYB': 2, 'RYI': 1, 'RBI': 1, 'RBB': 1, 'RIB': 1, 'GYB': 2, 'GYI': 1, 'GBI': 1, 'GBB': 1, 'GIB': 1, 'YBI': 1, 'YBB': 1, 'YIB': 1, 'BIB': 1}

Ainsi, nous pouvons voir que RGB, RYB, GYB se sont produits 2 fois. La complexité temporelle de l'insertion de la clé dans un dictionnaire est essentiellement O(1). Ainsi, si vous utilisez un dictionnaire, la complexité temporelle totale d'exécution du code sera :

O(1) + O(n*n)

Équivalent à O(n*n).

En utilisant la méthode précédente pour tracPour k doublons, le tri nécessite O(n*log(n)) ; la comparaison, O(n) ; et la fonction elle-même a une complexité temporelle de O(n*n). La complexité temporelle totale sera :

O(n*log(n)) + O(n) +O(n*n)

FAQ