Forum: Ruby packing algorithm in Ruby

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
44a43e7fef8e933e802a7802b4bd3525?d=identicon&s=25 John Small (johnsmall)
on 2008-10-21 17:29
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
457cf540784a12ba2f30e06565a2c189?d=identicon&s=25 Hugh Sasse (Guest)
on 2008-10-21 17:49
(Received via mailing list)
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
D0338c0de4cb3c5c17300396159933d1?d=identicon&s=25 Axel Etzold (Guest)
on 2008-10-21 22:04
(Received via mailing list)
-------- 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
44a43e7fef8e933e802a7802b4bd3525?d=identicon&s=25 John Small (johnsmall)
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
8b97d36adf7291c186c1fcbf9848e0cb?d=identicon&s=25 Calamitas (Guest)
on 2008-10-22 09:22
(Received via mailing list)
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
44a43e7fef8e933e802a7802b4bd3525?d=identicon&s=25 John Small (johnsmall)
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
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2008-10-22 10:53
(Received via mailing list)
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
This topic is locked and can not be replied to.