CODEWITHSUNDEEP
pythoniteration
user3015876
user3015876

Reputation: 133

looping through loops in python?

I'm trying to solve this problem on the easy section of coderbyte and the prompt is:

Have the function ArrayAdditionI(arr) take the array of numbers stored in arr and return the string true if any combination of numbers in the array can be added up to equal the largest number in the array, otherwise return the string false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23. The array will not be empty, will not contain all the same elements, and may contain negative numbers.

Here's my solution.

def ArrayAddition(arr):
arr = sorted(arr, reverse=True)
large = arr.pop(0)
storage = 0
placeholder = 0
for r in range(len(arr)):
    for n in arr:
        if n + storage == large: return True
        elif n + storage < large: storage += n
        else: continue
    storage = 0
    if placeholder == 0: placeholder = arr.pop(0)
    else: arr.append(placeholder); placeholder = arr.pop(0)
return False

print ArrayAddition([2,95,96,97,98,99,100])

I'm not even sure if this is correct, but it seems to cover all the numbers I plug in. I'm wondering if there is a better way to solve this through algorithm which I know nothing of. I'm thinking a for within a for within a for, etc loop would do the trick, but I don't know how to do that.

What I have in mind is accomplishing this with A+B, A+C, A+D ... A+B+C ... A+B+C+D+E

e.g) 

for i in range(len(arr):
print "III: III{}III".format(i)
storage = []
for j in range(len(arr):
    print "JJ: II({}),JJ({})".format(i,j)

    for k in range(len(arr):
        print "K: I{}, J{}, K{}".format(i,j,k)

I've searched all over and found the suggestion of itertool, but I'm wondering if there is a way to write this code up more raw.

Thanks.

Upvotes: 8

Views: 340

Answers (6)

VIKASH JAISWAL
VIKASH JAISWAL

Reputation: 838

If I understood the question correctly, simply this should return what you want:

2*max(a)<=sum(a)

Upvotes: 0

Sravan K Ghantasala
Sravan K Ghantasala

Reputation: 1338

One more way to do it...

Code:

import itertools
def func(l):
    m = max(l)
    rem = [itertools.combinations([x for x in l if not x == m],i) for i in range(2,len(l)-1)]
    print [item for i in rem for item in i if sum(item)==m ]


if __name__=='__main__':
    func([1,2,3,4,5])

Output:

[(1, 4), (2, 3)]

Hope this helps.. :)

Upvotes: 0

John La Rooy
John La Rooy

Reputation: 304473

Generate all the sums of the powerset and test them against the max

def ArrayAddition(L):
    return any(sum(k for j,k in enumerate(L) if 1<<j&i)==max(L) for i in range(1<<len(L)))

You could improve this by doing some preprocessing - find the max first and remove it from L

Upvotes: 0

perreal
perreal

Reputation: 98118

A recursive solution:

def GetSum(n, arr):
    if len(arr) == 0 and n != 0:
        return False
    return (n == 0 or  
      GetSum(n, arr[1:]) or  
      GetSum(n-arr[0], arr[1:]))

def ArrayAddition(arr):
    arrs = sorted(arr)
    return GetSum(arrs[-1], arrs[:-1])

print ArrayAddition([2,95,96,97,98,99,100])

The GetSum function returns False when the required sum is non-zero and there are no items in the array. Then it checks for 3 cases:

  1. If the required sum, n, is zero then the goal is achieved.
  2. If we can get the sum with the remaining items after the first item is removed, then the goal is achieved.
  3. If we can get the required sum minus the first element of the list on the rest of the list the goal is achieved.

Upvotes: 4

aIKid
aIKid

Reputation: 28332

Update: I forgot that you want to check all possible combinations. Use this instead:

def ArrayAddition(l):
    for length in range(2, len(l)):
        for lst in itertools.combinations(l, length):
            if sum(lst) in l:
                print(lst, sum(lst))
                return True
    return False

One-liner solution:

>>> any(any(sum(lst) in l for lst in itertools.combinations(l, length)) for length in range(2, len(l)))

Hope this helps!

Upvotes: 0

user2357112
user2357112

Reputation: 281997

Your solution doesn't work.

>>> ArrayAddition([10, 11, 20, 21, 30, 31, 60])
False

The simple solution is to use itertools to iterate over all subsets of the input (that don't contain the largest number):

def subsetsum(l):
    l = list(l)
    target = max(l)
    l.remove(l)
    for subset_size in xrange(1+len(l)):
        for subset in itertools.combinations(l, subset_size):
            if sum(subset) == target:
                return True
    return False

If you want to avoid itertools, you'll need to generate subsets directly. That can be accomplished by counting in binary and using the set bits to determine which elements to pick:

def subsetsum(l):
    l = list(l)
    target = max(l)
    l.remove(l)
    for subset_index in xrange(2**len(l)):
        subtotal = 0
        for i, num in enumerate(l):
            # If bit i is set in subset_index
            if subset_index & (1 << i):
                subtotal += num
        if subtotal == target:
            return True
    return False

Upvotes: 2

Related Questions