Algorytm kombinacji: Wydrukuj wszystkie możliwe kombinacje R

Jaka jest kombinacja?

Kombinacja to rodzaj uporządkowania pewnych danych obiektów. W kategoriach matematycznych kombinacja to zbiór wyborów/wybór elementów z unikalnego zestawu elementów/przedmiotów. Tutaj kolejność elementów nie ma znaczenia. Jest również znana jako metoda obliczania całkowitego wyniku zdarzenia, gdzie kolejność wyników nie ma znaczenia.

Na przykład dostajesz torbę w 5 różnych kolorach i zostajesz poproszony o wygenerowanie wzoru z dowolnymi 3 kolorami. Możesz także wybrać dowolne 3 kolory z 4, a następnie ułożyć je w różnej kolejności.

Załóżmy, że kolory to RGYBI(R=czerwony, G=zielony, Y=żółty, B=niebieski, I=indygo). Zatem możliwym wzorem może być RGB, RGY itp.

Przyjrzyjmy się poniższemu rysunkowi:

Wyjaśnienie:

Wybierz dowolne 4 kolory z 5 i wypisz je
Z każdego bloku 4 kolorów wybierz dowolne 3 i wypisz je wszystkie. Na przykład wybraliśmy na rysunku tylko „RGBI” i pokazaliśmy 4 kombinacje.
Kryje się za tym teoria obliczająca całkowitą liczbę kombinacji, jakie możemy wykonać. Kombinację r elementów z n można matematycznie przedstawić jako:

Znak „!” oznacza Factorial, Na przykład,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Powiedz 5! = 5*4*3*2*1 = 120

Zatem dla naszego powyższego problemu mamy 5 kolorów, co oznacza n = 5 i w dowolnym momencie musimy wybrać dowolne 3. Zatem r = 3. Po obliczeniu otrzymujemy:

W powyższym scenariuszu możliwych jest łącznie 10 kombinacji kolorów.

Analiza złożoności czasowej dla kombinacji

Załóżmy teraz, że mając tablicę o rozmiarze n, jesteśmy proszeni o pobranie r elementów z tablicy i wykonanie kombinacji r elementów.

Jeśli podana jest tablica o rozmiarze n, to zajmie ona O(n²) czas na wykonanie zadania. Ponadto, jeśli chcemy usunąć zduplikowany wpis, to:

Musimy wykonać następujące kroki:

Krok 1) Sortuj dane wejściowe tablicy w sposób rosnący. Złożoność czasowa sortowania wynosi O(n*log(n)).

Krok 2) Utwórz kolejną tablicę zawierającą unikalny element z podanych tymczasowych danych tablicy.

Krok 3) Następnie wykonaj funkcję kombinacji.

Całkowita złożoność czasowa wynosi zatem = Na²) + O(nLog(n)). Możemy to rozważyć O(n²), jak n²jest znacznie większe niż n*log(n).

Metoda 1: Naprawiono element z rekurencją

W tej metodzie wybierzemy element, a następnie znajdziemy kombinację elementów r-1. Gdy wybieramy element z reszty elementu, robimy to rekurencyjnie i dlatego nazywa się to elementem stałym i rekurencją.

Zademonstrujmy algorytm krok po kroku za pomocą diagramu:

Kroki podano poniżej:

Krok 1) W pierwszej warstwie weź elementy n-r+1. Oznacza to, że wzięliśmy 3 elementy.

Krok 2) Wybierz element z drugiej warstwy i przenieś go na nr. Zatem, jeśli weźmiemy „R”, to za pomocą R możemy wziąć G, Y i B.

Krok 3) Wybierz element z trzeciej warstwy i przenieś go do n-tego elementu i uformuj bloki zawierające po 3 elementy każdy.

Powyższy rysunek przedstawia wartość zwracaną przez rekurencję. Wydrukowana zostanie tylko ostatnia warstwa.

Pseudo kod

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

Implementacja w 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);
}

Wyjście:

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

wdrożenie w 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)

Wyjście:

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

Metoda 2 (uwzględnij i wyklucz każdy element)

Ta metoda opiera się na tożsamości Pascala. Wcześniej używaliśmy rekurencji do obliczania nCr. Tutaj metoda jest po prostu dzielona zamiast złożonej pętli.

Według tożsamości Pascala,

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

Zatem algorytm rekurencyjny będzie mógł znaleźć 2 logikę rekurencyjną w celu znalezienia kombinacji r elementów z danej tablicy o rozmiarze n.

Element jest zawarty w bieżącej Kombinacji
Element jest wykluczony z bieżącej Kombinacji

Pseudo kod

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)

Implementacja w 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);
}

Wyjście:

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

wdrożenie w 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)

Wyjście:

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

Obsługa zduplikowanych kombinacji

Czasami w tablicy wejściowej mogą znajdować się zduplikowane elementy.

Na przykład,

Tablica wejściowa zawiera n = {5, 2, 3, 1, 5}.
Tutaj widzimy, że 5 występuje 2 razy.
Teraz, jeśli chcemy uruchomić kod dla tej tablicy, niektóre kombinacje zostaną powtórzone.
Znajdziemy {5, 2, 5}, {5, 2, 3} itd. lub dowolna kombinacja zawierająca 5 zostanie powtórzona.

Możemy zastosować te dwie metody:

Sortuj tablicę wejściową. Sortowanie zajmie czas O(nlog(n)).
Następnie zwiększ wartość i, podczas gdy wartość i i wartość i+1 są takie same. Zasadniczo umieść następujące dwa wiersze kodu w funkcji Combination.

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

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

Używanie słownika lub nieuporządkowanej mapy do śledzenia zduplikowanych kombinacji

Jeśli więc nie chcemy sortować elementów w celu śledzenia duplikatu, możemy wykonać podane kroki.

Krok 1) Zadeklaruj globalny słownik lub hashmapę.
Krok 2) Wciśnij wygenerowaną kombinację do mapy mieszającej i zwiększ wartość o jeden. Kombinacja jest kluczem, a ich występowanie wartościami.
Krok 3) kiedy funkcja zakończy działanie, po prostu wydrukujemy wszystkie klucze z mapy mieszającej lub słownika.

Oto implementacja w Pythonie

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)

Wyjście:

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

Tutaj widać, że wprowadzone dane brzmiały „RGYBIB”. Ogólnie rzecz biorąc, powinno wystąpić kilka zduplikowanych kombinacji. Ponieważ jednak korzystaliśmy ze słownika i traktowaliśmy każdą kombinację jako klucz, możemy wydrukować tylko unikalną kombinację.

Teraz, jeśli napiszesz „print(unique_combination)”, możesz zobaczyć częstotliwość każdej kombinacji. Pokaże się tak:

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

Widzimy więc, że RGB, RYB, GYB wystąpiły 2 razy. Złożoność czasowa wstawiania klucza do słownika wynosi zasadniczo O(1). Tak więc, jeśli używasz słownika, całkowita złożoność czasowa uruchomienia kodu będzie wynosić:

O(1) + O(n*n)

Odpowiednik O(n*n).

Używając poprzedniej metody śledzenia duplikatów, potrzebujemy O(n*log(n)) do sortowania; do porównywania potrzebujemy O(n), a sama funkcja przyjmuje O(n*n). Całkowita złożoność czasowa wyniesie:

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

Możesz lubić:

Jaka jest kombinacja?

Analiza złożoności czasowej dla kombinacji

Metoda 1: Naprawiono element z rekurencją

Pseudo kod

Implementacja w C/C++

wdrożenie w Python

POWIĄZANE ARTYKUŁY

Metoda 2 (uwzględnij i wyklucz każdy element)

Pseudo kod

Implementacja w C/C++

wdrożenie w Python

Obsługa zduplikowanych kombinacji

Używanie słownika lub nieuporządkowanej mapy do śledzenia zduplikowanych kombinacji

Oto implementacja w Pythonie