#======================================================================
# Author: Isai Damier
# Title: Sum of Tuple
# Project: geekviewpoint
# Package: algorithms
#
# Statement:
# Given a list of integers, find all k-tuples that sum up to s.
# Use the power set algorithm.
#
# Sample Input: array= [1,2,3,4,-3,-5], s= 0
# Sample Output: [[1,2,-3],[1,4,-5],[2,3,-5]]
#
# Technical Details:
# 1] loop through the power set of the list,
# 2] for each subset that contains k-tuple elements, sum up
# the elements
# 3] if the calculation match the target sum, print the
# subset.
#
# Note: This solution is by no means efficient. We are using a power set
# to solve a particular problem: namely, the sums from subsets of a
# specific size -- namely k-tuple.
#
# Given a set of size n, a powerset is the set of all possible
# combinations C(n,k) for all k between 0 and n (i.e. 0 <= k <= n).
# The "Sum of Tuple" problem, even in its general form, is always
# interested in the solution for a particular k. Therefore, a powerset
# is a wasteful approach for solving this problem.
#
# Use powerSet on problems that need it. Use "All Combinations"
# or recursion-with-memoization on problems that need them.
# (http://geekviewpoint.com/python/numbers/all_combinations)
#======================================================================
def sumOfTuple( _array, _tuple, _sum ):
arrayLength = len( _array )
bits = "1"*arrayLength
power = int( bits, 2 )
result = []
group = []
while 0 < power:
# if subset only has tuple number of elements
if _tuple == countBits( power ):
bits = bin( power )[2:]
# sum up the elements
calc = 0
del group[:]
k = arrayLength - len( bits )
for b in bits:
if '1' == b:
calc += _array[k]
group.append( _array[k] )
k += 1
# if the calculated sum matches the requirement, print
if calc == _sum:
result.append( list( group ) )
power -= 1
return result
import unittest
from algorithms import bitwise as bits
class Test( unittest.TestCase ):
def testSumOfTuple( self ):
_tuple = 3
_sum = 15
A = [2, 3, 4, 5, 6, 7, 9, 15, 0, -2, -3, -4, -5, -6]
exp = [[2, 4, 9], [2, 6, 7], [2, 15, -2], [3, 5, 7],
[3, 15, -3], [4, 5, 6], [4, 15, -4], [5, 15, -5],
[6, 9, 0], [6, 15, -6]]
self.assertEquals( exp, bits.sumOfTuple( A, _tuple, _sum ) )
