Ejercicio: Tripletas.

Imagine tiene una lista no ordenada de n números enteros no repetidos los cuales pueden ser positivos, negativos o cero.  Encuentre los conjuntos de tres números cuya suma sea igual a cero. Ejemplo:

	# Lista
	lista = [ -1, 3, 2, 0, -5, -3 ]
	#Tripletas
	(-5, 2, 3), (-3, 0, 3), (-1, -1, 2)

view raw tripletaEjemplo.py hosted with ❤ by GitHub

El enfoque para solucionar este problema fue el siguiente:

1. Ordenar la lista en cuestión.
2. Particionar la lista ordenada en dos sub-listas. Una que albergue números negativos y la otra que guarde los números restantes(es decir, los números mayores o iguales a cero).
3. Iterar a través de los elementos de ambas sub-listas por medio de dos bucles anidados para encontrar los números cuya suma sea igual a cero.

Debido a que el paso 1 es muy claro, sólo se explicarán las implementaciones de los pasos 2 y 3. Por su parte, el paso 2 puesto en funcionamiento por medio del método getPartitionInt, el cual toma como parámetro de entrada una lista ordenada (obtenida en el paso 1) y devuelve el índice de la lista que posea el menor valor mayor o igual que cero. Más aún, éste método revisa que existan tanto números positivos como negativos en la lista, debido a que se necesitan tanto números negativos como positivos para realizar una suma igual a cero. De no cumplirse ésta condición, la función retornara -1. Por último, cabe decir que este método está basado en el algoritmo de Búsqueda Binaria por lo que su complejidad computacional es de O(log(n)).

	def getPartitionInt( alist ):
	low = 0
	high = len(alist)-1
	pos = len(alist)
	while low <= high:
	mid = (low+high)/2
	if alist[mid] < 0:
	low = mid + 1
	elif alist[mid] >= 0 and mid < pos:
	high = mid - 1
	pos = mid
	elif alist[mid] >= 0:
	high = mid - 1
	if pos == 0 or pos == len(alist):
	return -1
	else:
	return mid

view raw getPartitionInt.py hosted with ❤ by GitHub

Realizadas las revisiones correspondientes a los valores contenidos en la lista, el método triplets separa a los números negativos de los números restantes basado en la premisa de que se necesitan las siguientes combinaciones de números en la tripleta para calcular una suma igual a 0:

• Un número negativo y dos positivos.
• Un número positivo y dos negativos.
• Un número negativo, un número positivo y el cero.

	def triplets( alist ):
	alist.sort()
	p = getPartitionInt( alist )
	trips = set()
	if p == -1:
	return "No Triplets"
	glz = alist[:p]
	gez = alist[p:]
	for l in glz:
	for e in gez:
	if -(l+e) < 0:
	x = binarySearch(glz, -(l+e))
	else:
	x = binarySearch(gez, -(l+e))
	if x:
	t = [l,e,-(l+e)]
	t.sort()
	trips.add(tuple(t))
	return trips

view raw triplets.py hosted with ❤ by GitHub

Por su parte, Las líneas 13 a 18 del método triplets también están basadas en ese supuesto. No obstante las líneas 15 y 17 están justificadas por medio de una ecuación. Suponiendo que x + y + z = 0, entonces x = -(y+z). De este modo, si x resultara ser negativa entonces sólo bastaría con realizar una búsqueda binaria de x en la sub-lista ordenada de números negativos. De manera contraria, si x fuera positiva, solo bastaría con hacer una búsqueda binaría de x en la sub-lista ordenada de números positivos. El método binarySearch provee tal búsqueda y por ende también posee una complejidad computacional de O(log(n)).

	def binarySearch( alist, anum ):
	low = 0
	high = len(alist)-1
	while low <= high:
	mid = (low + high)/2
	if alist[mid] == anum:
	return True
	if alist[mid] < anum:
	low = mid + 1
	else:
	high = mid -1
	return False

view raw binarySearch.py hosted with ❤ by GitHub

El código completo puede ser descargado desde aquí.

Anuncio publicitario