I have a simple problem in Rails, I need to pack lists of things onto the screen most efficiently. But it's not really a Rails problem it's a simple packing algorithm. Well not really that simple since the general packing algo is NP-complete, but in this case it's cut down to a very simple case. So I'm wondering how to do it in Ruby. In a declarative language like Prolog it's quite simple, but Ruby is mostly procedural so it's a bit fiddly. With all the irrelevant stuff taken out it boils down to this. I have an array of numbers e,g. ar = [26,10,15,18,12] I want to pack those numbers into neat little arrays like this end_result = [[26],[10,15],[17,12]]. So that all the little sub-arrays are roughly the same length. in this case 26,25,29. The reason for I need this is that they're lists which I want to put in three cols on the screen. But I want a fairly general algorithm to do it. Now ruby has some pretty cool stuff for dealing with arrays. Is there a simple cool Ruby way to do this or do I have to use some clunky brute force tactic? Thanks in advance John Small

on 2008-10-21 17:29

on 2008-10-21 17:49

On Wed, 22 Oct 2008, John Small wrote: > I have a simple problem in Rails, I need to pack lists of things onto > the screen most efficiently. But it's not really a Rails problem it's a > simple packing algorithm. Well not really that simple since the general > packing algo is NP-complete, but in this case it's cut down to a very > simple case. So I'm wondering how to do it in Ruby. In a declarative > language like Prolog it's quite simple, but Ruby is mostly procedural so http://eigenclass.org/hiki.rb?tiny+prolog+in+ruby might be one way to solve it then > it's a bit fiddly. > > With all the irrelevant stuff taken out it boils down to this. I have an > array of numbers e,g. ar = [26,10,15,18,12] I want to pack those numbers > into neat little arrays like this end_result = [[26],[10,15],[17,12]]. > So that all the little sub-arrays are roughly the same length. in this You'd need to define "roughly". > case 26,25,29. The reason for I need this is that they're lists which I > want to put in three cols on the screen. But I want a fairly general > algorithm to do it. This looks to me like laying out columns in a newspaper or book so they balance. Maybe http://www.w3.org/People/howcome/TEB/www/hwl_th_10.html helps? > > Now ruby has some pretty cool stuff for dealing with arrays. Is there a > simple cool Ruby way to do this or do I have to use some clunky brute > force tactic? > > Thanks in advance > > John Small Hugh

on 2008-10-21 22:04

-------- Original-Nachricht -------- > Datum: Wed, 22 Oct 2008 00:28:37 +0900 > Von: John Small <jds340@gmail.com> > An: ruby-talk@ruby-lang.org > Betreff: packing algorithm in Ruby > I have a simple problem in Rails, I need to pack lists of things onto > the screen most efficiently. But it's not really a Rails problem it's a > simple packing algorithm. Well not really that simple since the general > packing algo is NP-complete, but in this case it's cut down to a very > simple case. So I'm wondering how to do it in Ruby. In a declarative > language like Prolog it's quite simple, but Ruby is mostly procedural so > it's a bit fiddly. Dear John, this sounds as if you were looking for a solution of the knapsack problem http://en.wikipedia.org/wiki/Knapsack_problem of combinatorial optimization/constraint programming. For the latter, there is gecode and its Ruby bindings, gecoder. Have a look at its square tiling example: http://gecoder.rubyforge.org/examples/square-tiling.html Best regards, Axel

on 2008-10-22 08:07

> this sounds as if you were looking for a solution of the knapsack > problem > > http://en.wikipedia.org/wiki/Knapsack_problem > > of combinatorial optimization/constraint programming. > > For the latter, there is gecode and its Ruby bindings, gecoder. > Have a look at its square tiling example: > > http://gecoder.rubyforge.org/examples/square-tiling.html > > Best regards, > > Axel Axel Thanks for the links, the gecoder one looks very interesting I'll read more on that later on. For the time being I'm close to solving the problem myself using Ruby's array magic coupled with array.in_groups_of() from Rails ActiveSupport. There's an additional constraint on my packing; the lists have to be in order. In essence what I do is break an array of records into groups, sum each group over an integer attribute on the items in the group, if the group sum is within bounds then select that group. I then remove the selected items from the initial list and do the whole thing again with a larger value in .in_groups_of. I'll post up the code when I've got it working so everyone can comment and improve it. John

on 2008-10-22 09:22

On Wed, Oct 22, 2008 at 8:05 AM, John Small <jds340@gmail.com> wrote: > the group sum is within bounds then select that group. I then remove the > selected items from the initial list and do the whole thing again with a > larger value in .in_groups_of. I'll post up the code when I've got it > working so everyone can comment and improve it. > A way to solve your problem goes as follows. First write a method sub_arrays(max) that builds the sub-arrays given a maximal sum. This should be easy enough; just fill up an array until the sum would exceed that maximum in which case you start a new array and fill that one up. Then either you have 3 columns or less, or you have more. Next observe that that maximal sum can never go beneath ar.sum / 3, and that it doesn't need to go above ar.sum / 3 + ar.max. So all you need to do then is to do a binary search on that range for the minimum m for which sub_arrays(m).length <= 3. This algorithm is O(log(ar.max) * ar.length). Peter

on 2008-10-22 10:36

> 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

on 2008-10-22 10:53

2008/10/22 John Small <jds340@gmail.com>: > >> this sounds as if you were looking for a solution of the knapsack >> problem >> >> http://en.wikipedia.org/wiki/Knapsack_problem >> >> of combinatorial optimization/constraint programming. And this is by far not a "simple case" as you said in your first posting. Just the numbers are small. The problem class does not change. > There's an additional constraint on my packing; the lists have to be in > order. In essence what I do is break an array of records into groups, > sum each group over an integer attribute on the items in the group, if > the group sum is within bounds then select that group. I then remove the > selected items from the initial list and do the whole thing again with a > larger value in .in_groups_of. I'll post up the code when I've got it > working so everyone can comment and improve it. I see one theoretical problem here: you have too much dimensions that are allowed to change, namely the number of groups and the sum of one group. Without limiting one of these, even the original array is a proper solution, i.e. you have just one group with a "large" sum. You will need to tackle this by reducing degrees of freedom here otherwise you are unlikely to reach a satisfactory solution. Kind regards robert