I need to write a function that takes in an array of integers and an integer, checks if the sum of any of the numbers in the array is equal to the supplied integer.
Any ideas would be much appreciated.
I need to write a function that takes in an array of integers and an integer, checks if the sum of any of the numbers in the array is equal to the supplied integer.
Any ideas would be much appreciated.
Well, I'm sure there are quite a few ways with pros and cons to each, but my computer was able to run this test code (below) with lists containing 8000 random values (each less than 10000), in less than 1 minute. If I needed to do this with really big arrays then I would look at generators, to compare the number to each "sum" as the generator does the enumeration of possible sums so I didn't need to store the whole list. Unless your going to reuse the enumeration of sums of course...
def one_way(your_num, your_array):
import time
start_time = time.time()
sum_enumeration = []
your_list = your_array.tolist()
your_list = list(set(your_list))
max_sum = (your_list[-1] + your_list[-2])
min_sum = (your_list[0] + your_list[1])
print "Max sum: ", max_sum
print "Min sum: ", min_sum
if your_num <= max_sum and your_num >= min_sum:
for x in range(len(your_list)):
current_element = your_list[x]
for number in your_list:
if number != current_element:
sum_enumeration.append(current_element + number)
sum_enumeration = list(set(sum_enumeration))
if your_num in sum_enumeration:
print "%s is indeed the sum of two elements of the array" % (your_num)
else:
print "%s is not the sum of two elements of the array" % (your_num)
else:
print "%s is not the sum of two elements of the array" % (your_num)
end_time = time.time()
print "Unique elements in list:", len(your_list)
print "Sum's enumerated:", len(sum_enumeration)
print "Total time: %i" % (end_time-start_time)
Of course, that was assuming you want to compare the number to the sum of any two unique numbers in the array, not including a number plus itself.
Thank you very much for the help.
What I was actually looking for was that the sum could constitute of any possible combination of the supplied numbers (preferably including the number itself.)
But still this is great help as I don't understand some of the statements like
list(set(my_list))
which gets me motivated to learn more of the language and techniques. And the way of the program is pretty neat too.
NewbieXcellence import statement shall never be inside a function always on top.
And the script dont work,where come tolist() from your_array.tolist()
Get this errormessage.
This is when you give function a number and a list one_way(5, [1,5,4])
exceptions.AttributeError: 'list' object has no attribute 'tolist'
*can't find the delete post button*
You can not delete post,think off it all question can help other pepole to learn.
It you delete it,you delete answer you got to.
That had been no good.
list(set(my_list))
>>> l = ['my', 'car', 'is', 'black', 'black', 'black']
>>> set(l)
set(['black', 'car', 'is', 'my'])
>>> #set remove equal elements in a list
>>> list(set(l))
['car', 'is', 'my', 'black']
>>> #This take set back to a list again,set and dictionary dont keep order off elements
NewbieXcellence import statement shall never be inside a function always on top.
And the script dont work,where come tolist() from your_array.tolist()Get this errormessage.
This is when you give function a number and a list one_way(5, [1,5,4])
exceptions.AttributeError: 'list' object has no attribute 'tolist'Well, it's not meant to be passed a list, it's meant to be passed an array which is converted to a list using tolist... I never actually tested it with an array though, I was using lists to test it myself, but with the one line with "tolist" commented out, so you'll either have to comment out that line or pass it an array.
What I was actually looking for was that the sum could constitute of any possible combination of the supplied numbers (preferably including the number itself.)
Wouldn't that be an ENDLESS number of possibile sums? IE: if your array had (1,2) in it, you you could make any possible number? I'm just trying to wrap my head around what you are trying to do here :) I'm sure we can come up with SOMETHING for you :)
I think it's simple as this:
list1 = [1, 5, 3, 9, 4]
int1 = 8
list2 = [item + item for item in list1]
if int1 in list2:
print int1, 'is the sum of', int1/2
else:
print int1, 'is not the sum of any of the numbers in the list'
or
list1 = [1, 5, 3, 9, 4]
int1 = 8
for item in list1:
if item + item == int1:
print int1, 'is the sum of', item
break
else:
print int1, 'is not the sum of any of the numbers in the list'
Cheers and Happy coding
Beat_Slayer, the OP said he wanted it so that "the sum could constitute of any possible combination of the supplied numbers", so the list you made with each number from the array doubled is really just a small subset of what the OP is looking for (I think! ;p)
If I understand what you want correctly guyfrompluto, I think it could be accomplished by seeing if:
"the number" - <a number from the array> == <any number from the array> OR <a factor of "the number" which is in the array> ..... or something along those lines? I will have to think this through more though, I'll try to pound out some code later this evening :)
list1 = [1, 5, 3, 9, 4]
int1 = 8
found = None
for x in list1:
for y in list1:
if (x + y) == int1:
print int1, 'is the sum of', x, 'and', y
found = True
if not found:
print int1, 'is not the sum of any of the numbers in the list'
Cheers and Happy coding
EDIT: Returning to the drawing table :)
Thank you for the solutions but as I mentioned earlier the sum could constitute of any combination of the numbers, not just two unique integers which is easily solvable.
I find the links provided to be too advanced/irrevalent for me, excuse my noobness.
Still working for a solution.
You can not delete post,think off it all question can help other pepole to learn.
It you delete it,you delete answer you got to.
That had been no good.
What I meant was I accidentally double posted but couldn't find a way to delete the post, not the entire thread.
Simplistic summing of every possibility:
from __future__ import print_function
def subset(seq, mask):
""" binary mask of len(seq) bits, return generator for the sequence """
return (c for ind,c in enumerate(seq) if mask & (1<<ind))
numbers = [1, 5, 3, 9, 4]
print('Numbers: ',numbers)
print('Possible sums',min(numbers),'..',sum(numbers))
for i in range(1,2**len(numbers)):
sub = list(subset(numbers, i))
print(sum(sub),'=',' + '.join(str(s) for s in sub))
print()
target = 11
print ('Finding subsequence for sum = %i' % target)
check = None
for check in (subset(numbers, mask)
for mask in range(1,2**len(numbers))
if sum(subset(numbers, mask))==target):
print (' + '.join(str(s) for s in check), ' = ', target)
if not check:
print('No solutions')
Well, it's not meant to be passed a list, it's meant to be passed an array which is converted to a list using tolist.
When we take about array in python we mean list.
my_array = [1,2,3]
my_list = [1,2,3]
Is both ok.
Make a list or in other languages is called array.
There are and not so much used array module in python(import array)
Something like this,not quite finish need off couse else clause if no match found.
def subsets_i(s):
subsets = []
n_elems = len(s)
n_subsets = 2**len(s)
for i in range(0,n_subsets):
sub = []
for j in range(0,n_elems):
if (i >> j & 1):
sub.append(s[j])
subsets.append(sub)
return subsets
def compare_sum(n ,l):
'''
Take argument integer(n) and subset_list(l)
Compare if sum off any number in list(l)
Are equal to integer(n)
'''
count = 0
for i in l:
if sum(i) == n:
count += 1
print 'There are %s number combination in my_list that sums upp to %d' % (count, n)
if __name__ == '__main__':
my_list = [1, 5, 3, 9, 4]
my_number = 8
sub_l = subsets_i(my_list)
compare_sum(my_number, sub_l)
'''Out-->
There are 2 number combination in my_list that sums upp to 8
'''
What the OP described is a variation of the Knapsack Problem, which is NP-complete (i.e. known to be very difficult from a computational viewpoint).
Still not totally finished, since I want to optimize it, but... It does the job.
list1 = [1, 5, 3, 9, 4, 2, 7, 8]
list1 = range(10, 75)
int1 = 60
print 'List:', ', '.join([str(i) for i in list1])
list1 = list(set(list1))
list1 = [item for item in list1 if item <= int1 and (item + min(list1)) <= int1]
print 'Clean List:', ', '.join([str(i) for i in list1])
list2 = list1[:]
pre_valid_sums = []
for x in list1:
list2 = list1[:]
list2.remove(x)
for rotation in range(len(list2)):
r = list2.pop(0)
list2.append(r)
list3 = list2[:]
for redution in range(len(list2) - 1):
list3.pop()
for iteration in range(len(list3) - 1):
list4 = list3[:]
list4.pop(iteration)
if (x + sum(list4)) == int1:
pre_valid_sums.append(sorted([x] + list4))
valid_sums = []
for sums in pre_valid_sums:
if sums not in valid_sums:
valid_sums.append(sums)
for sums in valid_sums:
print '%s is the sum of %s' % (int1, ', '.join([str(i) for i in sums]))
Cheers and Happy coding
Bent slayer_Slayer you are missing number combination in your code.
Here a test with range(10, 20) and number 60.
range(10, 75) will but my code down.
Example off one miss.
>>> sum([12, 14, 16, 18])
60
>>>
def subsets_i(s):
subsets = []
n_elems = len(s)
n_subsets = 2**len(s)
for i in range(0,n_subsets):
sub = []
for j in range(0,n_elems):
if (i >> j & 1):
sub.append(s[j])
subsets.append(sub)
return subsets
def compare_sum(n ,l):
'''
Take argument integer(n) and list(l)
Compare if sum off any number in list(l)
Are equal to integer(n)
'''
count = 0
for i in l:
if sum(i) == n:
count += 1
print i
print 'There are %s number combination in my_list that sums upp to %d' % (count, n)
if __name__ == '__main__':
my_list = range(10, 20)
my_number = 60
sub_l = subsets_i(my_list)
compare_sum(my_number, sub_l)
'''Out-->
[10, 11, 12, 13, 14]
[13, 14, 16, 17]
[12, 15, 16, 17]
[13, 14, 15, 18]
[12, 14, 16, 18]
[11, 15, 16, 18]
[12, 13, 17, 18]
[11, 14, 17, 18]
[10, 15, 17, 18]
[12, 14, 15, 19]
[12, 13, 16, 19]
[11, 14, 16, 19]
[10, 15, 16, 19]
[11, 13, 17, 19]
[10, 14, 17, 19]
[11, 12, 18, 19]
[10, 13, 18, 19]
There are 17 number combination in my_list that sums upp to 60
'''
#list1 = [1, 5, 3, 9, 4, 2, 7, 8]
list1 = range(10, 20)
int1 = 60
print 'List:', ', '.join([str(i) for i in list1])
list1 = list(set(list1))
list1 = [item for item in list1 if item <= int1 and (item + min(list1)) <= int1]
print 'Clean List:', ', '.join([str(i) for i in list1])
list2 = list1[:]
pre_valid_sums = []
for x in list1:
list2 = list1[:]
list2.remove(x)
for rotation in range(len(list2)):
r = list2.pop(0)
list2.append(r)
list3 = list2[:]
for redution in range(len(list2) - 1):
list3.pop()
for iteration in range(len(list3) - 1):
list4 = list3[:]
list4.pop(iteration)
if (x + sum(list4)) == int1:
pre_valid_sums.append(sorted([x] + list4))
valid_sums = []
for sums in pre_valid_sums:
if sums not in valid_sums:
valid_sums.append(sums)
for sums in valid_sums:
print '%s is the sum of %s' % (int1, ', '.join([str(i) for i in sums]))
'''Out-->
60 is the sum of 10, 15, 17, 18
60 is the sum of 10, 11, 12, 13, 14
60 is the sum of 11, 15, 16, 18
60 is the sum of 11, 12, 18, 19
60 is the sum of 12, 15, 16, 17
60 is the sum of 13, 14, 16, 17
60 is the sum of 10, 13, 18, 19
60 is the sum of 10, 14, 17, 19
60 is the sum of 13, 14, 15, 18
60 is the sum of 12, 14, 15, 19
'''
Thanks snippsat, I'll look at it. :)
I was using a small list during the build it did'nt shouwed up, back to the drawing table. lol
Cheers and Happy coding
Some basic optimization by checking limits and maximum number of terms and combinations:
from __future__ import print_function
from time import clock
import itertools as it
def subset(seq, mask):
""" binary mask of len(seq) bits, return generator for the sequence """
return (c for ind,c in enumerate(seq) if mask & (1<<ind))
def allsubsets_bruteforce(seq, target = None):
for i in range(1,2**len(seq)):
yield list(subset(seq, i))
def allsubsets_combinations(seq, target = None):
minimum_value = min(seq)
if target and (target < min(seq) or target > sum(seq)):
raise StopIteration
maxnumber_of_terms = target//minimum_value if target else len(seq)
for num_items in range(1,maxnumber_of_terms):
for subseq in it.combinations(seq, num_items):
yield subseq
def findsum(seq, target, subsetfunction = allsubsets_combinations):
for check in (selection
for selection in subsetfunction(seq, target)
if sum(selection)==target):
yield check
numbers = range(10, 30)
verbose = False
print('Numbers: ',numbers)
for target in (9, 60, 345):
print ('Finding subsequence for sum = %i' % target)
for subsetfunction in (allsubsets_combinations, allsubsets_bruteforce):
time = clock()
print('Using function %s to find possible subsets' % (str(subsetfunction).split()[1]))
count = -1
for count, solution in enumerate(findsum(numbers, target, subsetfunction)):
if verbose:
print ("%3d" % (count+1), ':',
' + '.join(str(number) for number in solution),
' = ', target)
print('No solutions' if not (count + 1)
else ('%i solutions' % (count + 1)))
print("Total time: %.0f ms" % (1000 * (clock() - time)))
print (50 * "-")
""" Nonverbose output:
Numbers: [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
Finding subsequence for sum = 9
Using function allsubsets_combinations to find possible subsets
No solutions
Total time: 14 ms
--------------------------------------------------
Using function allsubsets_bruteforce to find possible subsets
No solutions
Total time: 16974 ms
--------------------------------------------------
Finding subsequence for sum = 60
Using function allsubsets_combinations to find possible subsets
93 solutions
Total time: 234 ms
--------------------------------------------------
Using function allsubsets_bruteforce to find possible subsets
93 solutions
Total time: 18529 ms
--------------------------------------------------
Finding subsequence for sum = 345
Using function allsubsets_combinations to find possible subsets
26 solutions
Total time: 1148 ms
--------------------------------------------------
Using function allsubsets_bruteforce to find possible subsets
26 solutions
Total time: 16772 ms
--------------------------------------------------
"""
guyfrompluto,
Hello. I am new to this forum, so please forgive my unintentional gaffs and lack of decorum. If you don't have an answer yet to your query, try the following function. I think it meets your original specifications. With a few modifications, it could also return the list subset that adds up to the specified sum.
def isSum(sumInteger, listOfInts):
tempList = list(listOfInts)
tempList.sort()
sumValue = 0.0
for item in tempList:
sumValue += item
if sumValue == sumInteger:
return True
if sumValue > sumInteger:
break
return False
Good luck!!
Had a litle time to look at it and,
list1 = range(10, 20)
int1 = 60
print 'List:', ', '.join([str(i) for i in list1])
list1 = list(set(list1))
list1 = [item for item in list1 if (item + min(list1)) <= int1]
print 'Clean List:', ', '.join([str(i) for i in list1])
subsets_list = []
valid_sums = []
def subsets(nlist, wanted, max_list_size):
for iteration in range(len(nlist)):
ilist = nlist[:]
ilist.pop(iteration)
if ilist not in subsets_list:
subsets_list.append(ilist)
if len(ilist) <= max_list_size:
if sum(ilist) == wanted and ilist not in valid_sums:
valid_sums.append(ilist)
elif len(ilist) >= 3:
subsets(ilist, wanted, max_list_size)
elif len(ilist) >= 3:
subsets(ilist, wanted, max_list_size)
max_list_possible = lambda((x, mlist)): x / min(mlist)
subsets(list1, int1, max_list_possible((int1, list1)))
print '%s is the sum of %s subsets from the %s subsets calculated' % (int1, len(valid_sums), len(subsets_list))
for sums in valid_sums:
print '%s is the sum of %s' % (int1, ', '.join([str(i) for i in sums]))
Cheers and Happy coding
Had time to finnally optimize it using itertools now.
from itertools import combinations
import time
list1 = range(10, 30)
int1 = 60
print 'List:', ', '.join([str(i) for i in list1])
list1 = list(set(list1))
list1 = [item for item in list1 if (item + min(list1)) <= int1]
print 'Clean List:', ', '.join([str(i) for i in list1])
subsets_list = []
def min_list(x, mlist):
m, rest = divmod(x, max(mlist))
if rest:
return m + 1
else:
return m
def max_list(x, mlist):
m, rest = divmod(x, min(mlist))
if not rest:
return m - 1
else:
return m
def subsets(nlist, wanted, min_list_size, max_list_size):
for s in range(min_list_size, max_list_size + 1):
rlist = [item for item in nlist if item >= (wanted / len(nlist))]
for item in combinations(rlist, s):
subsets_list.append(item)
t1 = time.clock()
subsets(list1, int1, min_list(int1, list1), max_list(int1, list1))
t2 = time.clock()
print 'Subsets took %0.3f ms to calculate %s subsets' % ((t2 - t1) * 1000.0, len(subsets_list))
valid_sums = [item for item in subsets_list if sum(item) == int1]
print '%s is the sum of %s subsets' % (int1, len(valid_sums))
for sums in valid_sums:
print '%s is the sum of %s' % (int1, ', '.join([str(i) for i in sums]))
Cheers and Happy coding
Had time to finnally optimize it using itertools now.
from itertools import combinations import time list1 = range(10, 30) int1 = 60 print 'List:', ', '.join([str(i) for i in list1]) list1 = list(set(list1)) list1 = [item for item in list1 if (item + min(list1)) <= int1] print 'Clean List:', ', '.join([str(i) for i in list1]) subsets_list = [] def min_list(x, mlist): m, rest = divmod(x, max(mlist)) if rest: return m + 1 else: return m def max_list(x, mlist): m, rest = divmod(x, min(mlist)) if not rest: return m - 1 else: return m def subsets(nlist, wanted, min_list_size, max_list_size): for s in range(min_list_size, max_list_size + 1): rlist = [item for item in nlist if item >= (wanted / len(nlist))] for item in combinations(rlist, s): subsets_list.append(item) t1 = time.clock() subsets(list1, int1, min_list(int1, list1), max_list(int1, list1)) t2 = time.clock() print 'Subsets took %0.3f ms to calculate %s subsets' % ((t2 - t1) * 1000.0, len(subsets_list)) valid_sums = [item for item in subsets_list if sum(item) == int1] print '%s is the sum of %s subsets' % (int1, len(valid_sums)) for sums in valid_sums: print '%s is the sum of %s' % (int1, ', '.join([str(i) for i in sums]))
Cheers and Happy coding
Failed with my random inputs:
beat([18, 20, 53, 86, 91, 3, 13, 88, 4, 31, 21, 66, 66, 93, 14, 2, 67, 56, 46, 2], 816)
List: 18, 20, 53, 86, 91, 3, 13, 88, 4, 31, 21, 66, 66, 93, 14, 2, 67, 56, 46, 2
Clean List: 66, 3, 4, 2, 13, 14, 56, 18, 67, 20, 53, 86, 88, 46, 91, 21, 93, 31
Subsets took 3.973 ms to calculate 1 subsets
816 is the sum of 0 subsets
Correct answer:
Using function allsubsets_combinations to find possible subsets
------------------------------------------------------------
First solution: 1.190 s
1: 18 + 20 + 53 + 86 + 91 + 88 + 31 + 21 + 66 + 66 + 93 + 14 + 67 + 56 + 46 = 816
2: 18 + 53 + 86 + 91 + 3 + 13 + 88 + 4 + 31 + 21 + 66 + 66 + 93 + 14 + 67 + 56 + 46 = 816
3: 20 + 53 + 86 + 91 + 3 + 13 + 88 + 31 + 21 + 66 + 66 + 93 + 14 + 2 + 67 + 56 + 46 = 816
4: 20 + 53 + 86 + 91 + 3 + 13 + 88 + 31 + 21 + 66 + 66 + 93 + 14 + 67 + 56 + 46 + 2 = 816
5: 18 + 20 + 53 + 86 + 91 + 13 + 88 + 4 + 31 + 66 + 66 + 93 + 14 + 2 + 67 + 56 + 46 + 2 = 816
6: 18 + 53 + 86 + 91 + 3 + 13 + 88 + 31 + 21 + 66 + 66 + 93 + 14 + 2 + 67 + 56 + 46 + 2 = 816
6 solutions
Total time: 1.444 s
My version was written taking in count that no duplicates were used. Line 9 makes it pretty clear.
I can do a quick mod do accept duplicates.
I'll be back :D
Cheers and Happy coding
EDIT:
from itertools import combinations
import time
list1 = [18, 20, 53, 86, 91, 3, 13, 88, 4, 31, 21, 66, 66, 93, 14, 2, 67, 56, 46, 2]
int1 = 816
duplicates = True
print 'List:', ', '.join([str(i) for i in list1])
if not duplicates:
list1 = list(set(list1))
list1 = [item for item in sorted(list1) if (item + min(list1)) <= int1]
print 'Clean List:', ', '.join([str(i) for i in list1])
subsets_list = []
def min_list(x, mlist):
m, rest = divmod(x, max(mlist))
if rest:
return m + 1
else:
return m
def max_list(x, mlist):
m, rest = divmod(x, min(mlist))
if not rest:
return m - 1
else:
return m
def subsets(nlist, wanted, min_list_size, max_list_size):
for s in range(min_list_size, max_list_size + 1):
if not duplicates:
rlist = [item for item in nlist if item >= (wanted / len(nlist))]
nlist = rlist
for item in combinations(nlist, s):
subsets_list.append(item)
t1 = time.clock()
subsets(list1, int1, min_list(int1, list1), max_list(int1, list1))
t2 = time.clock()
print 'Subsets took %0.3f ms to calculate %s subsets' % ((t2 - t1) * 1000.0, len(subsets_list))
valid_sums = [item for item in subsets_list if sum(item) == int1]
print '%s is the sum of %s subsets' % (int1, len(valid_sums))
for sums in valid_sums:
print '%s is the sum of %s' % (int1, ', '.join([str(i) for i in sums]))
Cheers and Happy coding
Faster...
from itertools import combinations
import time
list1 = [18, 20, 53, 86, 91, 3, 13, 88, 4, 31, 21, 66, 66, 93, 14, 2, 67, 56, 46, 2]
int1 = 816
duplicates = True
print 'List:', ', '.join([str(i) for i in list1])
if not duplicates:
list1 = list(set(list1))
list1 = [item for item in sorted(list1) if (item + min(list1)) <= int1]
print 'Clean List:', ', '.join([str(i) for i in list1])
def min_list(x, mlist):
m, rest = divmod(x, max(mlist))
if rest:
return m + 1
else:
return m
def max_list(x, mlist):
m, rest = divmod(x, min(mlist))
if not rest:
return m - 1
else:
return m
def subsets(nlist, wanted, min_list_size, max_list_size):
for s in range(min_list_size, max_list_size + 1):
for item in combinations(nlist, s):
if sum(item) == int1:
yield item
t1 = time.clock()
valid_sums = []
for valid in subsets(list1, int1, min_list(int1, list1), max_list(int1, list1)):
valid_sums.append(valid)
t2 = time.clock()
print 'Subsets took %0.3f ms' % ((t2 - t1) * 1000.0)
print '%s is the sum of %s subsets' % (int1, len(valid_sums))
for sums in valid_sums:
print '%s is the sum of %s' % (int1, ', '.join([str(i) for i in sums]))
Cheers and Happy coding