I've run into an odd sorting problem, one that happens all the time in the real world, but I can't think of a determinate solution for it. I think it's an interesting problem and (would be) a useful algorithm to have around. I'm still working on it, but have only managed to come up with solutions that work for certain cases and not others. Perhaps this is because the only thing I learned in statistics (lo, these *many* years ago) is how to sleep with my eyes open...

The problem: how do you arrange two arrays so that the elements of @a are "spread apart" as far as possible by the elements of @b? In other words, given 

sub interleave {
    # PNAMBIC; I'm just making two arrays using length args
    @a = split //, "A" x shift;
    @b = split //, "B" x shift;
    
    # Some magic happens here with @$a and @$b
}

[download]
I need to produce results like these: 
# These are just demonstrator edge cases
interleave(1, 1);
AB
interleave(2, 1);
ABA
###  This is the good stuff
interleave(1, 2);
ABB        # BAB and BBA are also fine
interleave(2, 2);
ABBA
interleave(3, 3);
ABABBA     # ABBABA is also fine
interleave(4, 14);
ABBBBABBBBBABBBBBA  # 'B' strings can be swapped around
interleave(7, 4);
ABABABABAAA

[download]
etc.

Or, to put it a different way - given a barbecue, a bunch of beef cubes, and a number of cherry tomatoes, how would you arrange the skewers in such a way that a) there's a beef 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 beef and all the tomatoes? (NO, that's *not* the real problem... :) As I've said, it's common in the real world - us humans just tend to think of it as "arranging things neatly and fairly", but coming up with an algorithm is something else entirely.

I'd be grateful for any help that you folks can provide.

In reply to Spreading out the elements by Anonymous Monk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.