From: John Small <jds340@...>
Date: 2008-10-22T17:35:06+09:00
Subject: Re: packing algorithm in Ruby


> This algorithm is O(log(ar.max) * ar.length).
> 
> Peter

Luckily my data set is so small I don't need to worry about complexity 
classes. I only need the first part of your solution, which is to step 
through the items in order, filling up sub-arrays to a max size as I go. 
That's sufficient and it's linear in ar.length. However I also thought 
I'd try doing it using Ruby array magic as it's always a good idea to at 
least make an attempt to solve a standard problem in a new way when 
learning a new programming language. The answer is yes it's do-able with 
an intricate collection of each, select, map, sum and so on. But keeping 
things is order is not guaranteed so the brute force simple approach of 
stepping through things filling up containers as I go is they way I 
finally decided on.

John


-- 
Posted via http://www.ruby-forum.com/.