|Perl: the Markov chain saw|
Disclaimer: noobish advice
I don't understand why it concerns you that the foreach pushes to an array. It's scoped within the subroutine so I don't think it's particularly inefficient.
Because you push twice to the output array, a map is difficult to pull off while preserving the overall flow of information. This probably occcurred to you.
The remaining duplicated code seems natural to me to leave as-is. Wrapping it up in a subroutine seems like overkill; you weren't considering THAT, were you?
I think the function is stunning, BTW. I'm still wrapping my head around it. One may be able to make its workings more obvious, but I can't help you, as I barely follow how it works. Perhaps my self-declared confusion will prompt some of the Enlightened to elaborate.
"I'm not afraid of Al Quaeda. I'm afraid of Al Cracker." -Chris Rock