Ejemplos de divide y vencerás ============================= **Nota: Algunos de estos ejemplos son interactivos. Para probarlos necesitarás las capacidades de IPython Notebook. La forma más fácil es subirlo en `tmpnb.org `__. veamos cómo hacerlo.** - Descarga el `archivo correspondiente a este cuaderno `__ y guárdalo en tu ordenador. - Entra en `tmpnb.org `__ y pulsa sobre el botón *Upload*. Selecciona el archivo que guardaste en el paso anterior y acepta. - Aparecerá el archivo en la página de `tmpnb.org `__ con un botón *Upload* a la derecha, pulsa sobre él para que se realice la transferencia. - Posteriormente comprueba de que el nombre del archivo termina en ``.ipynb``. Si no lo hace marca la casilla (*checkbox*) a la izquierda del archivo subido y pulsa el botón *Rename*. Edita el nombre para que termine en ``.ipynb`` y acepta. - Ya puedes pinchar sobre el nombre del archivo para interactuar con el cuaderno. Ahora selecciona la opción de menú *Cell->Run All* para ver ejecutar todas las celdas en el nuevo entorno. Torres de Hanoi --------------- Mover ``n`` discos desde el palo ``orig`` al palo ``dest``. Es directo usando la estrategia de divide y vencerás. Para mover los ``n`` discos tenemos que mover primero los ``n-1`` superiores al palo libre, entonces movemos el disco grande al palo destino y posteriormente movemos los ``n-1`` discos del palo libre al palo destino. .. code:: python def hanoi(n, orig=1, dest=3): ''' Asume n número natural (> 0), orig número de palo origen, orig in (1,2,3), dest número de palo destino, dest in (1,2,3). Imprime los movimientos a realizar para mover n discos desde el palo orig al palo dest. ''' if n < 1: return libre = (set((1,2,3)) - set((orig,dest))).pop() hanoi(n-1, orig, libre) print('De {} a {}'.format(orig, dest)) hanoi(n-1, libre, dest) Solo falta probarlo: .. code:: python hanoi(4) .. parsed-literal:: De 1 a 2 De 1 a 3 De 2 a 3 De 1 a 2 De 3 a 1 De 3 a 2 De 1 a 2 De 1 a 3 De 2 a 3 De 2 a 1 De 3 a 1 De 2 a 3 De 1 a 2 De 1 a 3 De 2 a 3 Como puede verse no es muy vistoso que digamos. Sería más elegante una representación gráfica. Pero esto es algo que no debería mezclarse con la solución del problema. El error ha sido mezclar la interacción con el usuario con la solución del problema. Vamos a arreglarlo. El resultado de ``hanoi`` debe ser la secuencia de movimientos. Cada movimiento es un par de números, el palo origen y el destino. Por tanto el resultado debe ser una lista de tuplas de dos números. Para concatenar dos listas podemos usar el método ``extend`` de las listas o la suma de listas, que también concatena. .. code:: python def hanoi(n, orig=1, dest=3): ''' Asume n número natural (> 0), orig número de palo origen, orig in (1,2,3), dest número de palo destino, dest in (1,2,3). Imprime los movimientos a realizar para mover n discos desde el palo orig al palo dest. ''' if n < 1: return [] libre = [x for x in (1,2,3) if not x in (orig,dest)][0] return hanoi(n-1, orig, libre) \ + [(orig, dest)] \ + hanoi(n-1, libre, dest) .. code:: python print(hanoi(4)) .. parsed-literal:: [(1, 2), (1, 3), (2, 3), (1, 2), (3, 1), (3, 2), (1, 2), (1, 3), (2, 3), (2, 1), (3, 1), (2, 3), (1, 2), (1, 3), (2, 3)] Y si queremos volver a tener la misma salida: .. code:: python for m in hanoi(4): print('De {} a {}'.format(m[0], m[1])) .. parsed-literal:: De 1 a 2 De 1 a 3 De 2 a 3 De 1 a 2 De 3 a 1 De 3 a 2 De 1 a 2 De 1 a 3 De 2 a 3 De 2 a 1 De 3 a 1 De 2 a 3 De 1 a 2 De 1 a 3 De 2 a 3 Lo bueno es que ahora podemos preparar otra visualización más vistosa sin tocar el algoritmo. .. code:: python %matplotlib inline from IPython.display import HTML, display from IPython.html.widgets.interaction import interact def mostrar_torres(ndiscos=8, paso=0): '''Asume ndiscos entero positivo (> 0) paso entero positivo (>= 0). Muestra un SVG que represemta el estado de las torres en esta situación. ''' t = [list(range(ndiscos+1,1,-1)),[],[]] mov = hanoi(ndiscos) for i in range(min(paso, len(mov))): mover(t,mov[i]) display(HTML(torres(t))) def mover(t,m): '''Asume t es una lista de 3 listas. Cada lista de t contiene los discos del palo correspondiente. Cada disco se representa con su longitud. Asume m es una tupla de dos números. El palo origen y el palo destino. Los palos se numeran desde 1. Mueve el último disco según de t[m[0]] a t[m[1]]. ''' orig, dest = m t[dest-1].append(t[orig-1].pop()) def torres(ll): '''Asume ll es una lista de 3 listas. Cada lista de t contiene los discos del palo correspondiente. Cada disco se representa con su longitud. Devuelve un SVG que representa el contenido de ll. ''' return '{}' \ .format(''.join([palos(150, 6, 100)] + \ [torre(ll[i],i+1, 100) for i in range(len(ll))])) def palos(x, w, h): '''Asume x, w, h son enteros positivos que representan respectivamente la posición en el eje x del primer palo, el ancho y el alto. Devuelve una cadena con los elementos graficos que representan los palos y la base de las torres de Hanoi. ''' return ''.join([rect(x-w/2, 10, w, h), rect(2*x-w/2, 10, w, h), rect(3*x-w/2, 10, w, h), rect(x/2, 10+h, 3*x, 2*w)]) def rect(x,y,w,h,style='fill:lightgray'): '''Asume x, y, w, h son enteros positivos que representan respectivamente la posición en el eje x, en el eje y, el ancho y el alto. Asume style es una cadena que contiene un estilo CSS. Devuelve una cadena que representa el rectángulo de estas características. ''' return '' \ .format(x,y,w,h,style) def torre(l, palo, h): '''Asume l es una lista de enteros que corresponde a los anchos de los discos de una torre desde el inferior hasta el superior. Asume palo es un entero (palo in [1,2,3]). Asume h entero positivo. Devuelve una cadena con la representación gráfica de la torre correspondiente, siendo h la altura del palo. ''' return ''.join([disco(l[i], palo, i, h) for i in range(len(l))]) def disco(ancho, palo, y, h): '''Asume ancho, palo, y, h enteros positivos. Asume palo in [1,2,3]. Devuelve una cadena con la representación gráfica de un disco de ancho ancho, en el palo palo, en la posición y, siendo la altura del palo h. ''' return ''' ''' \ .format(palo*150 - ancho*5, h - 10*y, ancho*10) interact(mostrar_torres, ndiscos=(4,8,1), paso=(0,256,1)) .. raw:: html Ordenación: *Merge sort* ------------------------ Consideremos el problema de ordenar una secuencia de números. .. code:: python import random datos = list(range(20)) random.shuffle(datos) print(datos) .. parsed-literal:: [13, 14, 16, 8, 2, 1, 19, 10, 9, 7, 0, 17, 18, 5, 3, 15, 12, 11, 6, 4] Podemos aplicar *divide y vencerás* de varias formas. Por ejemplo, dividimos la lista en 2, ordenamos las 2 mitades y mezclamos las dos listas ordenadas. Este algoritmo se lo debemos a John von Neumann. .. code:: python def merge_sort(l): if len(l) < 2: return l mitad = len(l)//2 return merge(merge_sort(l[:mitad]), merge_sort(l[mitad:])) def merge(l1, l2): i, j = 0, 0 l = [] while i < len(l1) and j < len(l2): if l1[i] < l2[j]: l.append(l1[i]) i += 1 else: l.append(l2[j]) j += 1 return l + l1[i:] + l2[j:] Lo único complejo es la mezcla. La mezcla selecciona elementos de una lista o de otra dependiendo de cuál tiene el menor. Cuando una lista se acaba la mezcla debe incluir el resto de la otra. Tal vez sea más fácil de entender la función ``merge`` si usamos divide y vencerás para describirla. .. code:: python def merge(l1, l2): if len(l1) == 0: return l2 if len(l2) == 0: return l1 if l1[0] < l2[0]: return [l1[0]] + merge(l1[1:], l2) return [l2[0]] + merge(l1, l2[1:]) .. code:: python print(merge_sort(datos)) .. parsed-literal:: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] Una característica interesante de este algoritmo es que es fácil de adaptar al caso en el que no disponemos de memoria suficiente para ordenar todos los elementos (por ejemplo, cuando los datos están en una base de datos). Sin embargo se trata de un algoritmo que consume bastante memoria, porque se copian los elementos para formar las listas ordenadas. Ordenación: *Quicksort* ----------------------- Otra forma de aplicar la estrategia de *divide y vencerás* es el algoritmo Quicksort de C. A. R. Hoare. El método consiste en seleccionar un elemento denominado *pivote*. Todos los elementos menores o iguales al pivote se ponen a un lado y todos los mayores o iguales se ponen a otro lado. Al acabar tenemos dos grupos de números que volvemos a ordenar utilizando el mismo algoritmo. Lo bueno de este algoritmo es que puede usarse *in-place* para reducir el consumo de memoria. .. code:: python def qsort(l): qsort_segmento(l, 0, len(l)) def qsort_segmento(l, primero, ultimo): if ultimo - primero < 2: return div = clasifica(l, primero, ultimo) qsort_segmento(l, primero, div) qsort_segmento(l, div, ultimo) def clasifica(l, primero, ultimo): pivote = (primero + ultimo) // 2 l[primero], l[pivote] = l[pivote], l[primero] div = primero + 1 for i in range(primero + 1, ultimo): if l[i] <= l[primero]: l[div], l[i] = l[i], l[div] div += 1 return div La parte más difícil es clasificar con respecto al pivote. Nosotros seleccionamos el elemento del medio como pivote (para no perjudicar a las listas ya ordenadas). Ese elemento lo situamos como primero del segmento a ordenar y el resto lo vamos pegando a él si es menor o igual o lo dejamos si es mayor. Puede que te preguntes por qué se mueve el pivote como primer elemento. Se hace para evitar casos desafortunados en que el pivote es el mayor elemento del segmento. Si no se moviera llamaríamos indefinidamente a la función de ordenación con el mismo segmento. Solo queda probarlo. .. code:: python ordenados = datos[:] qsort(ordenados) print(ordenados) .. parsed-literal:: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]