Este es una serie de posts sobre un ejemplo básico de analisis de algoritmos. Va a constar de 3 partes: Descripción del problema y solución básica, Análisis de complejidad de la solución básica y Posibles mejoras. El codigo de estos posts se puede encontrar aquí .

Hace unos días estuve hablando con un ex-compañero de la facultad sobre una entrevista de trabajo que había tenido en una empresa muy grande de estados unidos. Me comento muy rapidamente y sin muchos detalles sobre el problema que le habían presentado y me resultó interesante como un buen ejercicio de Algoritmia básica.

Descripción del problema

El problema consiste en dado una lista de numeros enteros, remover los duplicados de la lista. Asumí al hacer el codigo, que interesa mantener la estructura de la lista ( O sea dado una lista: [5,3,4,5,3,2]; encontrar la misma lista pero con los duplicados removidos: [5,3,4,2] ).

Obviamente el problema no es solamente solucionar este problema, sino razonar sobre la corrección y eficiencia de la solución encontrada y ademas codificarlo en algun lenguaje ( especificamente C ).

Algunos pasos previos

Antes de comenzar a trabajar en el problema, me parecio conveniente hacer algunas funciones para poder testear y probar el codigo.

Struct de la lista

La estructura de datos que se va a utilizar en el ejercicio


typedef struct Node *List;
struct Node {
  int value;
  struct Node *next;
};

Función para mostrar la lista

Una función para mostrar la lista por pantalla.


void mostrar_lista(List lista) {
	//Este primer paso es para el pretty print de la lista
	if(lista != NULL) {
		printf("%d", lista->value);
		lista = lista->next;
	}
	while(lista != NULL) {
		printf("-%d", lista->value);
		lista = lista->next;
	}
}

Función para cargar una lista de prueba

Una función que dado un string con una lista de enteros separados por comas, lo parsea a un linked list.

Esta es una versión mejorada sobre la que hice originalmente, esta versión es forgiving con aquellos caracteres que pueden haber sido mal tipeados por el usuario o por input malintencionado, tomando solo los caracteres que representan dígitos ( el string: “1,a2,3b,d4d,xxxx,5,,,,6,a8b0,10” se tranforma en la lista: [1,2,3,4,5,6,80,10] ). La versión original era un poco más simple y no anticipaba malas entradas.


List crear_lista(List lista, char str[2000]) {
	int i=0;
	List rList = lista;

	//Es forgiving, solo lee los digitos y descarta lo demas.
	while( str[i] != '' ) {
		while( str[i] != '' && (str[i] < '0' || str[i] > '9') ) i++;
		if(str[i] == '') break;

		int pre = 0;
	    
		//Calcular el int
		while( str[i] != ',' && str[i] != '' ) {
			if(!(str[i] < '0' || str[i] > '9')) { 
				pre = pre * 10;
				pre = pre + (str[i] - '0');
			} 
			i++; 
		}
	    
		//Crear el nodo nuevo    
		List temp;
		temp = (List) malloc(sizeof(struct Node));
		temp->value = pre;
		temp->next = NULL;

		//Primera iteracion
		if(lista==NULL) {
			//Agregar nodo a lista
			lista = temp;
			//Lista de retorno
			rList = lista;
		} else {
			//Agregar nodo, mover cursor.
			lista->next = temp;
			lista = lista->next;
		} 
		i++;
	}
	return rList;
}

Ejemplo de uso:


	char str[2000] = "";
	scanf("%s", str);
	lista = crear_lista(lista, str);
	printf("La lista es: n");
	mostrar_lista(lista);

Solución básica

La solución básica consiste de 2 funciones. Una función int esta_en_lista(int value, List *pasados) que dado un entero value y una lista pasados verifica si el valor existe en la lista. Si ya existe devuelve 1, si no, devuelve -1 (podría haber usado constantes TRUE y FALSE como macros y el codigo seria mas bonito) y agrega este valor a la lista pasados en orden ascendente. La lista pasados se pasa por referencia ( efectivamente es un puntero a puntero ) dado que como side effect de la función se modifica esta lista, agregandosele ordenadamente cualquier valor que no pre-existe. O sea, en sucesivas llamadas a la funcion se va creando una lista ordenada de valores. La otra función List * sacar_duplicados(List *lista, List *pasados), recibe 2 punteros a listas, la lista de enteros de la que queremos sacar duplicados y una lista donde se guardan los valores que ya existen en la lista. Esta es la función que devuelve la primer lista con los valores removidos. Esta pensado para ser llamada con pasados siendo una lista vacia.


//Version basica a ser mejorada
//Se pasa un puntero al puntero de lista para hacer los side effects
int esta_en_lista(int value, List *pasados) {

	List rList, prev;

	rList = *pasados;
	prev = NULL;

	if(rList == NULL) {
		//Agregarlo antes
		List temp;
		temp = (List) malloc(sizeof(struct Node));
		temp->value = value;
		temp->next = *pasados;
		*pasados = temp;
		return -1;
	}

	while(rList != NULL) {
		if(rList->value == value) return 1;
		if(rList->value > value) {
			List temp;
			temp = (List) malloc(sizeof(struct Node));
			temp->value = value;
			temp->next = rList;
			if(prev==NULL) {
				*pasados = temp;
			} else {
				prev->next = temp;
			}
			return -1;
		}
		prev = rList;
		rList = rList->next;
	}
	//Agregarlo al final
	List temp;
	temp = (List) malloc(sizeof(struct Node));
	temp->value = value;
	temp->next = NULL;
	prev->next = temp;
	return -1;
}



//ESTA ES LA FUNCION QUE IMPORTA EN UN PRIMER PASO
//EN UN SEGUNDO PASO LO QUE IMPORTA ES MEJORAR LA FUNCION ANTERIOR
List * sacar_duplicados(List *lista, List *pasados) {
	//Caso Base
	if( (*lista) == NULL) {
		return lista;
	} else {
	//PASO INDUCTIVO
		if( esta_en_lista( (*lista)->value, pasados) > 0 ) {
			List next = (*lista)->next;
			free( (*lista) );
			return sacar_duplicados( &(next), pasados);
		} else {
			(*lista)->next = *( sacar_duplicados( &((*lista)->next), pasados) );
			return lista;
		}
	}
}

Se puede testear el programa compilando y corriendo solucion-basica.c .

Razonando sobre la corrección del algoritmo

Primera Parte

Lo primero que habria que considerar es si la función esta_en_lista() es correcta. No voy a hacer un análisis muy formal, pero supongamos los posibles casos:

  • pasados es una lista vacia: Se ejecuta el primer if: if(rList == NULL) , se crea un nodo nuevo que se agrega a pasados y se devuelve -1.
  • pasados no es una lista vacia y el valor existe en la lista:, se ejecuta el primer if y devuelve falso, se ejecuta la sentencia: while(rList != NULL) , se itera por todos los nodos hasta que se encuentra el nodo en el que pre-existe el valor, se llega a la condición: if(rList->value == value) y se devuelve 1.
  • pasados no es una lista vacia, el valor no existe en la lista y es menor a cualquier valor de la lista: se llega al while, en la primera iteración se llega a la condición: if(rList->value > value), se crea el nuevo nodo, se le agrega el resto de la lista como nodo hijo y se evalua la condición: if(prev==NULL), como prev fue inicializado a NULL y es la primera iteración, se asigna este nuevo nodo a pasados y se devuelve -1.
  • pasados no es una lista vacia, el valor no existe en la lista y esta entre medio de 2 valores de la lista: se llega al while, se itera por los nodos hasta que se llega a la condición: if(rList->value > value), se crea el nuevo nodo, se le agrega el resto de la lista como nodo hijo y se evalua la condición: if(prev==NULL), como prev esta apuntando al nodo pàdre del actual, se asigna este nuevo nodo como hijo de prev y se devuelve -1.
  • pasados no es una lista vacia, el valor no existe en la lista y es mayor a cualquier valor de la lista: se llega al while, se itera por los nodos hasta que se recorre toda la lista y se sale del while, se crea el nuevo nodo, se le agrega null como nodo hijo y se evalua la condición, se asigna este nuevo nodo como hijo de prev (que en este momento es el ultimo nodo de la lista) y se devuelve -1.

Razonar sobre la corrección del valor que devuelve (1 o -1) es trivial. Asi como razonar que no agrega un valor que ya existe.

Lo que es importante ver es que si se llama a la función con una lista ordenada y un valor que no existe en la misma, por los 3 ultimos casos (y el primero siendo estrictos, ya que una lista vacia es una lista ordenada), a esta lista se le agrega el valor en orden.

Segunda parte

Asumiendo que la función anterior es correcta y que la función esta_en_lista() devuelve un valor correcto y asi mismo que en sucesivas llamadas a la lista pasados se guardan en esta todos los elementos anteriores, podemos razonar sobre la función sacar_duplicados() que es la que nos importa.

La función es recursiva, por lo que para pensar sobre su corrección alcanza con hacer induccion para demostrar que la función retorna la misma lista sin duplicados. Voy a hacer un esquema del razonamiento que nos llevaria a una demostracion.

Paso base

El paso base es que la lista esta vacia. En ese caso se retorna una lista vacia, como una lista vacia es una lista sin duplicados, no hay nada más que demostrar. El codigo que soporta este caso es:


	//Caso Base
	if( (*lista) == NULL) {
		return lista;
	} 

Paso Inductivo

Ahora tenemos que demostrar que si llamamos a la funcion con una lista con n elementos sin duplicados entonces llamando a la función con la lista con n+1 elementos tambien se retorna una lista sin duplicados.

Para razonar sobre esto alcanza pensar que en el caso en que se llama a la función con (n+1) elementos, se llega a la siguiente porción de codigo:


		if( esta_en_lista( (*lista)->value, pasados) > 0 ) {
			List next = (*lista)->next;
			free( (*lista) );
			return sacar_duplicados( &(next), pasados);
		} else {
			(*lista)->next = *( sacar_duplicados( &((*lista)->next), pasados) );
			return lista;
		}

Analizemos los dos casos:

  • Si el valor (n+1) ya existe en la lista, se devuelve la lista hasta n. Como por la hipótesis inductiva, la lista hasta n es una lista sin duplicados y se devuelve esta, la lista que se devuelve en la llamado con n+1 elementos es así mismo una lista sin duplicados.
  • Si el valor (n+1) no existe en la lista, se devuelve la lista hasta n mas el elemento n+1. Como por la hipótesis inductiva, la lista hasta n es una lista sin duplicados y por asunción de caso el elemento nuevo no existe en la lista hasta n, la lista que se devuelve en la llamado con n+1 elementos es una lista sin duplicados.

Por exhaustación de casos, se comprueba que se cumple el paso inductivo.

Algunas observaciones sobre el algoritmo

El proximo paso y va ser el siguiente post es analizar la complejidad del algoritmo y despues buscar formas de mejorarlo. Como observaciones basicas se puede ver que llamando a la función sacar_duplicados() con una lista con n elementos, se itera (recursivamente) por cada uno de los n elementos de la lista, por otro lado la lista pasados va creciendo con cada llamado a esta_en_lista() que tiene un elemento nuevo y en todo caso de que este elemento sea mayor a cualquiera de los j elementos anteriores de pasados, esta_en_lista() itera por cada uno de los j elementos de pasados. Es pensando en estos temas que vamos a encarar el siguiente post.

Referencias

Foundations of Computer Science: C Edition; Aho, Ullman; W. H. Freeman; 1994