Permutaciones Lexicográficas.

En el campo de las matemáticas una permutación se remite a todas las posibles maneras en las que puede ordenarse un conjunto finito de elementos De este modo, una permutación puede ser vista como una combinación de elementos en donde el orden en el cual están dispuestos es un factor clave. Cabe mencionar que el número de permutaciones posible de un conjunto de n elementos es igual a n!.

Por otro lado, un orden lexicográfico hace referencia a la manera en que ordenan un conjunto de caracteres. Así, intersectando ambas definiciones, se produce lo que se conoce como una permutación lexicográfica: Conjunto de permutaciones enlistadas numérica o alfabéticamente. Considerando lo anterior, podemos argumentar que del conjunto finito {a, b, c} se pueden obtener las siguientes permutaciones:

bac
cba
abc
bca
acb

Las cuales ordenadas alfabéticamente, pueden ser dispuestas como:

abc
acb
bac
bca
cab
cba

El algoritmo para generar la siguiente permutación(es decir la permutación m+1) lexicográfica a partir de una permutación m constituida de  n elementos es el siguiente:

1. Encontrar el mayor valor de x tal que P[x] < P[x+1]. Si dicho valor de x no existe, entonces P es la última permutación lexicográfica que puede ser concebida por medio del conjunto de elementos que la conforman.
2. Encontrar el mayor valor de y tal que P[x]<P[y]. Si dicho valor de y no existe, entonces P es la última permutación lexicográfica que puede ser concebida por medio del conjunto de elementos que la conforman.
3. Intercambiar P[x] por P[y] y viceversa.
4. Invertir los elementos desde P[x+1] hasta P[n].

Por útlimo, el siguiente código en Python utiliza listas para implementar el algoritmo explicado anteriormente. El código posee comentarios para  que el lector pueda identificar facilmente los pasos de dicho algoritmo:

	def lexico( w ):
	x = y = -1
	# Paso 1
	for i in xrange(len(w)-2, -1, -1):
	if ord(w[i]) < ord(w[i+1]):
	x = i
	break
	if x == -1:
	return None
	# Paso 2
	for i in xrange(len(w)-1, x-1, -1):
	if ord(w[x]) < ord(w[i]):
	y = i
	break
	if y == -1:
	return None
	# Paso 3
	w[x], w[y] = w[y], w[x]
	# Paso 4
	p1 = w[:x+1]
	p2 = w[x+1:]
	p2.reverse()
	p1 += p2
	# Retornar nueva permutacion
	return p1

view raw permutaciones.py hosted with ❤ by GitHub

Anuncio publicitario