Algoritmo di combinazione: stampa tutte le possibili combinazioni di R

By: Sara Chen Sara Chen
Hours aggiornato

⚡ Riepilogo intelligente

L'algoritmo di combinazione stampa ogni possibile selezione di r elementi da un insieme di n, dove l'ordine non ha importanza. Questa risorsa spiega la formula di combinazione, la complessità temporale, due metodi ricorsivi, la gestione dei duplicati e il codice C completo. C++e Python implementazioni.

  • 🎯 Definizione: Una combinazione seleziona r elementi da n elementi, dove l'ordine di selezione non ha importanza.
  • 🧮 Formula: Il numero di combinazioni è nCr, pari a n! diviso per r!(nr)!.
  • 🔁 Metodo 1: Una ricorsione a elementi fissi seleziona un elemento, quindi trova le combinazioni dei restanti r-1 elementi.
  • ➕ Metodo 2: Una ricorsione di inclusione-esclusione basata sull'identità di Pascal utilizza o ignora ciascun elemento.
  • 🗂️ duplicati: L'ordinamento o un dizionario rimuovono le combinazioni ripetute quando l'input contiene valori duplicati.
Scopri di più

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:

Combinazione di colori
Combinazione di colori

Spiegazione:

  • Prendi 4 colori qualsiasi su 5 ed elencali
  • Da ogni blocco di 4 colori, scegline 3 e elencale tutte. Ad esempio, nella figura abbiamo scelto solo "RGBI" e 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:
Formula di combinazione

Formula di combinazione

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:

pelle mista

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(n2) 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 = Sopra2) + O(nLog(n)). Possiamo considerarlo O(n2), come n2 è 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:

Elemento fisso con ricorsione

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.

Soprannome 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

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

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

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

ARTICOLI CORRELATI

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

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

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

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 >= 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 track combinazioni duplicate

Quindi, se non vogliamo ordinare gli elementi per tracper duplicare il contenuto, 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 >= 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 track duplicati, per l'ordinamento è necessario O(n*log(n)); per il confronto è necessario O(n), e la funzione stessa richiede O(n*n). La complessità temporale totale sarà:

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

DOMANDE FREQUENTI

Una combinazione è una selezione in cui l'ordine non ha importanza, quindi RGB e BGR contano come uno. Una permutazione è una disposizione in cui l'ordine è importante, quindi RGB e BGR contano come due. Le combinazioni utilizzano nCr; le permutazioni utilizzano nPr.

nCr è il numero di modi per scegliere r elementi da n elementi quando l'ordine non ha importanza. Si calcola dividendo n! per r! e moltiplicando per (nr)!. Ad esempio, 5C3 è uguale a 10.

Gli algoritmi di combinazione compaiono nelle probabilità della lotteria, nella selezione di squadre o comitati, nella ricerca di sottoinsiemi di caratteristiche nell'apprendimento automatico, nella generazione di casi di test e nell'analisi dello spazio delle password o delle chiavi. Ovunque si scelga un gruppo senza preoccuparsi dell'ordine, si applicano le combinazioni.

Gli strumenti di intelligenza artificiale possono generare tutte le combinazioni di un set di dati, filtrare i duplicati e persino suggerire il metodo più efficiente per input di grandi dimensioni. Ciò consente di risparmiare tempo, sebbene sia necessario verificare la correttezza del conteggio confrontandolo con la formula nCr.

Sì. Gli assistenti di programmazione AI possono scrivere codice combinato in C, C++, Pythone altri linguaggi, inclusi i metodi ricorsivi e di inclusione-esclusione. Testare sempre l'output e verificare i casi limite come elementi duplicati o r maggiore di n.

Riassumi questo post con: