Asp Forum - packing algorithm in Ruby

John Small

10/21/2008 3:29:00 PM

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
--
Posted via http://www.ruby-....

6 Answers

Hugh Sasse

10/21/2008 3:48:00 PM

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+prol...

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_...

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

Axel Etzold

10/21/2008 8:03:00 PM

-------- 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/Knapsa...

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-t...

Best regards,

Axel
--
"Feel free" - 10 GB Mailbox, 100 FreeSMS/Monat ...
Jetzt GMX TopMail testen: http://www.gmx.net/de/...

John Small

10/22/2008 6:06:00 AM

> this sounds as if you were looking for a solution of the knapsack
> problem
>
> http://en.wikipedia.org/wiki/Knapsa...
>
> 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-t...
>
> 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

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

Calamitas

10/22/2008 7:21:00 AM

[Note: parts of this message were removed to make it a legal post.]

On Wed, Oct 22, 2008 at 8:05 AM, John Small <jds340@gmail.com> wrote:

> 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.
>

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

John Small

10/22/2008 8:35:00 AM

> 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-....

Robert Klemme

10/22/2008 8:52:00 AM

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/Knapsa...
>>
>> 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

--
remember.guy do |as, often| as.you_can - without end

comp.lang.ruby

packing algorithm in Ruby

John Small

Hugh Sasse

Axel Etzold

John Small

Calamitas

John Small

Robert Klemme

x Login to ForumsZone