From: Axel Etzold <AEtzold@...>
Date: 2008-10-22T05:02:36+09:00
Subject: Re: packing algorithm in Ruby


-------- 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 
-- 
"Feel free" - 10 GB Mailbox, 100 FreeSMS/Monat ...
Jetzt GMX TopMail testen: http://www.gmx.net/de/go/topmail