hi, i need to find which elements of an array sums up to an specific value any idea of how to do this? best, rf -- GNU/Linux User #479299 skype: fabbri.renato
Thu, 01 Jul 2010 06:17:50 -0300, Renato Fabbri wrote:
i need to find which elements of an array sums up to an specific value
any idea of how to do this?
Sounds like the knapsack problem http://en.wikipedia.org/wiki/Knapsack_problem
On Thu, Jul 1, 2010 at 3:17 AM, Renato Fabbri <renato.fabbri@gmail.com> wrote:
hi, i need to find which elements of an array sums up to an specific value
any idea of how to do this?
Not sure if there is a better way but a brut force way would be to
a array([[ 7., 5., 9., 3.], [ 7., 2., 7., 8.], [ 6., 8., 3., 2.]]) alist= a.flatten() alist [7.0, 5.0, 9.0, 3.0, 7.0, 2.0, 7.0, 8.0, 6.0, 8.0, 3.0, 2.0] asolution = [] for r in range(len(alist): for comb in itertools.combinations(alist, r): if sum(comb)==TheValue: asolution.append(comb)
Now just find the comb values in the array. Like I said kinda brute force. Also depends if you want all solutions or a solution. Vincent
best, rf
-- GNU/Linux User #479299 skype: fabbri.renato _______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
just a solution (not all of them) and the application happen to come up with something like 10k values in the array. don care waiting, but... 2010/7/1 Vincent Davis <vincent@vincentdavis.net>:
On Thu, Jul 1, 2010 at 3:17 AM, Renato Fabbri <renato.fabbri@gmail.com> wrote:
hi, i need to find which elements of an array sums up to an specific value
any idea of how to do this?
Not sure if there is a better way but a brut force way would be to
a array([[ 7., 5., 9., 3.], [ 7., 2., 7., 8.], [ 6., 8., 3., 2.]]) alist= a.flatten() alist [7.0, 5.0, 9.0, 3.0, 7.0, 2.0, 7.0, 8.0, 6.0, 8.0, 3.0, 2.0] asolution = [] for r in range(len(alist): for comb in itertools.combinations(alist, r): if sum(comb)==TheValue: asolution.append(comb)
Now just find the comb values in the array.
Like I said kinda brute force. Also depends if you want all solutions or a solution.
Vincent
best, rf
-- GNU/Linux User #479299 skype: fabbri.renato _______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
-- GNU/Linux User #479299 skype: fabbri.renato
On Thu, Jul 1, 2010 at 8:46 AM, Renato Fabbri <renato.fabbri@gmail.com> wrote:
just a solution (not all of them)
and the application happen to come up with something like 10k values in the array. don care waiting, but...
then something like ( I am not testing this so you might need to "fix" it and it is ugly) solution = None for r in range(len(alist): for comb in itertools.combinations(alist, r): if sum(comb)==TheValue: solution=comb break break
2010/7/1 Vincent Davis <vincent@vincentdavis.net>:
On Thu, Jul 1, 2010 at 3:17 AM, Renato Fabbri <renato.fabbri@gmail.com> wrote:
hi, i need to find which elements of an array sums up to an specific value
any idea of how to do this?
Not sure if there is a better way but a brut force way would be to
a array([[ 7., 5., 9., 3.], [ 7., 2., 7., 8.], [ 6., 8., 3., 2.]]) alist= a.flatten() alist [7.0, 5.0, 9.0, 3.0, 7.0, 2.0, 7.0, 8.0, 6.0, 8.0, 3.0, 2.0] asolution = [] for r in range(len(alist): for comb in itertools.combinations(alist, r): if sum(comb)==TheValue: asolution.append(comb)
Now just find the comb values in the array.
Like I said kinda brute force. Also depends if you want all solutions or a solution.
Vincent
best, rf
-- GNU/Linux User #479299 skype: fabbri.renato _______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
-- GNU/Linux User #479299 skype: fabbri.renato _______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
to, 2010-07-01 kello 11:46 -0300, Renato Fabbri kirjoitti:
just a solution (not all of them)
and the application happen to come up with something like 10k values in the array. don care waiting, but...
As said, the problem is a well-known one, and it's not really Python or Numpy-specific, so slightly off-topic for this list. Numpy and Scipy don't ship pre-made algorithms for solving these. But anyway, you'll probably find that the brute force algorithm (e.g. the one from Vincent) takes exponential time (and exp(10000) is a big number). So you need to do something more clever. First stop, Wikipedia, http://en.wikipedia.org/wiki/Knapsack_problem http://en.wikipedia.org/wiki/Subset_sum_problem and if you are looking for pre-cooked solutions, second stop stackoverflow, http://stackoverflow.com/search?q=subset+sum+problem Some search words you might want to try on Google: http://www.google.com/search?q=subset%20sum%20dynamic%20programming Generic advice only this time, sorry; I don't have pre-made code for solving this at hand, but hopefully the above links give some pointers for what to do. -- Pauli Virtanen
participants (3)
-
Pauli Virtanen -
Renato Fabbri -
Vincent Davis