[TAG] Max-spread algorithm

[Ben Okopnik]

[ If you're not a programmer or a mathematician, you might want to hit
the 'delete' key right about now. Either that, or risk being bored to
tears. Remember, I warned you! :) ]

As I've just mentioned in my previous post, I've been fiddling with a
"max-spread" algorithm - i.e., if I have two lists, and I want the items
in the first list to be spread as widely as possible (using the items in
the second list as the "padding"), how do I interpolate them?

This can also be stated as follows: given a barbecue, a bunch of pork
cubes, and a number of cherry tomatoes, how would you arrange the
skewers in such a way that a) there's a pork chunk at the beginning and
the end of every skewer, b) each skewer is arranged in as even a manner
as possible, and c) you use up all the pork and all the tomatoes?

I got most of the way to a solution - essentially reinventing the
Bresenham line algorithm [1] (and the wheel... and fire... sheesh. I'm a
_very_ poor mathematician, and a worse statistician), but got scooped by
a fellow Perl monk from the Monastery (perlmonks.org) - really nice work
on his part. I rewrote his script to actually sort arrays rather than
strings and added some guard conditions. Sample output looks like this:

```
ben at Tyr:~/devel/0$ ./skewer 2 2
pork1|tmt1|tmt2|pork2

 ---#00#---

ben at Tyr:~/devel/0$ ./skewer 3 3
pork1|tmt1|tmt2|pork2|tmt3|pork3

 ---#00#0#---

ben at Tyr:~/devel/0$ ./skewer 4 4
pork1|tmt1|tmt2|pork2|tmt3|pork3|tmt4|pork4

 ---#00#0#0#---

ben at Tyr:~/devel/0$ ./skewer 5 4
pork1|tmt1|pork2|tmt2|pork3|tmt3|pork4|tmt4|pork5

 ---#0#0#0#0#---

ben at Tyr:~/devel/0$ ./skewer 7 4
pork1|tmt1|pork2|tmt2|pork3|tmt3|pork4|tmt4|pork5|pork6|pork7

 ---#0#0#0#0###---
'''

Can you reproduce this algorithm? :) I found it a very interesting
exercise, myself.



[1] http://en.wikipedia.org/wiki/Special:Search?search=Bresenham%20line%20algorithm

-- 
* Ben Okopnik * Editor-in-Chief, Linux Gazette * http://LinuxGazette.NET *