Funciones recursivas


Este es el tercer artículo que escribo sobre este tipo de funciones, los otros: aquí y aquí; y es que en un foro han preguntado sobre una función que devolviese todas las permutaciones de 0s y 1s que puede haber en un vector de n elementos. Lo he visto interesante, y es similar a lo que hice en el primero de los artículos, pero ahora que he vuelto de un examen, he hecho la función en un rato.

Está hecho en Matlab porque es el lenguaje que se pedía en el foro… debería ser fácil de pasar a cualquier otro, quedaría una función similar a la del primer artículo de funciones recursivas.

La función es muy simple, así que la pongo primero, y luego la explico:

function permutations(vector, n, i)
%n número de 1 que meter
%i lugar en el que empezar

if n==0				%Terminar
	vector
	return
end

for j=i:length(vector)-(n-1)

	if j == i
		vector(j) = 1;
	else
		vector(j) = 1;
		vector(j-1) = 0;
	end
	permutations(vector, n-1, j+1);

end

Como he dicho, es bastante corta. Esta función ha de empezar a ser leída por el segundo bloque, el for. Lo que hace es lo siguiente:

  • Le llega un vector de ceros, y un número n de 1 que debe permutar, (como el resto ha de ser ceros las permutaciones vienen dadas tan sólo por el lugar de los 1).
  • Recorre todos los lugares del vector en los que pueda poner el primer 1, estos lugares son desde el primero, hasta el último menos (n-1), ya que ha de dejar n-1 huecos, por lo menos, para el resto de 1
  • En cada uno de esos lugares, mira si es el primero del bucle, si lo es, entonces mete un 1 en ese lugar y pasa el vector de nuevo a la función recursiva, con parámetros n-1 (ya ha metido un 1, quedan n-1), y j+1 como el lugar en el que debe empezar a meter el resto de 1.
  • Puesto que estamos “moviendo” 1, es importante mirar si el lugar en cada fase recursiva es el primero (if j==i), en ese caso no hay problema, pero si no lo es, debemos poner un 0 en el lugar anterior, lo que equivale a quitar el anterior 1 y moverlo un lugar a la derecha.

Como siempre, la mejor forma de ver esto es coger un papel, y un caso pequeño, por ejemplo un vector de 4 lugares, y dos 1, lo que da un total de 6 posibles permutaciones, con papel y lápiz, ir siguiendo la función paso por paso para ver lo que hace y entenderla bien.

Analizando un poco el algoritmo, es fácil ver que depende tanto del tamaño del vector como del número de 1 que estemos permutando. El algoritmo recorre recursivamente todos los subconjuntos de n elementos del conjunto de todos los elementos del vector, llamemos m al tamaño del vector. Es combinatoria básica que el número total de subconjuntos es \binom{m}{n} = \frac{m!}{n!(m-n)!}

El mejor de los casos ocurre cuando n=1 ó n=m-1, en ese caso tenemos un algoritmo lineal, en notación asintótica: O(m), hay un caso más trivial, n=0, o n=m, en el que hay sólo una posibilidad y tenemos un algoritmo constante O(1).

El peor caso es cuando n=m/2 ó n=(m\pm 1)/2 dependiendo de si m es par o impar. Si eso se cumple tenemos el número más grande posible que da ese factorial (fácil de ver porque es el número más grande de cada fila del triángulo de Pascal). En ese caso: \frac{m!}{n!(m-n)!} = \frac{m!}{(m/2)!(m/2)!} = \frac{1}{2}m(m-1)(m-2)...(m-m/2+1) , en notación asintótica, tenemos O(m^{m/2}).

Bastante lento… Me gustaría conocer algún algoritmo más rápido para el caso, que seguro que lo hay. Si alguien lo conoce que me lo comente por aquí.

Un saludo a todos.

Anuncios
Esta entrada fue publicada en Manuales, Tutoriales y etiquetada , , , , , , . Guarda el enlace permanente.

2 respuestas a Funciones recursivas

  1. raul dijo:

    Hola, he estado leyendo como lo has hecho porque tengo que hacer exactamente lo mismo pero con una matriz y que luego me guarde los resultados para multiplicar cada una de las matrices por otra y ya seguir el programa en cada caso. Tambien he estado leyendo en el foro, pero no consigo hacer que me reparta los unos a lo largo de toda la matriz, ¿si no es mucha molestia me podrias echar un cable?. Gracias

  2. Ruben dijo:

    hola que tal bastante bueno el algoritmo, pero como puedo construir una matriz con los resultados

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s