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

¿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 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:
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(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:
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.
- El elemento estÔ incluido en la combinación actual.
- 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)


