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.