Subj : Re: stacking algorithm
To   : comp.programming
From : Rob Thorpe
Date : Thu Aug 04 2005 07:18 am

nobiscuit wrote:
> Hi,
>
> I need some pointers on a good place to start with an algorithm to
> solve this problem.
>
> Given an arbitrary collection of lines with differing 'lengths' and
> starting points - like this:
>
> ---------   (length = 9, start = 0)
>   ---       (length = 3, start = 2)
> --          etc
> -----------
>     -----
>        -----
> ---
>
>
> And a fixed width 'tray' to place them in, like this:
>
>
> |____________|  (length = 12)
>
>
>
> I need to find a way to 'stack' them in a reasonably efficient way -
> like this:
>
>
> (Gaps in between lines shown for clarity)
>
>  --- -----
>  -- ---	-----
>  ---------
>  -----------
> |____________|  TRAY
>
>
> The code I inherited just checks the starting point of the current line
> being processed against the ending point of the previous line being
> processed and if there is overlap it moves the current line up a level
> in the stack.  This creates situations like this:
>
>           ------
>     ----------
> --------
>
> The requirements team wants something like this instead:
>
>     ----------
> --------  ------
>
>
> I figure this has to be a pretty common problem.  I did a google search
> but didn't find anything.  Can anyone suggest an algorithm which is
> similar or does anyone have any cunning suggestions for an algorithm?

A fairly practical solution might be this:

* Make some sets out of lines, say 10 lines per set
* Exhaustively pack each set
  This means try every combination of packing and take the best
* Stack them one on top of each other.

or this:

* Split lines up into bins according to length, making a histogram.
* Make a some sets of lines, each set of lines contains an amount of
lines from a bin proportional to the amount in the bin.  ie. each set
takes a percentage.
* Now, exhaustively pack each set
* Stack them one on top of each other.

Either way avoids solving the solution exhaustively.

.