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.
guyfrompluto 0 Newbie Poster
NewbieXcellence 0 Light Poster
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) NewbieXcellence 0 Light Poster
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.
guyfrompluto 0 Newbie Poster
*can't find the delete post button*
guyfrompluto 0 Newbie Poster
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.
snippsat 661 Master Poster
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 0 Light Poster
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.
NewbieXcellence 0 Light Poster
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 :)
Beat_Slayer 17 Posting Pro in Training
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
NewbieXcellence 0 Light Poster
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)
NewbieXcellence 0 Light Poster
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 :)
TrustyTony 888 pyMod Team Colleague Featured Poster
Beat_Slayer 17 Posting Pro in Training
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 :)
guyfrompluto 0 Newbie Poster
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.
TrustyTony 888 pyMod Team Colleague Featured Poster
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') snippsat 661 Master Poster
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
'''
arkoenig 340 Practically a Master Poster
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).
Beat_Slayer 17 Posting Pro in Training
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
snippsat 661 Master Poster
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
''' Beat_Slayer 17 Posting Pro in Training
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
TrustyTony 888 pyMod Team Colleague Featured Poster
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
--------------------------------------------------
""" ChrisJones2102 0 Newbie Poster
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 FalseGood luck!!
Beat_Slayer 17 Posting Pro in Training
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
Beat_Slayer 17 Posting Pro in Training
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
TrustyTony 888 pyMod Team Colleague Featured Poster
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 subsetsCorrect 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 Beat_Slayer 17 Posting Pro in Training
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
Beat_Slayer 17 Posting Pro in Training
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
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.