packing algorithm in Ruby

[John Small]

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

 

[Hugh Sasse]

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

 

[Axel Etzold]

-------- Original-Nachricht --------

Datum: Wed, 22 Oct 2008 00:28:37 +0900
Von: John Small <[email protected]>
An: (e-mail address removed)
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

 

[John Small]

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

 

[Calamitas]

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

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]

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

 

[Robert Klemme]

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