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í.

Deja un comentario