issue trying to implement a sum of subsets solution in python

Question

I am trying to write a brute-force solution to a sum of subsets problem in python but don't get any output... Am I going about this the right way/Any idea what i'm doing wrong?

my code:

def ss(set, tVal):
    #remove items greater than target from list
    cleaned = [c for c in set if c < tVal]
    #sort the list
    cleaned.sort()  

    occurance = 0
    leftIndex = 0
    rightIndex = len(cleaned) - 1
    print("rI length: ", rightIndex)

    while(leftIndex < rightIndex):
        #if target value found
        if cleaned[leftIndex] + cleaned[rightIndex] == tVal:
            print("found!!! ", cleaned[leftIndex], " + ", cleaned[rightIndex])
            #occurance += 1
            leftIndex += 1
            rightIndex += 1
        #else if left index + right index < target increment left index
        elif cleaned[leftIndex] + cleaned[rightIndex] < tVal:
            leftIndex += 1
        #otherwise decrement right index
        else:
            rightIndex -= 1

cities = [18897109, 12828837, 9661105, 6371773, 5965343, 5926800, 5582170, 5564635, 5268860, 4552402, 4335391, 4296250, 4224851, 4192887, 3439809, 3279933, 3095213, 2812896, 2783243, 2710489, 2543482, 2356285, 2226009, 2149127, 2142508, 2134411]
target = 101000000 

ss(cities, target)

Answer 1

Your cleaned usage is incorrect. I added a debug print to your code and found that the total was always more than tVal. Thus your if test always failed and did not print out the found message.

As an example

lIndex =  24 rIndex =  25
c[lIndex] =  12828837 c[rIndex] = 18897109
total  -  31725946 tval =  101000000

Alternatively put in an else for not found to see this.

The debug prints that showed this were

    while(leftIndex < rightIndex):
    print 'lIndex = ', leftIndex, 'rIndex = ', rightIndex
    print 'c[lIndex] = ', cleaned[leftIndex], 'c[rIndex] =', cleaned[rightIndex]
    mytot = cleaned[leftIndex] + cleaned[rightIndex]
    print 'total  - ', mytot, 'tval = ', tVal
    if mytot == tVal:
        print("found!!! ", cleaned[leftIndex], " + ", cleaned[rightIndex])
        leftIndex += 1
        rightIndex +=1
    elif cleaned[leftIndex] + cleaned[rightIndex] < tVal:
        leftIndex += 1
    else:
        rightIndex -= 1

Answer 2

It's a little unclear what you are trying to accomplish by reading the code versus what your problem description states. When you say: "sum of subsets", are you attempting to sum each possible subset (e.g. powerset) of those 25 cities?

If that is the case, then there are 2^n-1 possible subets, or for n = 25, 33,554,433. If you try to read that into memory at once by creating a list or set of all of those subsets, you will probably consume all your memory.

You can use a generator to stream the results one at a time, and check for a solution eg:

import itertools

cities = [18897109, 12828837, 9661105, 6371773, 5965343, 5926800, 5582170, 5564635, 5268860, 4552402, 4335391, 4296250, 4224851, 4192887, 3439809, 3279933, 3095213, 2812896, 2783243, 2710489, 2543482, 2356285, 2226009, 2149127, 2142508, 2134411]
target = 101000000 
ps = (set(itertools.combinations(cities,i)) for i in range(len(cities)))
for s in ps:
    for x in s:
        if sum(x) == target:
            print ('target reached:', x)

The accepted answer fixed your immediate problem, but I'm not sure if it is the correct solution to your described problem.

Answer 3

It seems there is no match in your test, that's why there is no output. I added some debug code to print every calc:

val is lower than tval 21031520 101000000
val is lower than tval 21039617 101000000
val is lower than tval 21046236 101000000
val is lower than tval 21123118 101000000
val is lower than tval 21253394 101000000
val is lower than tval 21440591 101000000
val is lower than tval 21607598 101000000
val is lower than tval 21680352 101000000
val is lower than tval 21710005 101000000
val is lower than tval 21992322 101000000
val is lower than tval 22177042 101000000
val is lower than tval 22336918 101000000
val is lower than tval 23089996 101000000
val is lower than tval 23121960 101000000
val is lower than tval 23193359 101000000
val is lower than tval 23232500 101000000
val is lower than tval 23449511 101000000
val is lower than tval 24165969 101000000
val is lower than tval 24461744 101000000
val is lower than tval 24479279 101000000
val is lower than tval 24823909 101000000
val is lower than tval 24862452 101000000
val is lower than tval 25268882 101000000
val is lower than tval 28558214 101000000
val is lower than tval 31725946 101000000

When I changed the target value to one of the sums, it found it.

>>> ss(cities, 21039617)
val is lower than tval 21031520 21039617
found.  1   25

Also, you have a problem with this code:

if cleaned[leftIndex] + cleaned[rightIndex] == tVal:
            print("found!!! ", cleaned[leftIndex], " + ", cleaned[rightIndex])
            #occurance += 1
            leftIndex += 1
            rightIndex += 1

If you enter this condition, you'll try to increase rightIndex by 1. If it wasn't reduced in previous loops, on the next call to cleaned[rightIndex] -->
IndexError: list index out of range.

You need to add a check if rightIndex is smaller than len(cleaned) - 1 first, and only then increase it. Otherwise leave it as it is.

Answer 4

Are you sure your target isn't off by an order of magnitude? Your left + right sums don't ever come close to tVal. Your code is functioning correctly, the loop just keeps incrementing leftIndex until while fails. A few print statements will help to see what's happening.

Modifying the inside of ss() slightly:

def ss(set, tVal):

    # ...

    print("target:       ", tVal) # spacing aligned for printing

    while(leftIndex < rightIndex):
        left_plus_right = cleaned[leftIndex] + cleaned[rightIndex]
        print("left + right: ", left_plus_right)

        if left_plus_right == tVal:
            print("found!!! ", cleaned[leftIndex], " + ", cleaned[rightIndex])
            leftIndex += 1
            rightIndex += 1
        elif left_plus_right < tVal:
            leftIndex += 1
        else:
            rightIndex -= 1

    # ...

Shows our sums are always roughly an order of magnitude smaller than target:

target:        101000000
left + right:  21031520
left + right:  21039617
left + right:  21046236
left + right:  21123118
left + right:  21253394
left + right:  21440591
left + right:  21607598
left + right:  21680352
left + right:  21710005
left + right:  21992322
left + right:  22177042
left + right:  22336918
left + right:  23089996
left + right:  23121960
left + right:  23193359
left + right:  23232500
left + right:  23449511
left + right:  24165969
left + right:  24461744
left + right:  24479279
left + right:  24823909
left + right:  24862452
left + right:  25268882
left + right:  28558214
left + right:  31725946