Bloque de Colores

Algunos resultados interesantes

Icono de Post March 3 2012 :: Combinatoria, Python, Uncategorized ::

Como conte en este post, para resolver el problema del post anterior, hice una serie de pruebas cuyos resultados se pueden ver acá. Me quedo un cubo triangularmente cortado de resultados de variaciones de los parámetros de la función descripta. Para acelerar un poco los tests, una vez que conseguí una solución (cuya demostración se puede encontrar en una hermosa versión typesetada en LaTeX acá) la programe en python usando técnicas de programacion dinámica. Esta versión se puede encontrar aqui.

Lo interesante fue que me quedaron varias secuencias de números y decidí ir a OEIS para testearlo. Me encontré entonces con una serie de resultados interesantes que decidí publicar acá para revisarlos mas adelante.

Resultados simples

  • Si m=n=k , la función devuelve una permutación. m!
  • si m=n, m<k => f(n, m, k) = k!/(k-m)!

Resultados interesantes

Parece existir algún tipo de patrón, lamentablemente no tengo el tiempo en este momento y sobre todas las cosas el nivel de matemática suficiente como para investigarlo un poco más. Escribo este post más que nada para revisarlo nuevamente después de haber pasado por Concrete Mathematics, que todavía no pude estudiar.

Algún otro resultado

Da la sensación de que jugando con las variables del cubo se encontrarían un montón de resultados interesantes.

Autor: Emiliano Martínez Luque.

Comments Off on Algunos resultados interesantes

Cuantas cadenas de tamaño n pueden ser creadas con exactamente m símbolos de un alfabeto de k símbolos?

Icono de Post March 3 2012 :: Combinatoria, Lenguajes Formales, Lógica ::

Lo que estamos buscando es, dado A un alfabeto de tamaño k, la cantidad de cadenas de tamaño n que contienen exactamente m símbolos de A.

Para resolver este problema primero vamos a resolver lo siguiente:

Cuantas cadenas de tamaño n pueden ser creadas con todos los símbolos de un alfabeto de k símbolos?

Se propone la siguiente relación de recurrencia de 2 variables, donde:

n: representa el tamaño de la cadena

k: representa la cantidad de símbolos en el alfabeto

f(0, k) = 0

Para todo k, ya que la cantidad de cadenas de tamaño 0 que pueden formarse con todos los símbolos de A es 0.

f(1, 1) = 1

Ya que existe solo una cadena de tamaño 1 con 1 símbolo.

f(n, k) = k( f(n-1,k) + f(n-1, k-1) )

Demostración

Llamemos An,k al conjunto de todas las cadenas de tamaño n que contienen a todos los símbolos de A e intentemos construir todas las cadenas que pertenecen a este conjunto.

Para cada símbolo a de An,k vamos a realizar el siguiente procedimiento:

1. Llamemos An-1,k al conjunto de todas las cadenas de tamaño (n-1) con exactamente k símbolos de A (o sea con todos los símbolos de A).

Para cada cadena α de An-1,k construimos una nueva cadena concatenandole a, nos queda así una nueva cadena: . Como α tiene tamaño (n-1), la nueva cadena tiene tamaño n.

Ademas por definición de An-1,k, α contiene a todos los símbolos de A, y en particular contiene a a. Entonces de esta manera hemos formado todas las cadenas de An,k que comienzan por a y tienen al menos 2 ocurrencias de a.

Nos queda todavía construir todas las cadenas de An,k que comienzan por a pero tienen solo una ocurrencia de a.

2. Llamemos An-1,k-1 al conjunto de todas las cadenas de tamaño (n-1) que están formadas por todos los símbolos de A menos a.

Para cada cadena β de An-1,k-1 construimos una nueva cadena . Se cumple entonces que tiene tamaño n y ademas dado que β contiene a todos los símbolos de A menos a a y le hemos concatenado a, contiene los k símbolos de A.

A partir de estos dos pasos hemos construido todas las cadenas de An,k que comienzan con a. Como por definición de An,k, cualquier cadena de An,k necesariamente tiene que comenzar con un símbolo de A y a es un elemento arbitrario podemos aplicar el procedimiento para construir todas las cadenas del conjunto An,k.

Como por hipótesis, |An-1,k-1| = f(n-1,k-1), |An-1,k| = f(n-1,k) y como existen exactamente k símbolos de A se cumple que f(n, k) = k( f(n-1,k) + f(n-1, k-1) ).

Cuantas cadenas de tamaño n pueden ser creadas con exactamente m símbolos de un alfabeto de k símbolos?

Asumiendo que la función anterior es correcta, podemos proponer la siguiente función:


g

(
n
,
m
,
k
)

=

(

m
k

)

×
f

(
n
,
m
)


Llamemos Am al conjunto de todos los subconjuntos de A con exactamente m elementos. Es conocido que la cantidad de subconjuntos de tamaño m de un conjunto se puede calcular como:


|

A
m

|
=

(

m
k

)


(Ver Combination) . Sabemos ademas por el resultado anterior que la cantidad de cadenas de tamaño n que pueden hacerse de un conjunto de tamaño m es igual a f(n,m), a partir de lo cual derivamos la formula.

Autor: Emiliano Martínez Luque.

Comments Off on Cuantas cadenas de tamaño n pueden ser creadas con exactamente m símbolos de un alfabeto de k símbolos?

Algunas notas sobre Explosión Combinatoria, los Lenguajes de Scripting y el Uso de Memoria

Icono de Post March 1 2012 :: c, Javascript ::

Hace un par de meses estuve trabajando en un problema de combinatoria que consistía en los siguiente: Dado un alfabeto A de tamaño k, cuantas cadenas de tamaño n pueden construirse con exactamente z símbolos de A. Busque en bastantes libros y no pude encontrar una solución, por lo que decidí investigarlo por mi cuenta, para esto, decidí hacer una serie de experimentos con diferentes valores de k, n y z para intentar llegar a una formula general (que sera el tema de un próximo post).

Lo interesante fue que en este proceso fui probando los limites de mi PC y tuve que buscar diferentes soluciones para lograr los resultados que buscaba, ese es el tema de este post, cuyo código se puede encontrar aquí.

Primer Intento en Javascript

Mi primer intento fue simplemente hacer una variedad de diferentes loops en Javascript generando las diferentes combinaciones. Use Javascript porque ingenuamente pensé que era un problema simple y lo que quería resolver rápido.

No hay nada muy complejo en esta solución y se pueden ver una versión para 4 y 5 elementos en la carpeta de Github.

El problema es obviamente que hay que hacer un nested loop para cada tamaño de cadena y alfabeto distinto, era evidente que necesitaba una versión mejor.

Segundo Intento en Javascript

El segundo intento es una versión general que usando recursividad busca generar las diferentes combinaciones y además cuenta la cantidad de símbolos que tiene cada cadena y genera un reporte. De nuevo, fue una versión rápida codificada sin mucho razonamiento previo, pero que era lo suficientemente general como para poder resolver el problema.

El problema fue que cuando intente correrla con valores mayores a 6 o 7, mi navegador se tildaba y tenía que reiniciar la maquina. Bueno, es bien sabido que javascript sobre un browser no es un entorno muy confiable cuando se le demanda demasiado, por otro lado todas las cadenas de tamaño 7 con un alfabeto de 7 son 77=823543 variaciones. Además por como funciona javascript en la función donde se generan estas cadenas, se copia un array, pero cuando se agrega un elemento a un array o se concatenan dos array en javascript (a diferencia de por ejemplo Python, donde las listas se concatenan por referencia) se genera un array nuevo con el consiguiente uso de memoria que esto implica.


function generarCombinaciones(depth, size) {
	if(depth==1) {
		var arr = [];
		for(var x=0; x<size; x++) {
			arr[x] = x;
		} 
		return arr;
	} else {
		var arr = new Array();
		var pre = generarCombinaciones(depth-1, size);
		for(var x=0; x<size; x++) {
			for(var y=0; y<pre.length; y++) {
				var arr2 = new Array();
				arr2.push(x);
				arr2 = arr2.concat(pre[y]);
				arr.push(arr2);
			}
		}
		return arr;
	}
}

Decidí para mejorar la performance pasar a C.

Primer intento en C

El primer intento en C tenía en cuenta este problema y lo que hacia para resolverlo era a través de punteros ir generando recursivamente las nuevos elementos como referenciando a los elementos anteriores. Por ejemplo: primero se generaba la lista [1,2] y luego para generar [[1,1], [1,2], [2,1], [2,2]] se utilizaba el mismo [1] para [1,1] y para [2,1] o sea el puntero de estas dos listas apuntan al mismo nodo en las dos listas. De esta manera se va generando recursivamente un árbol en el que cada sublista es reutilizada por la lista que las listas que la contienen.

Esta versión se puede encontra aquí y se puede correr, haciendo gcc contar_combinaciones.c -lm -o contar_combinaciones. Además esta versión genera una página HTML con las tablas de resultados y también una tabla con los resultados factorizados. La porción de código a la que se hace referencia es:



Result_list generar_combinaciones(int depth, int size) {
	Result_list results = NULL;
	Result_list cursor;

	int x;	

	if(depth == 0) {
		for(x=0; x<size; x++) {
			List temp;
			temp = (List) malloc(sizeof(struct Node));
			temp->value = x;
			temp->next = NULL;

			Result_list temp_result;
			temp_result = (Result_list) malloc(sizeof(struct Result));
			temp_result->list = temp;
			temp_result->next = NULL;

			if(results == NULL) {
				results = temp_result;
				cursor = temp_result;
			} else {
				cursor->next = temp_result;
				cursor = cursor->next;
			}
		}
		return results;
	} else {
		Result_list previous_results;
		Result_list previous_temp_cursor;

		previous_results = generar_combinaciones(depth-1, size);
		
		while(previous_results != NULL) {
			for(x=0; x<size; x++) {
				List temp;
				temp = (List) malloc(sizeof(struct Node));
				temp->value = x;
				temp->next = previous_results->list;

				Result_list temp_result;
				temp_result = (Result_list) malloc(sizeof(struct Result));
				temp_result->list = temp;
				temp_result->next = NULL;

				if(results == NULL) {
					results = temp_result;
					cursor = temp_result;
				} else {
					cursor->next = temp_result;
					cursor = cursor->next;
				}
			}
			previous_temp_cursor = previous_results->next;
			free(previous_results);
			previous_results = previous_temp_cursor;			
		}
		return results;
	}
} 


Me resulto muy interesante de hacer el tener que generar una lista de resultados en cada iteración recursiva que va hilvanando las listas finales.

Sin embargo había otro problema, cuando se van generando cada una de las combinaciones se mantienen en memoria antes de ser computados la cantidad de símbolos que contienen. Bueno con parámetros lo suficientemente grandes, me quedaba sin memoria! y empezaba a tocar el swap (a pesar de que mi maquina de desarrollo tiene 16 gigas de ram). Por lo que tuve que buscar otra solución que fue la solución final.

Solución final en C

En la versión final se me ocurrió simplemente contar la cantidad de símbolos luego de generar la lista. Como las listas se van generando recursivamente me pareció una solución bastante elegante.



void generar_contar_combinaciones(int depth, int size, List lista, int arr[MAX_ALPHABET_SIZE]) {
	int x, c;	
	List cursor_ultimo = lista;

	if(cursor_ultimo != NULL) {
		while(cursor_ultimo->next != NULL) cursor_ultimo = cursor_ultimo->next;
	}

	if(depth == 0) {
		for(x=0; x<size; x++) {
			List temp;
			temp = (List) malloc(sizeof(struct Node));
			temp->value = x;
			temp->next = NULL;

			if(cursor_ultimo == NULL) {
				c = contar_elementos_distintos(temp, size);
				arr[ c ]++;
				free(temp);
			} else {
				cursor_ultimo->next = temp;
				c = contar_elementos_distintos(lista, size);
				arr[ c ]++;
				free(temp);
				cursor_ultimo->next = NULL;
			}
		}
	} else {
		for(x=0; x<size; x++) {
			List temp;
			temp = (List) malloc(sizeof(struct Node));
			temp->value = x;
			temp->next = NULL;

			if(cursor_ultimo == NULL) {
				generar_contar_combinaciones(depth-1, size, temp, arr);
				free(temp);
			} else {
				cursor_ultimo->next = temp;
				generar_contar_combinaciones(depth-1, size, lista, arr);
				free(temp);
				cursor_ultimo->next = NULL;
			}
		}
	}
}

Resultados

Los resultados de esta exploración pueden encontrarse aquí y proximamente voy a hacer un post con la respuesta al problema.