Combinatoria con recursivos: Combine Tools

Combinatoria: Combine Tools

   
Muestras
El primer valor son las iteraciones y el segundo es el resultado de la fórmula, debiendo cumplir la fórmula del coste.
Configuración
La función para copiar Arrays puede afectar al tiempo de ejecución. Puede cambiar el método de copia en la configuración. La función copy2() se utiliza en los algoritmos de partición.
let copyMethod = "slice";
function copy(arr=[]) {
    if (copyMethod==="slice") {
        return arr.slice(0);
    } else if (copyMethod==="map") {
        return arr.map(v => v);
    } else if (copyMethod==="concat") {
        return [].concat(arr);
    } else if (copyMethod==="spread"){
        return [...arr];
    } else if (copyMethod==="json") {
        return JSON.parse(JSON.stringify(arr));
    } else if (copyMethod==="loop") {
        let arrCopy = [];
        for (let i=0; i<arr.length; i++){
            arrCopy[i] = arr[i];
        }
        return arrCopy;
    } else {
        return arr;
    }
}
function copy2(arr=[[]]) {
    if (copyMethod==="slice") {
        return arr.slice(0).map(v => v.slice(0));
    } else if (copyMethod==="map") {
        return arr.map(v => v.map(w => w));
    } else if (copyMethod==="concat") {
        return [].concat(arr).map(v => [].concat(v));
    } else if (copyMethod==="spread"){
        return [...arr].map(v => [...v]);
    } else if (copyMethod==="json") {
        return JSON.parse(JSON.stringify(arr));
    } else if (copyMethod==="loop") {
        let arrCopy = [];
        for (let i=0; i<arr.length; i++){
            arrCopy[i] = [];
            for (let j=0; j<arr[i].length; j++) {
                arrCopy[i].push(arr[i][j]);
            }
        }
        return arrCopy;
    } else {
        return arr;
    }
}
Vista del resultado

Combinaciones

Las combinaciones de una lista con n elementos son todas las sublistas con k elementos distintos que se pueden extraer sin importar el orden. Se denotan como (nk), C(n, k) y también como Cn,k.

Número de sublistas:
C(n, k) =n!
k!(n-k)!
Base matemática:
C(n, k) = C(n-1, k-1) + C(n-1, k)
Sublistas generadas:
Tiempo:
Iteraciones: (Sin coste de copia)
Coste calculado (Sin coste de copia):
T(n, k) = 2 ( ∑j=0..k C(n, j) ) - 1 =
Código JS: Llamar con combine1(list, k)
// C(n, k) = C(n-1, k-1) + C(n-1, k)
function combine1(list=[], k=0, n=list.length, res=[], result=[], n0=list.length){
    if (k===0){
        result.push(copy(res));
    } else if (n>0) {
        res.push(list[n0-n]);
        combine1(list, k-1, n-1, res, result);
        res.pop();
        combine1(list, k, n-1, res, result);
    }
    return result;
}
Trazado

Factorial

Las permutaciones de una lista con n elementos distintos son todas las sublistas ordenadas con n elementos distintos que se pueden generar. Se denota generamente como P(n) y su valor es P(n) = n! denominado el factorial. Se calcula recursivamente con n! = n (n-1)!.
0! = 1,
n! = n × (n-1)!
// n! = n * (n-1)!
function factorial(n){
    if (n<=0){
        return 1;
    } else {
        return n*factorial(n-1);
    }
}

Forma canónica de una permutación cíclica

Una permutación cíclica es una permutación que fija cero o más elementos y mueve el resto de forma cíclica. Cuando no se fija ningún elemento se denomina permutación circular. En esta aplicación un ciclo es como (1 2 3) separando los elementos con espacio. Y una permutación cíclica es uno o más ciclos como (1 2 4)(3 5), de tal forma que es la permutación 2 4 5 1 3 (ver notación en una o dos líneas) del conjunto de elementos {1, 2, 3, 4, 5}.

Estos tres ciclos son equivalente (1 2 3) = (2 3 1) = (3 1 2) dada su característica circular. La forma canónica es aquella cuyo primer elemento es el menor (1 2 3). Y los ciclos se ordenarán por los primeros elementos, así que (5 3)(2 4 1) se canoniza como (1 2 4)(3 5). En la aplicación si marcamos Canonizar siempre entonces se canonizarán las entradas σ y π así como el resultado.

Versión: 2024-08-20

Aplicación Combinatoria

Figura
Figura. Combinatorics Tool

La combinatoria estudia la forma de generar todas las posibles sublistas de una lista de elementos. En el fondo se trata de contar elementos. Los métodos principales son las combinaciones, permutaciones y variaciones de una lista de elementos. Vea que el problema es generar el conjunto de sublistas más que calcular el valor númerico de esas funciones. Ya hace tiempo analicé el coste de permutar un Array. En esa serie de temas veíamos como resolver recurrencias para calcular el coste de algoritmos recursivos usando técnicas como el desarrollo o la ecuación característica. A raíz de necesitar las combinaciones de una lista de dígitos para la aplicación Sudoku, me planteé estudiar más a fondo estas funciones combinatorias.

Para analizar una función combinatoria como C(n, k) podemos utilizar la técnica de la función generadora o generatriz. Esta aplicación servirá para comprobar los resultados matemáticos alcanzados en cada caso. Con esta aplicación se incluyen una serie de temas que analizan el coste de las funciones combinatorias. El tema inicial Funciones de generación para resolver recurrencias es una introducción a esa materia, repitiendo algunos problemas que ya resolvimos con desarrollos o ecuación característica.

En el tema Resumen funciones combinatorias recopilamos toda la información que aparece en la aplicación, separada en dos partes:

  1. Funciones combinatorias que generan listas, recopilando las funciones que vemos en la pestaña "Listas" de la aplicación.
  2. Funciones combinatorias numéricas, recopilando las funciones que vemos en la pestaña "Numéricos" de la aplicación.
Figura
Figura. Copy Math

El nuevo componente Copy Math nos permite ver la expresión en lenguaje natural de una fórmula, explicándose lo relacionado con las funciones combinatorias con más detalle en el tema Muestras de fórmulas matemáticas.