1. ¿Por qué la combinatoria es útil en algoritmos?
Un algoritmo suele tomar decisiones entre varias alternativas. La combinatoria permite estimar cuántas entradas, estados, recorridos o configuraciones puede tener que procesar.
Esta estimación ayuda a anticipar el tiempo de ejecución, el uso de memoria y la necesidad de aplicar estrategias más eficientes.
2. Espacio de búsqueda
El espacio de búsqueda es el conjunto de todas las posibilidades que un algoritmo podría examinar. Si cada una de n posiciones puede contener uno de k valores, el espacio tiene kn configuraciones.
Opciones independientes: kn
Por ejemplo, cadenas de longitud 8 sobre un alfabeto de 4 símbolos: 48 = 65 536.
3. Fuerza bruta
Un algoritmo de fuerza bruta prueba sistemáticamente todas las posibilidades. Es fácil de diseñar y puede servir como referencia para verificar soluciones, pero su costo puede crecer rápidamente.
Si debe revisar todas las permutaciones de n elementos, el número de candidatos es n!. Si revisa todos los subconjuntos, es 2n.
4. Ejemplo: generar subconjuntos
La siguiente función usa una decisión binaria para cada elemento: incluirlo o no incluirlo. Por eso genera exactamente 2n subconjuntos.
function subconjuntos(elementos) {
const resultado = [];
function construir(indice, actual) {
if (indice === elementos.length) {
resultado.push(actual.slice());
return;
}
construir(indice + 1, actual);
actual.push(elementos[indice]);
construir(indice + 1, actual);
actual.pop();
}
construir(0, []);
return resultado;
}
console.log(subconjuntos(["A", "B", "C"]));5. Poda de posibilidades
La poda evita continuar una rama cuando ya se sabe que no puede producir una solución válida. En lugar de recorrer todo el espacio de búsqueda, el algoritmo descarta partes completas.
La combinatoria permite comparar el tamaño teórico del espacio con la cantidad de configuraciones que realmente se visitan después de podar.
6. Conteo de operaciones
Para analizar un algoritmo se cuenta cuántas veces se ejecuta una operación importante. Si un bucle recorre n elementos, el conteo puede ser lineal; si se comparan todos los pares, puede ser cuadrático.
Todos los pares de n elementos: C(n, 2) = n(n - 1)/2.
Todos los ordenamientos: n!.
7. Programación dinámica
Muchos problemas combinatorios tienen subproblemas repetidos. La programación dinámica guarda sus resultados y evita resolverlos varias veces.
El conteo de caminos, la sucesión de Fibonacci y el cambio de monedas son ejemplos en los que una recurrencia permite construir soluciones de menor tamaño hasta llegar al caso solicitado.
8. Ejemplo: caminos en una cuadrícula
La cantidad de caminos hasta una celda puede obtenerse sumando los caminos que llegan desde arriba y desde la izquierda. La tabla de resultados es una representación del cálculo combinatorio.
function tablaDeCaminos(filas, columnas) {
const tabla = Array.from({ length: filas }, function () {
return Array(columnas).fill(1);
});
for (let f = 1; f < filas; f++) {
for (let c = 1; c < columnas; c++) {
tabla[f][c] = tabla[f - 1][c] + tabla[f][c - 1];
}
}
return tabla;
}
console.log(tablaDeCaminos(4, 5)[3][4]); // 359. Backtracking
El backtracking construye una solución paso a paso. Cuando una elección conduce a una situación inválida, deshace la elección y prueba otra alternativa.
Se utiliza para generar permutaciones, resolver laberintos, ubicar elementos con restricciones y explorar asignaciones.
10. Greedy y decisiones locales
Un algoritmo voraz elige en cada etapa la alternativa que parece mejor en ese momento. La combinatoria ayuda a estudiar cuántas decisiones posibles existen, pero la corrección requiere demostrar que las elecciones locales producen una solución global adecuada.
Cuando esa propiedad no se cumple, puede ser necesario explorar más configuraciones o aplicar programación dinámica.
11. Conteo de soluciones y optimización
En optimización combinatoria no siempre interesa enumerar todas las soluciones. Puede buscarse la mejor, una válida o el número de soluciones que cumplen una condición.
12. Complejidad combinatoria
Algunas funciones crecen con rapidez:
- Lineal: n.
- Polinómica: n2, n3.
- Exponencial: 2n.
- Factorial: n!.
Para tamaños pequeños una búsqueda exhaustiva puede ser aceptable; para tamaños mayores se necesitan restricciones, poda, aproximaciones o algoritmos especializados.
13. Comparar dos estrategias
Supongamos que una estrategia examina todos los subconjuntos y otra examina todas las permutaciones. El número de candidatos es 2n para la primera y n! para la segunda. La diferencia se vuelve muy grande al aumentar n.
function factorial(n) {
let resultado = 1;
for (let i = 2; i <= n; i++) resultado *= i;
return resultado;
}
for (let n = 1; n <= 8; n++) {
console.log(n, Math.pow(2, n), factorial(n));
}14. Simulación: crecimiento del espacio de búsqueda
Selecciona la cantidad de elementos y compara cuántos candidatos debe revisar una estrategia que genera subconjuntos, permutaciones o cadenas binarias.
15. Buenas prácticas
Al diseñar un algoritmo combinatorio conviene definir qué representa cada estado, establecer los casos iniciales, identificar decisiones repetidas, medir el tamaño del espacio de búsqueda y probar con entradas pequeñas.
También es importante separar la generación de candidatos de la validación de restricciones, porque así resulta más sencillo incorporar poda o memorización.
16. Resumen
La combinatoria permite estimar y organizar los espacios de búsqueda de los algoritmos. Subconjuntos, permutaciones, caminos y asignaciones generan cantidades diferentes de candidatos. La programación dinámica, el backtracking y la poda aprovechan esa estructura para reducir trabajo sin perder la corrección de la solución.