Algoritmo de combinação: imprima todas as combinações possíveis de R

Qual é a combinação?

A Combinação é uma espécie de arranjo de alguns objetos. Em termos matemáticos, Combinação é um conjunto de escolhas/seleções de itens de um conjunto único de itens/objetos. Aqui, a ordem dos itens não importa. Também é conhecido como método de cálculo do resultado total de um evento, onde a ordem do resultado não importa.

Por exemplo, você recebe uma sacola com 5 cores diferentes e pede para gerar um padrão com 3 cores quaisquer. Você também pode escolher 3 cores de 4 e organizá-las em ordens diferentes.

Vamos supor que as cores sejam RGYBI(R= Vermelho, G= Verde, Y= Amarelo, B= Azul, I= Índigo). Portanto, o padrão possível pode ser RGB, RGY, etc.

Vamos dar uma olhada na figura a seguir:

Explicação:

• Pegue 4 cores de 5 e liste-as
• De cada bloco de 4 cores, escolha 3 e liste todas elas. Por exemplo, escolhemos apenas “RGBI” na figura e mostramos 4 combinações.
• Existe uma teoria por trás disso para calcular o número total de combinações que podemos fazer. Uma combinação de r elementos de n pode ser apresentada matematicamente como:

O sinal "!" significa o fatorial. Por exemplo, a
N! =N * (N-1) * (N-2) *… * 3 * 2 * 1
Diga, 5! = 5*4*3*2*1 = 120

Portanto, para o nosso problema acima, temos 5 cores que significam n = 5 e, a qualquer momento, precisamos escolher qualquer 3. Portanto, r = 3. Após calcular, obtemos,

Um total de 10 combinações de cores são possíveis para o cenário acima.

A análise de complexidade de tempo para combinação

Agora, digamos que, dado um array de tamanho n, somos solicitados a pegar r elementos do array e realizar combinações de r elementos.

Se uma matriz de tamanho n for fornecida, será necessário O(n²) tempo para executar a tarefa. Além disso, se quisermos remover a entrada duplicada, então,

Precisamos realizar as seguintes etapas:

Passo 1) Classifique os dados da matriz de entrada em ordem crescente. A complexidade temporal da classificação é O(n*log(n)).

Passo 2) Crie outro array contendo um elemento exclusivo dos dados do array temporário fornecido.

Passo 3) Em seguida, execute a função de combinação.

Então, a complexidade total do tempo torna-se = Sobre²) + O(nLog(n)). Podemos considerá-lo O(n²), como n² é muito maior que n*log(n).

Método 1: elemento fixo com recursão

Neste método, escolheremos um elemento e encontraremos uma combinação de r-1 elementos. Como estamos escolhendo um elemento do resto do elemento, estamos fazendo de forma recursiva, e é por isso que é chamado de elemento fixo e recursão.

Vamos demonstrar o algoritmo passo a passo com um diagrama:

As etapas são dadas abaixo:

Passo 1) Na primeira camada, pegue n-r+1 elementos. Significa que pegamos 3 elementos.

Passo 2) Escolha um elemento da 2ª camada e leve-o até o nº. Então, se pegarmos “R”, então com R podemos pegar G, Y e B.

Passo 3) Escolha um elemento da 3ª camada e leve-o até o enésimo elemento, e forme blocos contendo 3 elementos cada.

A figura acima é o valor de retorno da recursão. Somente a última camada será impressa.

Pseudo-código

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

Implementação em 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);
}

Saída:

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

Implementação em 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)

Saída:

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étodo 2 (incluir e excluir todos os elementos)

Este método é baseado na identidade de Pascal. Anteriormente usávamos recursão para calcular nCr. Aqui, o método é apenas dividido em vez de um loop complexo.

De acordo com a identidade de Pascal,

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

Portanto, haverá 2 lógicas recursivas para o algoritmo recursivo encontrar uma combinação de r elementos de um determinado array de tamanho n.

1. O elemento está incluído na combinação atual
2. O elemento foi excluído da combinação atual

Pseudo-código

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)

Implementação em 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);
}

Saída:

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

Implementação em 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)

Saída:

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

Lidando com combinações duplicadas

Às vezes pode haver elementos duplicados na matriz de entrada.

Por exemplo, nos

• A matriz de entrada contém n = {5, 2, 3, 1, 5}.
• Aqui, podemos ver que 5 está presente 2 vezes.
• Agora, se quisermos executar o código deste array, algumas combinações serão repetidas.
• Encontraremos {5, 2, 5}, {5, 2, 3} etc ou qualquer combinação que contenha 5 será repetida.

Podemos usar estes dois métodos:

• Classifique a matriz de entrada. A classificação levará tempo O(nlog(n)).
• Em seguida, aumente o valor de i, enquanto o valor de i e o valor de i+1 são iguais. Basicamente, coloque as duas linhas de código a seguir na função Combination.

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

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

Usando um dicionário ou mapa não ordenado para rastrear combinações duplicadas

Portanto, se não quisermos classificar os elementos para rastrear a duplicata, podemos seguir os passos indicados.

Passo 1) Declare um dicionário global ou hashmap.
Passo 2) Envie a combinação gerada para o hashmap e aumente o valor em um. A combinação é a chave e sua ocorrência são valores.
Passo 3) quando a função terminar de ser executada, simplesmente imprimiremos todas as chaves do hashmap ou dicionário.

Aqui está a implementação em 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)

Saída:

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

Aqui, você pode ver que a entrada foi “RGYBIB”. Geralmente, devem ocorrer algumas combinações duplicadas. Mas como usamos um dicionário e tratamos cada Combinação como chave, podemos imprimir apenas a Combinação única.

Agora, se você escrever “print(unique_combination)”, poderá ver a frequência de cada combinação. Irá mostrar assim:

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

Assim, podemos ver que RGB, RYB, GYB ocorreram 2 vezes. A complexidade de tempo de inserção da chave em um dicionário é basicamente O(1). Portanto, se você usar um dicionário, a complexidade total de tempo para execução do código será:

O(1) + O(n*n)

Equivalente a O(n*n).

Usando o método anterior para rastrear duplicatas, precisamos de O(n*log(n)) para classificação; para comparar, precisamos de O(n), e a própria função leva O(n*n). A complexidade total do tempo será:

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