Algoritmo de combinación: imprima todas las combinaciones posibles de R

¿Qué es la combinación?

La Combinación es una especie de disposición de algunos objetos determinados. En términos matemáticos, combinación es un conjunto de elecciones/selección de elementos de un conjunto único de elementos/objetos. Aquí el orden de los artículos no importa. También se conoce como método para calcular el resultado total de un evento, donde el orden del resultado no importa.

Por ejemplo, te dan una bolsa con 5 colores diferentes y te piden que generes un patrón con 3 colores cualesquiera. También puedes elegir 3 colores de 4 y luego organizarlos en diferentes órdenes.

Supongamos que los colores son RGYBI (R= Rojo, G= Verde, Y= Amarillo, B= Azul, I= Índigo). Entonces, el patrón posible puede ser RGB, RGY, etc.

Veamos la siguiente figura:

Explicación:

• Tome 4 colores de 5 y enumerelos
• De cada bloque de 4 colores, elige 3 y enuméralos todos. Por ejemplo, solo elegimos "RGBI" en la figura y mostramos 4 combinaciones.
• Hay una teoría detrás para calcular el número total de combinaciones que podemos hacer. Una combinación de r elementos de n se puede presentar matemáticamente como:

La señal "!" significa el factorial. Por ejemplo,
¡NORTE! = N * (N-1) * (N-2) * … * 3 * 2 * 1
¡Di, 5! = 5*4*3*2*1 = 120

Entonces, para nuestro problema anterior, tenemos 5 colores, lo que significa n = 5, y en cualquier momento dado, debemos elegir 3 cualesquiera. Entonces, r = 3. Después de calcular, obtenemos,

Para el escenario anterior es posible un total de 10 combinaciones de colores.

El análisis de la complejidad temporal para la combinación

Ahora, digamos, dada una matriz de tamaño n, se nos pide que tomemos r elementos de la matriz y realicemos combinaciones de r elementos.

Si se da una matriz de tamaño n, entonces tomará O(n²) tiempo para realizar la tarea. Además, si queremos eliminar la entrada duplicada, entonces,

Necesitamos realizar los siguientes pasos:

Paso 1) Ordena los datos de la matriz de entrada de manera ascendente. La complejidad temporal de la ordenación es O(n*log(n)).

Paso 2) Cree otra matriz que contenga un elemento único a partir de los datos de la matriz temporal dada.

Paso 3) Luego, realice la función de combinación.

Por lo tanto, la complejidad temporal total se convierte en = En²) + O(nLog(n)). Podemos considerarlo O(n²), como norte² es mucho mayor que n*log(n).

Método 1: elemento fijo con recursividad

En este método, elegiremos un elemento y luego encontraremos una combinación de r-1 elementos. Cuando elegimos un elemento del resto del elemento, lo hacemos de forma recursiva, y por eso se llama elemento fijo y recursividad.

Demostremos el algoritmo paso a paso con un diagrama:

Los pasos se dan a continuación:

Paso 1) En la primera capa, tome n-r+1 elementos. Es decir, tomamos 3 elementos.

Paso 2) Elija un elemento de la segunda capa y llévelo hasta n-r. Entonces, si tomamos "R", entonces con R podemos tomar G, Y y B.

Paso 3) Elija un elemento de la tercera capa y llévelo hasta el enésimo elemento y forme bloques que contengan 3 elementos cada uno.

La figura anterior es el valor de retorno de la recursividad. Sólo se imprimirá la última capa.

Pseudocó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

Implantación en 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);
}

Salida:

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

Implementación en 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)

Salida:

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 y excluir todos los elementos)

Este método se basa en la identidad de Pascal. Anteriormente, utilizamos la recursión para calcular nCr. Aquí, el método simplemente se divide en lugar de un bucle complejo.

Según la identidad de Pascal,

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

Entonces, habrá 2 lógicas recursivas para que el algoritmo recursivo encuentre una combinación de r elementos de una matriz determinada de tamaño n.

1. El elemento está incluido en la combinación actual.
2. El elemento está excluido de la combinación actual.

Pseudocó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)

Implantación en 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);
}

Salida:

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

Implementación en 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)

Salida:

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

Manejo de combinaciones duplicadas

A veces puede haber elementos duplicados en la matriz de entrada.

Por ejemplo,

• La matriz de entrada contiene n = {5, 2, 3, 1, 5}.
• Aquí podemos ver que 5 está presente 2 veces.
• Ahora, si queremos ejecutar el código de esta matriz, se repetirán algunas combinaciones.
• Encontraremos {5, 2, 5}, {5, 2, 3} etc o cualquier combinación que contenga 5, se repetirá.

Podemos utilizar estos dos métodos:

• Ordena la matriz de entrada. La clasificación llevará O(nlog(n)) tiempo.
• Luego, aumenta el valor de i, mientras que el valor de i y el valor de i+1 sean iguales. Básicamente, coloca las siguientes dos líneas de código en la función Combinación.

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

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

Usar un diccionario o un mapa desordenado para rastrear combinaciones duplicadas

Entonces, si no queremos ordenar los elementos para rastrear el duplicado, podemos seguir los pasos indicados.

Paso 1) Declarar un diccionario global o hashmap.
Paso 2) Empuje la combinación generada al mapa hash y aumente el valor en uno. La combinación es la clave y su aparición son los valores.
Paso 3) Cuando la función termine de ejecutarse, simplemente imprimiremos todas las claves del hashmap o diccionario.

Aquí está la implementación en 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)

Salida:

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

Aquí puede ver que la entrada fue "RGYBIB". Generalmente, deberían ocurrir algunas combinaciones duplicadas. Pero como usamos un diccionario y tratamos cada combinación como clave, solo podemos imprimir la combinación única.

Ahora, si escribe "imprimir (combinación_única)", podrá ver la frecuencia de cada combinación. Se mostrará así:

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

Por lo tanto, podemos ver que RGB, RYB, GYB han ocurrido 2 veces. La complejidad temporal de insertar la clave en un diccionario es básicamente O(1). Por lo tanto, si utiliza un diccionario, la complejidad temporal total para ejecutar el código será:

O(1) + O(n*n)

Equivalente a O(n*n).

Si utilizamos el método anterior para rastrear duplicados, necesitamos O(n*log(n)) para ordenar; para comparar, necesitamos O(n), y la función en sí misma toma O(n*n). La complejidad temporal total será:

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