looping through loops in python?

Question

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.

As a side note, what you're calling arrays aren't arrays. They're lists (ArrayLists to be precise, but lists nonetheless). In Python, "arrays" usually refers to NumPy arrays, which are a different data structure. — Max Noel
– Max Noel, Commented Dec 6, 2013 at 7:08

perreal · Accepted Answer · 2013-12-06 06:08:35Z

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:

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

I don't know much about recursions, but this is something I'll have to start trying to learn, THanks!
Adding an explanation would probably be really good for the OP. Also, you should probably use .sort() instead of .sorted(). Nice solution, though.
I'm confused as to why when it loops into the if statement, the function just doesn't stop and return false. Instead it keeps looping. (eg. when n = 100 and arr = []

user2357112 · Accepted Answer · 2013-12-06 06:00:40Z

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

aIKid · Accepted Answer · 2013-12-06 06:07:27Z

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!

John La Rooy · Accepted Answer · 2013-12-06 06:21:43Z

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

Sravan K Ghantasala · Accepted Answer · 2013-12-06 06:24:24Z

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.. :)

VIKASH JAISWAL · Accepted Answer · 2013-12-06 06:37:07Z

0

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

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

answered Dec 6, 2013 at 6:37

VIKASH JAISWAL

8381 gold badge5 silver badges12 bronze badges

2 Comments

thefourtheye Over a year ago

Sorry, I believe you havnt understood the question correctly :)

VIKASH JAISWAL Over a year ago

Hmm, that's what I suspected :)

Collectives™ on Stack Overflow

looping through loops in python?

6 Answers 6

3 Comments

1 Comment

Comments

Comments

Comments

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

3 Comments

1 Comment

Comments

Comments

Comments

2 Comments

Related