# Packing algorithm in Ruby

**URL:** <https://www.ruby-forum.com/t/packing-algorithm-in-ruby/151449>\
**Category:** Ruby\
**Created:** [October 21, 2008, 5:29pm UTC](https://www.ruby-forum.com/t/packing-algorithm-in-ruby/151449 "2008-10-21T17:29:58Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![captaffy](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/f04885/32.png) [@captaffy](https://www.ruby-forum.com/u/captaffy)\
**Post date:** [October 21, 2008, 5:29pm UTC](https://www.ruby-forum.com/t/packing-algorithm-in-ruby/151449/1 "2008-10-21T17:29:58Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![captaffy](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/f04885/32.png) [@captaffy](https://www.ruby-forum.com/u/captaffy)\
**Post date:** [October 21, 2008, 5:49pm UTC](https://www.ruby-forum.com/t/packing-algorithm-in-ruby/151449/2 "2008-10-21T17:49:59Z")

</div>

On Wed, 22 Oct 2008, John S. 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](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](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 S.

```
    Hugh

```

---

<div class="post-metadata">

**Author:** ![captaffy](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/f04885/32.png) [@captaffy](https://www.ruby-forum.com/u/captaffy)\
**Post date:** [October 21, 2008, 10:04pm UTC](https://www.ruby-forum.com/t/packing-algorithm-in-ruby/151449/3 "2008-10-21T22:04:40Z")

</div>

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

> Datum: Wed, 22 Oct 2008 00:28:37 +0900  
> Von: John S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
> An: removed\_email\_address@domain.invalid  
> 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

> **[Knapsack problem](https://en.wikipedia.org/wiki/Knapsack_problem)**
>
> The knapsack problem is the following problem in combinatorial optimization:
> It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items. The problem often arises in resource allocation where the decision-makers have to choose from a set of non-divisible projects or tasks under a fixed budget or time constraint, respectively.
> The knapsack problem has been studied for more than a century, with early works dating ...

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](http://gecoder.rubyforge.org/examples/square-tiling.html)

Best regards,

Axel

---

<div class="post-metadata">

**Author:** ![captaffy](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/f04885/32.png) [@captaffy](https://www.ruby-forum.com/u/captaffy)\
**Post date:** [October 22, 2008, 8:07am UTC](https://www.ruby-forum.com/t/packing-algorithm-in-ruby/151449/4 "2008-10-22T08:07:12Z")

</div>

> this sounds as if you were looking for a solution of the knapsack  
> problem
> 
> [Knapsack problem - Wikipedia](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](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

---

<div class="post-metadata">

**Author:** ![captaffy](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/f04885/32.png) [@captaffy](https://www.ruby-forum.com/u/captaffy)\
**Post date:** [October 22, 2008, 9:22am UTC](https://www.ruby-forum.com/t/packing-algorithm-in-ruby/151449/5 "2008-10-22T09:22:56Z")

</div>

On Wed, Oct 22, 2008 at 8:05 AM, John S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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

---

<div class="post-metadata">

**Author:** ![captaffy](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/f04885/32.png) [@captaffy](https://www.ruby-forum.com/u/captaffy)\
**Post date:** [October 22, 2008, 10:36am UTC](https://www.ruby-forum.com/t/packing-algorithm-in-ruby/151449/6 "2008-10-22T10:36:36Z")

</div>

> 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

---

<div class="post-metadata">

**Author:** ![captaffy](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/f04885/32.png) [@captaffy](https://www.ruby-forum.com/u/captaffy)\
**Post date:** [October 22, 2008, 10:53am UTC](https://www.ruby-forum.com/t/packing-algorithm-in-ruby/151449/7 "2008-10-22T10:53:52Z")

</div>

2008/10/22 John S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> > this sounds as if you were looking for a solution of the knapsack  
> > problem
> > 
> > [Knapsack problem - Wikipedia](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