Kombinationsalgorithmus: Drucken Sie alle möglichen Kombinationen von R

By: Sarah Chen Sarah Chen
Hours Aktualisiert

Was ist die Kombination?

Die Kombination ist eine Art Anordnung einiger gegebener Objekte. In mathematischen Begriffen ist eine Kombination eine Reihe von Auswahlmöglichkeiten/Auswahl von Elementen aus einer einzigartigen Menge von Elementen/Objekten. Dabei spielt die Reihenfolge der Artikel keine Rolle. Es wird auch als Methode zur Berechnung des Gesamtergebnisses eines Ereignisses bezeichnet, bei der die Reihenfolge des Ergebnisses keine Rolle spielt.

Sie erhalten beispielsweise eine Tasche mit fünf verschiedenen Farben und werden gebeten, ein Muster mit drei beliebigen Farben zu erstellen. Sie können auch 5 beliebige Farben aus 3 auswählen und diese dann in unterschiedlicher Reihenfolge anordnen.

Nehmen wir an, die Farben seien RGYBI(R= Rot, G= Grün, Y= Gelb, B= Blau, I= Indigo). Das mögliche Muster kann also RGB, RGY usw. sein.

Schauen wir uns die folgende Abbildung an:

Farbkombination
Farbkombination

Erläuterung:

  • Nehmen Sie 4 beliebige Farben von 5 und listen Sie sie auf
  • Wählen Sie aus jedem Block mit 4 Farben drei beliebige aus und listen Sie sie alle auf. Beispielsweise haben wir in der Abbildung nur „RGBI“ ausgewählt und 3 Kombinationen angezeigt.
  • Dahinter steckt eine Theorie zur Berechnung der Gesamtzahl der Kombinationen, die wir machen können. Eine Kombination von r Elementen aus n kann mathematisch dargestellt werden als:
Formel der Kombination

Formel der Kombination

Das Schild "!" Bedeutet die Fakultät. Beispielsweise,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Sag mal, 5! = 5*4*3*2*1 = 120

Für unser obiges Problem haben wir also 5 Farben, was n = 5 bedeutet, und zu jedem Zeitpunkt müssen wir drei beliebige auswählen. Also ist r = 3. Nach der Berechnung erhalten wir:

Kombination

Für das obige Szenario sind insgesamt 10 Farbkombinationen möglich.

Die Zeitkomplexitätsanalyse für Kombination

Nehmen wir nun an, dass wir bei einem gegebenen Array der Größe n aufgefordert werden, r Elemente aus dem Array zu entnehmen und Kombinationen von r Elementen durchzuführen.

Wenn ein Array der Größe n angegeben wird, benötigt es O(n2) Zeit zum Ausführen der Aufgabe. Wenn wir außerdem den doppelten Eintrag entfernen möchten, dann

Wir müssen die folgenden Schritte durchführen:

Schritt 1) Sortieren Sie die Eingabearraydaten aufsteigend. Die Zeitkomplexität der Sortierung ist O(n*log(n)).

Schritt 2) Erstellen Sie aus den angegebenen temporären Array-Daten ein weiteres Array, das ein eindeutiges Element enthält.

Schritt 3) Führen Sie dann die Kombinationsfunktion aus.

Die gesamte Zeitkomplexität beträgt also = Auf2) + O(nLog(n)). Wir können es als O(n) betrachten2), als n2 ist viel größer als n*log(n).

Methode 1: Festes Element mit Rekursion

Bei dieser Methode wählen wir ein Element aus und finden dann eine Kombination aus r-1 Elementen. Wenn wir ein Element aus dem Rest des Elements auswählen, gehen wir rekursiv vor, und deshalb wird es festes Element und Rekursion genannt.

Lassen Sie uns den Algorithmus Schritt für Schritt anhand eines Diagramms demonstrieren:

Festes Element mit Rekursion

Die Schritte sind unten angegeben:

Schritt 1) Nehmen Sie in der ersten Ebene n-r+1 Elemente. Das heißt, wir haben 3 Elemente genommen.

Schritt 2) Wählen Sie ein Element aus der 2. Ebene und bringen Sie es bis Nr. Wenn wir also „R“ nehmen, können wir mit R G, Y und B nehmen.

Schritt 3) Wählen Sie ein Element aus der 3. Ebene aus, bringen Sie es zum n-ten Element und bilden Sie Blöcke mit jeweils 3 Elementen.

Die obige Abbildung ist der Rückgabewert der Rekursion. Es wird nur die letzte Ebene gedruckt.

Pseudocode

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

Implementierung in 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 & lt; r; i++) {
      printf("%c", combinationArray[i]);
    }
    printf("\n");
    return;
  }
  for (int i = start; i & lt; = end & amp; & amp; end - i + 1 & gt; = 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);
}

Ausgang:

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

Umsetzung in 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 & lt; = end and end - i + 1 & gt; = 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)

Ausgang:

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

ÄHNLICHE ARTIKEL

Methode 2 (Jedes Element einschließen und ausschließen)

Diese Methode basiert auf der Pascalschen Identität. Zuvor haben wir Rekursion zur Berechnung von nCr verwendet. Hier wird die Methode einfach aufgeteilt, anstatt einer komplexen Schleife.

Laut Pascals Identität

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

Es gibt also zwei rekursive Logiken für den rekursiven Algorithmus, um eine Kombination von r Elementen aus einem gegebenen Array der Größe n zu finden.

  1. Element ist in der aktuellen Kombination enthalten
  2. Element ist aus der aktuellen Kombination ausgeschlossen

Pseudocode

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)

Implementierung in 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 & lt; r; j++) {
      printf("%c", combinationArray[j]);
    }
    printf("\n");
    return;
  }
  if (i & gt; = 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);
}

Ausgang:

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

Umsetzung in Python

def Combination(inputArray, combinationArray, n, r, index, i):
    if index == r:
    for item in combinationArray:
    print(item, end = " ")
print()
return
if i & gt; = 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)

Ausgang:

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

Umgang mit doppelten Kombinationen

Manchmal kann es vorkommen, dass das Eingabearray doppelte Elemente enthält.

Zum Beispiel,

  • Das Eingabearray enthält n = {5, 2, 3, 1, 5}.
  • Hier können wir sehen, dass 5 zweimal vorhanden ist.
  • Wenn wir nun den Code für dieses Array ausführen möchten, werden einige Kombinationen wiederholt.
  • Wir finden {5, 2, 5}, {5, 2, 3} usw. oder jede Kombination, die 5 enthält, wird wiederholt.

Wir können diese beiden Methoden verwenden:

  • Sortieren Sie das Eingabearray. Das Sortieren dauert O(nlog(n)) Zeit.
  • Erhöhen Sie dann den Wert von i, während der i-Wert und der i+1-Wert gleich bleiben. Fügen Sie grundsätzlich die folgenden zwei Codezeilen in die Kombinationsfunktion ein.
// For c/c++
while(inputArray[i] == inputArray[i+1]){
  i++;
}

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

Verwenden eines Wörterbuchs oder einer ungeordneten Karte, um doppelte Kombinationen zu verfolgen

Wenn wir die Elemente also nicht sortieren möchten, um das Duplikat zu verfolgen, können wir die angegebenen Schritte befolgen.

Schritt 1) Deklarieren Sie ein globales Wörterbuch oder eine Hashmap.
Schritt 2) Schieben Sie die generierte Kombination in die Hashmap und erhöhen Sie den Wert um eins. Die Kombination ist der Schlüssel, und ihr Auftreten sind Werte.
Schritt 3) Wenn die Funktion fertig ist, drucken wir einfach alle Schlüssel aus der Hashmap oder dem Wörterbuch aus.

Hier ist die Implementierung in 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 & gt; = 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)

Ausgang: 

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

Hier können Sie sehen, dass die Eingabe „RGYBIB“ war. Im Allgemeinen sollte es einige doppelte Kombinationen geben. Da wir jedoch ein Wörterbuch verwendet und jede Kombination als Schlüssel behandelt haben, können wir nur die eindeutige Kombination drucken.

Wenn Sie nun „print(unique_combination)“ schreiben, können Sie die Häufigkeit jeder Kombination sehen. Es wird so angezeigt:

{'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}

Wir können also sehen, dass RGB, RYB und GYB 2 Mal aufgetreten sind. Die Zeitkomplexität beim Einfügen des Schlüssels in ein Wörterbuch beträgt im Wesentlichen O(1). Wenn Sie also ein Wörterbuch verwenden, beträgt die Gesamtzeitkomplexität zum Ausführen des Codes:

O(1) + O(n*n)

Entspricht O(n*n).

Wenn wir die vorherige Methode zum Verfolgen von Duplikaten verwenden, benötigen wir O(n*log(n)) zum Sortieren; zum Vergleichen benötigen wir O(n) und die Funktion selbst benötigt O(n*n). Die gesamte zeitliche Komplexität beträgt:

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