Thanks for the reply Ian,
I've looked in to the bin-packing problem in a general sense now, and I
think my ugly algorithm is actually not too bad (although not too
efficient either!) :)
It was only for a quick job any how.
Thanks again. Tom.
On 24/11/10 16:16, Ian Kelly wrote:
On Wed, Nov 24, 2010 at 8:34 AM, Tom Boland<t...@t0mb.net> wrote:
I'm trying to find a _nice_ way of taking a list of integers, and splitting
them in to lists where the sum of the values does not exceed a threshold.
for instance:
l = [1, 2, 3, 4, 5, 6]
n = 6
nl = [1,2,3], [4], [5], [6]
I don't mind if it's done like playing blackjack/pontoon (the card game
where you try not to exceed a total of 21), ie. going through the list
sequentially, and splitting off the list as soon as the running total would
exceed n. A way of efficiently making all lists as close to n as possible
would be nice however.
You've described the bin-packing problem [1]. It's known to be
NP-hard, so you won't find a solution that is both efficient and
optimal, although the Wikipedia page mentions some polynomial-time
approximate algorithms that you might want to take a look at.
Cheers,
Ian
[1] http://en.wikipedia.org/wiki/Bin_packing_problem
--
http://mail.python.org/mailman/listinfo/python-list
