I downloaded String::Combination via ActiveState's PPM, and produced this behavior.

I couldn't find the distro (or the author) on CPAN, but the documentation in the distro's POD seems to indicate that the combinations should be unique:

"From a set of n elements, given an integer k, the algorithm calculates k! * n!/(k!(n-k)!) elements that are all the combinations of k elements from the set of n elements. "

I believe Active's PPM just grabs "whatever will build" from CPAN, and doesn't do any other testing. Perhaps the C library that this module is the XS glue for is making assumptions about the machine it is running on?

Edit: Forgot to mention, you can grab Algorithm::Combinatorics or Math::Combinatorics via PPM. Looking quickly, I'm thinking that they are overkill for your problem, but they are an option at least.