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

⚔ Resumen inteligente

El algoritmo de combinación imprime todas las posibles selecciones de r elementos de un conjunto de n, donde el orden no importa. Este recurso explica la fórmula de combinación, la complejidad temporal, dos métodos recursivos, el manejo de duplicados y el código completo en C. C++, y Python implementaciones

  • šŸŽÆ Definición: Una combinación selecciona r elementos de un conjunto de n elementos, donde el orden de selección no importa.
  • 🧮 Fórmula: El nĆŗmero de combinaciones es nCr, igual a n! dividido por r!(nr)!.
  • šŸ” MĆ©todo 1: Una recursión de elemento fijo elige un elemento y luego encuentra combinaciones de los r-1 elementos restantes.
  • āž• MĆ©todo 2: Una recursión de inclusión-exclusión basada en la identidad de Pascal utiliza o omite cada elemento.
  • šŸ—‚ļø Duplicados: La ordenación o el uso de un diccionario elimina las combinaciones repetidas cuando la entrada contiene valores duplicados.

¿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:

Combinación de colores
Combinación de colores

Explicación:

  • Tome 4 colores de 5 y enumerelos
  • De cada bloque de 4 colores, elige 3 cualesquiera y enumĆ©ralos todos. Por ejemplo, en la figura solo elegimos ā€œRGBIā€ 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:
Fórmula de combinación

Fórmula de combinación

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,

Mixta

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(n2) 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 = En2) + O(nLog(n)). Podemos considerarlo O(n2), como norte2 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:

Elemento fijo con recursividad

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.

Apodo 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

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

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

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.

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

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

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

Utilizar un diccionario o un mapa no ordenado para track combinaciones duplicadas

Entonces, si no queremos ordenar los elementos para tracKing 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 >= 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).

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

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

Preguntas Frecuentes

Una combinación es una selección donde el orden no importa, por lo que RGB y BGR cuentan como uno. Una permutación es una disposición donde el orden importa, por lo que RGB y BGR cuentan como dos. Las combinaciones usan nCr; las permutaciones usan nPr.

nCr es el nĆŗmero de maneras de elegir r elementos de entre n elementos cuando el orden no importa. Se calcula como n! dividido por r! multiplicado por (nr)!. Por ejemplo, 5C3 es igual a 10.

Los algoritmos de combinación aparecen en las probabilidades de lotería, la selección de equipos o comités, la búsqueda de subconjuntos de características en el aprendizaje automÔtico, la generación de casos de prueba y el anÔlisis de contraseñas o espacios de claves. En cualquier situación donde se elija un grupo sin importar el orden, se aplican las combinaciones.

Las herramientas de IA pueden generar todas las combinaciones posibles de un conjunto de datos, filtrar duplicados e incluso sugerir el método mÔs eficiente para grandes volúmenes de datos. Esto ahorra tiempo, aunque conviene verificar el recuento con la fórmula nCr para comprobar su exactitud.

Sí. Los asistentes de codificación de IA pueden escribir código combinado en C, C++, Pythony otros lenguajes, incluidos los métodos recursivos y de inclusión-exclusión. Siempre compruebe el resultado y verifique los casos límite, como elementos duplicados o r mayor que n.

Resumir este post con: