SGCG

…esto no es un subtítulo…

Ir a: contenido categorías calendario archivo suscripción

Volver arriba

Jugando con autómatas celulares (7)

2013-08-27

Hace varios artículos, planteamos un interesante proyecto: una pequeña biblioteca para construir autómatas celulares. Los autómatas celulares son unas estructuras matemáticas muy curiosas: retículos de celdas que van cambiando de un estado a otro y que pueden, a partir de reglas sencillas, exhibir complejísimos comportamientos emergentes. Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en Python 2. El enfoque es funcional porque el problema se presta mucho a ello. No nos preocuparemos tanto por hacer un código especialmente rápido como por hacerlo claro y conciso.

Seguimos construyendo funciones para hacer una biblioteca de autómatas celulares razonablemente general y práctica. Nuestros autómatas celulares pueden tener topologías muy diversas, pero una de las más comunes es la de una malla cartesiana que a menudo es toroidal o cíclica: al avanzar en una de las direcciones coordenadas, la malla se repite periódicamente. Es muy interesante manejar autómatas con esta topología tan frecuente, pero las funciones que hemos preparado hasta ahora solamente trabajan con listas planas. Esto no ha de preocuparnos en exceso, pues podemos establecer una correspondencia sencilla entre los elementos de una lista plana y los elementos de una malla multidimensional. Lo que vamos a hacer es almacenar las celdas en una lista con un orden que se conoce en inglés como row-major: en dos dimensiones, almacenamos los elementos de la primera fila de izquierda a derecha, luego los elementos de la segunda fila, luego los elementos de la tercera fila…; en más dimensiones, generalizamos y vamos apilando siempre con incrementos en los índices situados más a la derecha y luego sucesivamente los índices más a la izquierda conforme los índices con más prioridad dan la vuelta. Por ejemplo, si tenemos una malla tridimensional de dos celdas por dos celdas por dos celdas con índices de 1 a 3 en cada dimensión tales que denotamos una celda mediante la tripla (nivel, fila, columna), la lista de celdas correspondiente sería la {(1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2)}.

Paso de índices planos a índices multidimensionales

Lo más difícil que vamos a hacer hoy es el paso de índice plano a índices multidimensionales. Usaremos la función unfold que definimos hace unos días. Naturalmente, es posible hacer el mismo trabajo con estructuras de control más explícitas como bucles y funciones recursivas a medida.

El paso de un índice plano a los índices multidimensionales correspondientes en orden row-major puede hacerse mediante divisiones enteras sucesivas. El incremento de un índice a la izquierda supone que han dado la vuelta todos los índices a su derecha; el tamaño de la vuelta es el producto de los tamaños de las dimensiones a la derecha del índice que queremos extraer. De lo anterior se extrae que, dado un índice plano, el índice más a la izquierda es la división entera del índice plano entre la vuelta correspondiente al índice más a la izquierda; el siguiente índice es la división entera del resto de la anterior división y la vuelta correspondiente al siguiente índice… Esto queda plasmado en la siguiente función flat->multidimensional que acepta una lista sizes con los tamaños de las dimensiones desde la que está más a la izquierda hasta la que está más a la derecha y un índice plano index; la función devuelve una lista con los índices multidimensionales desde el situado más a la izquierda hasta el situado más a la derecha:
(define (flat->multidimensional sizes index) (define strides (reverse (cons 1 (if (= (length sizes) 1) '() (cumulative-product (reverse (cdr sizes))))))) (define current-index car) (define current-stride cadr) (define strides-list cdr) (unfold (lambda (index-and-strides) (null? (strides-list index-and-strides))) (lambda (index-and-strides) (floor (/ (current-index index-and-strides) (current-stride index-and-strides)))) (lambda (index-and-strides) (cons (modulo (current-index index-and-strides) (current-stride index-and-strides)) (cdr (strides-list index-and-strides)))) (cons index strides)))
Es así en Python:
def flat_to_multidimensional(sizes, index): import math if len(sizes) == 1: strides = [1] else: strides = ([1] + cumulative_product(sizes[:0:-1]))[::-1] def current_index(index_and_strides): return index_and_strides[0] def current_stride(index_and_strides): return strides_list(index_and_strides)[0] def strides_list(index_and_strides): return index_and_strides[1] def stop_p(index_and_strides): return len(strides_list(index_and_strides)) == 0 def generate(index_and_strides): return int(math.floor(current_index(index_and_strides) / current_stride(index_and_strides))) def update(index_and_strides): return (current_index(index_and_strides) % current_stride(index_and_strides), strides_list(index_and_strides)[1:]) seed = (index, strides) return tuple(unfold(stop_p, generate, update, seed))

Paso de índices multidimensionales a índices planos

El algoritmo es mucho más sencillo. Lo que hay que hacer es multiplicar cada índice por su vuelta correspondiente y sumar los resultados para obtener el índice plano. Podemos hacer esto con la función cumulative-product de ayer para calcular las vueltas (strides) igual que en flat->multidimensional, luego hacer map para multiplicar cada índice por su vuelta y finalmente hacer fold para hacer la suma; en vez de esto, vamos a hacer un único fold, lo que es posible gracias a la propiedad distributiva del producto sobre la suma. El algoritmo queda plasmado en la siguiente función flat->multidimensional de Scheme que acepta una lista sizes de tamaños de las diferentes dimensiones desde la primera (la del índice más a la izquierda) a la última (la del índice más a la derecha) y una lista de índices indices desde el primero (el que está más a la izquierda) hasta el último (el que está más a la derecha):
(define (multidimensional->flat sizes indices) (fold (lambda (index size accumulator) (+ (* size accumulator) (modulo index size))) 0 indices sizes))
Es así en Python:
def multidimensional_to_flat(sizes, indices): def accumulate(index, size, accumulator): return size * accumulator + index % size return fold(accumulate, 0, indices, sizes)

Otros artículos de la serie


Categorías: Informática

Permalink: http://sgcg.es/articulos/2013/08/27/jugando-con-automatas-celulares-7/