El algoritmo de Heap genera las permutaciones de forma más eficiente que el que hemos usado en el tema anterior. Se basa en generar cada permutación desde una previa intercambiando una pareja de elementos cada vez. En la Imagen puede ver como se van intercambiando posiciones desde la lista inicial [0, 1, 2] generando las permutaciones {[0, 1, 2], [1, 0, 2], [2, 0, 1], [0, 2, 1], [1, 2, 0], [2, 1, 0]}.

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). Su valor es P(n) = n! Como se observa en la Imagen, para tres elementos obtenemos P(3) = 3! = 6.

El caso base de una recurrencia es aquel que nos permite resolverla, finalizando el proceso recursivo y devolviendo la solución. Cuando el caso base es un índice mayor de cero decimos que está desplazado. Y esto afecta a la forma en que aplicamos la técnica de la función generadora o generatriz. Resolveremos un ejemplo que trata de buscar los dos puntos que se encuentran a menor distancia entre un conjunto de puntos.

En la página OEIS podemos ver la secuencia 1, 6, 27, 124, 645, ... que denomina Convolución exponencial de factoriales y cuadrados (Exponential convolution of factorials and squares). Es el resultado de la recurrencia a(n) = n a(n-1) + n² con a(0)=0. Expone entre otras la solución a(n) = ∑_j=0..n (n! j²) / j! que es como la que aparece en la Imagen para k=2. Podemos encontrar OEIS con factoriales y cubos, que también se ajusta a la general con k=3. En este tema analizamos esta recurrencia y su relación con las K-Tuplas que vimos en el tema anterior.

Adicionalmente en este tema veremos la Función Gamma pues está relacionada con las series que resuelven las recurrencias. He podido también representar esa función como se observa en la Imagen, generada en mi aplicación Gráficas matemáticas. Usa la definición en formato de texto plot-gamma.txt, para lo cual debe copiar ese texto y pegarlo en la pestaña I/O para importarlo en ese graficador de funciones matemáticas si quisiera observar su generación. En rojo se dibuja la función Gamma Γ(x) y en azul la función recíproca 1/Γ(x), que, como se observa, cruza por cero y los enteros negativos.

Definimos las K-Tuplas de un conjunto A con n elementos distintos a todas las sublistas ordenadas que podemos generar con las permutaciones aplicadas sobre todos los subconjuntos de orden k hasta n que se obtienen desde el conjunto A.

Una recurrencia con coeficientes variables es como K(n) = n K(n-1) + 1. No puede usarse el modelo de ecuación de recurrencia de coeficientes constantes y es necesario utilizar la técnica de la función generadora o generatriz exponencial. Se analiza esa recurrencia de ejemplo usando varias técnicas y estudiando nuevos conceptos como el producto de series, la relación con las combinaciones y las series binomiales, la función gamma incompleta, el factorial ascendente (símbolo de Pochhammer) y descendente, la función hipergeométrica generalizada y la función hipergeométrica confluente de segunda clase.

Las combinaciones con repetición de una lista con n elementos distintos son todas las sublistas con k elementos no necesariamente distintos que se pueden extraer sin importar el orden. Se denotan como CR(n, k) y también como CR_n,k.

Hay varias identidades relacionadas con los coeficientes binomiales. Una de ellas es la que vemos en la imagen, obtenida a partir de la denominada identidad Hockey-stick. Se observa que es una expresión recurrente que podría servirnos para buscar una versión mejorada del problema de obtener los subconjuntos combinaciones sin repetición de un conjunto que vimos en el tema anterior.

Usaremos la técnica de la función generadora para obtener el coste del algoritmo. Finalizaremos comparando la mejora obtenida con respecto al algoritmo del tema anterior.

El número de combinaciones sin repetición de n elementos distintos en subconjuntos de k elementos son las posibles muestras de k elementos distintos y sin orden que pueden extrarser de los n elementos. En estas páginas las denotaremos como C(n, k).

La primera aproximación para implementar un algoritmo es usar la conocida fórmula matemática con la recurrencia C(n, k) = C(n-1, k-1) + C(n-1, k) que sirve para construir el Triángulo de Pascal. La fila n son los coeficientes binomiales del polinomio (1+x)ⁿ. Analizaremos el coste usando la técnica de la función generadora.

Para analizar el coste de un recursivo de una variable vimos varias posibilidades, como desarrollar la recurrencia hasta el caso trivial o equipararla a una ecuación característica. Son técnicas básicas para recurrencias simples como T(n). Pero si la recurrencia es más compleja o incluye dos variables T(n, k), entonces hemos de aplicar la técnica de la función generadora que veremos en estos temas.

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.

Esta aplicación servirá para comprobar los resultados matemáticos alcanzados con cada algoritmo. Con esta aplicación se incluyen una serie de temas que analizan el coste de las funciones combinatorias.

Los posicionamientos CSS que conocemos hace tiempo son static, relative, absolute y fixed. Ahora se introduce el nuevo posicionamiento sticky. El documento oficial W3C Sticky positioning está en fase de borrador (Working Draft) con fecha 01/09/2022. A la fecha en la que edito esta página (diciembre 2022) ya es soportado por todos los navegadores.

Una aplicación práctica para sticky es fijar las filas o columnas cabeceras de una tabla. En la Figura vemos una tabla cuyo ancho y alto es mayor que el contenedor donde se ubica y donde hemos fijado la primera fila y la primera columna. Actuando sobre las barras de desplazamiento (scroll) del contenedor exterior veremos que la primera fila permanece fija respecto al scroll vertical. Y que la primera columna permanece fija respecto al scroll horizontal.

El grupo Fish de técnicas de resolución de un Sudoku se basa en una rejilla de n×n celdas que comprende 'n' conjuntos fila × 'n' conjuntos columna, o viceversa. En las intersecciones entre filas y columnas hemos de encontrar un disponible al menos en dos de ellas. Uno de los conjuntos se denomina conjunto base y el otro conjunto cobertura.

Estas son las técnicas que he implementado:

• Fish, X-Wing en el grupo Fish, Pez espada (Swordfish), Medusa (Jellyfish)
• Finned X-Wing, Finned Swordfish, Finned Jellyfish
• Sashimi X-Wing, Sashimi Swordfish, Sashimi Jellyfish
• Franken X-Wing, Franken Swordfish, Franken Jellyfish
• Finned Franken Swordfish (base), Finned Franken Swordfish (cover), Finned Franken Swordfish (2 boxs)
• Sashimi Franken Swordfish (base), Sashimi Franken Swordfish (cover)

Un verdadero Sudoku es aquel tablero inicial que conduce a una única solución. Muchos tableros iniciales conducen a resultados con más de una solución. E incluso algunos no tienen solución. El problema de resolver un Sudoku con técnicas de profundizado y sin usar el último recurso del vuelta atrás parte de la base de que el tablero inicial conduce a una única solución. Y esto puede aprovecharse para crear un nuevo conjunto de técnicas que se agrupan dentro del termino Unicidad (Uniqueness).

El tablero del ejemplo en la imagen adjunta muestra el momento en que hay sólo cuatro celdas que llenar, todas con los mismos diponibles '69'. Si en una ponemos '6', en la otra en la misma fila hemos de poner '9'. Y sus opuestos en la otra fila. Esto conduce a obtener dos soluciones para el Sudoku. Por lo tanto para ese tablero no aplica el concepto de unicidad, pues tiene dos soluciones. Pero cuando aplicamos las técnicas de resolución partimos de la base de que el Sudoku se planteó en un tablero inicial para que tuviera solución única. El rectángulo de NO unicidad formado por las cuatro celdas sin llenar que se observa en la Figura no puede darse nunca en un verdadero Sudoku. Ese rectángulo que debemos evitar se suele denominar patrón mortal o deadly pattern en la terminología en inglés. En lo que sigue veremos como aprovechar estos conceptos para encontrar y borrar números disponibles, para lo cual hemos de evitar que aparezca un rectángulo de no unicidad.

Basándonos en estos conceptos aplicaremos las técnicas de unicidad rectángulos únicos, ocultos y evitables (unique, hidden and avoidable rectangles) así como la técnica BUG+1:

• Rectángulo único (I)
• Rectángulo único (II)
• Rectángulo único (III)
• Rectángulo único (IV)
• Rectángulo único (V)
• Rectángulo oculto (I)
• Rectángulo oculto (II)
• Rectángulo evitable (I)
• Rectángulo evitable (II)
• BUG+1

La técnica de resolución o profundizado de un Sudoku denominada Ala WXYZ (WXYZ Wing) se basa en cuatro celdas y cuatro números W, X, Y, Z. Hay dos tipos I y II de Ala WXYZ. En los esquemas adjuntos se observan ambos tipos. La celda WXYZ puede contener entre 2 y 4 números W, X, Y o Z, pero al menos debe contener W o Z necesariamente. A continuación encontraremos una celda con los disponibles WZ, que para el tipo I estará en la misma caja y para el tipo II en la misma fila. Finalmente econtraremos dos celdas con XYZ, que puede tener entre 2 y 3 números de valores X, Y o Z, sin que puedan contener W. Para el tipo I estarán en la misma fila que WXYZ. Y para el tipo II en la misma caja que WXYZ.

Si se cumplen las condiciones anteriores podemos eliminar hasta dos disponibles z en las celdas resaltadas.