Algoritmo di combinazione: stampa tutte le possibili combinazioni di R

Qual è la combinazione?

La Combinazione è una sorta di disposizione di alcuni oggetti dati. In termini matematici, la Combinazione è un insieme di scelte/selezione di elementi da un insieme unico di elementi/oggetti. Qui l'ordine degli articoli non ha importanza. È noto anche come metodo per calcolare il risultato totale di un evento, in cui l'ordine del risultato non ha importanza.

Ad esempio, ti viene data una borsa con 5 colori diversi e ti viene chiesto di generare un motivo con 3 colori qualsiasi. Puoi anche scegliere 3 colori qualsiasi su 4, quindi disporli in ordini diversi.

Supponiamo che i colori siano RGYBI(R= Rosso, G= Verde, Y= Giallo, B= Blu, I= Indaco). Quindi, il modello possibile può essere RGB, RGY, ecc.

Diamo un'occhiata alla figura seguente:

Spiegazione:

• Prendi 4 colori qualsiasi su 5 ed elencali
• Da ogni blocco di 4 colori, scegline 3 ed elencali tutti. Ad esempio, nella figura abbiamo selezionato solo "RGBI" e abbiamo mostrato 4 combinazioni.
• Dietro c'è una teoria per calcolare il numero totale di combinazioni che possiamo realizzare. Una combinazione di r elementi su n può essere matematicamente presentata come:

il segno "!" significa che fattoriale. Per esempio,
N! = N * (N-1) * (N-2) * … * 3 * 2 * 1
Diciamo 5! = 5*4*3*2*1 = 120

Quindi, per il nostro problema di cui sopra, abbiamo 5 colori che significano n = 5 e, in qualsiasi momento, dobbiamo sceglierne 3 qualsiasi. Quindi, r = 3. Dopo il calcolo, otteniamo:

Per lo scenario sopra riportato sono possibili un totale di 10 combinazioni di colori.

Analisi della complessità temporale per la combinazione

Ora, supponiamo che, dato un array di dimensione n, ci venga chiesto di prendere r elementi dall'array ed eseguire combinazioni di r elementi.

Se viene fornito un array di dimensione n, allora occorrerà O(n²) tempo per eseguire l'attività. Inoltre, se vogliamo rimuovere la voce duplicata, allora,

Dobbiamo eseguire i seguenti passaggi:

Passo 1) Ordina i dati dell'array di input in modo ascendente. La complessità temporale dell'ordinamento è O(n*log(n)).

Passo 2) Crea un altro array contenente un elemento univoco dai dati dell'array temporaneo fornito.

Passo 3) Quindi, eseguire la funzione di combinazione.

Quindi, la complessità temporale totale diventa = Sopra²) + O(nLog(n)). Possiamo considerarlo O(n²), come n² è molto più grande di n*log(n).

Metodo 1: elemento fisso con ricorsione

In questo metodo, sceglieremo un elemento e poi troveremo una combinazione di r-1 elementi. Poiché selezioniamo un elemento dal resto dell'elemento, lo facciamo in modo ricorsivo, ed è per questo che si chiama elemento fisso e ricorsione.

Dimostriamo l'algoritmo passo dopo passo con un diagramma:

I passaggi sono indicati di seguito:

Passo 1) Nel primo strato, prendi n-r+1 elementi. Ciò significa che abbiamo preso 3 elementi.

Passo 2) Scegli un elemento dal 2° strato e portalo al nr. Quindi, se prendiamo “R”, allora con R possiamo prendere G, Y e B.

Passo 3) Scegli un elemento dal 3° strato e portalo fino all'ennesimo elemento e forma blocchi contenenti 3 elementi ciascuno.

La figura sopra è il valore restituito dalla ricorsione. Verrà stampato solo l'ultimo strato.

Pseudo codice

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

Implementazione 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);
}

Produzione:

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

implementazione 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)

Produzione:

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

Metodo 2 (Includi ed escludi ogni elemento)

Questo metodo si basa sull'identità di Pascal. In precedenza abbiamo utilizzato la ricorsione per calcolare nCr. Qui, il metodo è semplicemente diviso invece di un ciclo complesso.

Secondo l'identità di Pascal,

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

Quindi, ci saranno 2 logiche ricorsive affinché l'algoritmo ricorsivo trovi una combinazione di r elementi da un dato array di dimensione n.

1. L'elemento è incluso nella combinazione corrente
2. L'elemento è escluso dalla combinazione corrente

Pseudo codice

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)

Implementazione 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);
}

Produzione:

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

implementazione 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)

Produzione:

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

Gestione delle combinazioni duplicate

A volte potrebbero esserci elementi duplicati nell'array di input.

Per esempio,

• L'array di input contiene n = {5, 2, 3, 1, 5}.
• Qui possiamo vedere che 5 è presente per 2 volte.
• Ora, se vogliamo eseguire il codice per questo array, verranno ripetute alcune combinazioni.
• Troveremo {5, 2, 5}, {5, 2, 3} ecc. oppure qualsiasi combinazione che contenga 5 verrà ripetuta.

Possiamo utilizzare questi due metodi:

• Ordina l'array di input. L'ordinamento richiederà tempo O(nlog(n)).
• Quindi aumenta il valore di i, mentre il valore i e il valore i+1 sono uguali. In pratica inserisci le seguenti due righe di codice nella funzione Combination.

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

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

Utilizzando un dizionario o una mappa non ordinata per tenere traccia delle combinazioni duplicate

Quindi, se non vogliamo ordinare gli elementi per tracciare il duplicato, possiamo seguire i passaggi indicati.

Passo 1) Dichiarare un dizionario globale o una hashmap.
Passo 2) Spingi la combinazione generata sull'hashmap e aumenta il valore di uno. La combinazione è la chiave e la loro occorrenza sono valori.
Passo 3) una volta terminata l'esecuzione della funzione, stamperemo semplicemente tutte le chiavi dall'hashmap o dal dizionario.

Ecco l'implementazione 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)

Produzione:

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

Qui puoi vedere che l'input era "RGYBIB". In generale, dovrebbero verificarsi alcune combinazioni duplicate. Ma poiché abbiamo utilizzato un dizionario e abbiamo trattato ciascuna combinazione come chiave, possiamo stampare solo la combinazione univoca.

Ora, se scrivi "print(unique_combination)", puoi vedere la frequenza di ciascuna combinazione. Verrà visualizzato in questo modo:

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

Quindi, possiamo vedere che RGB, RYB, GYB si sono verificati 2 volte. La complessità temporale dell'inserimento della chiave in un dizionario è fondamentalmente O(1). Quindi, se si utilizza un dizionario, la complessità temporale totale per l'esecuzione del codice sarà:

O(1) + O(n*n)

Equivalente a O(n*n).

Utilizzando il metodo precedente per tracciare i duplicati, abbiamo bisogno di O(n*log(n)) per l'ordinamento; per il confronto, abbiamo bisogno di O(n), e la funzione stessa accetta O(n*n). La complessità temporale totale sarà:

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