Hopefully, the title will attract the right people.

Given a string, say "HHAA", I want to generate all the permutations, without repetitions, so


or to pharse it slightly differently, if I give you a string length (4 in the above example) generate all possible permutations but where the number of Hs and A's are equal (for those of you that are interested, I am trying to generate all the "Home and Away Patterns" for sports scheduling.

Typically, the string length will be 20, 22, 24, 26 (that sort of magnitude) so I don't want to generate ALL permutations and discard some as there are n! (n factorial) of those and I don't have the time.

I have two thoughts on the number of permutations.

Thought 1:
There are 'n! / (2! * 2!)', so in the above example we have 4! =24 / ( 2 * 2) = 6

So, for a string length of 22, the number to generate is still large at '2.81000182 10^20', but a smaller than 22! = '1.12400073 10^21'.

In this case, I'd have to terminate the program early, and a recursive solution would probably not be suitable.

Thought 2:
As we have n positions, where each position can either be an "H" or "A" then we have 2^n possibilities. This would allow "non-balanced" strings (i.e. number of "H" != number of "A"), but even so 2^11 = 4,194,304 which is tractable (though maybe not recursively).

Anyhow, the maths is a side event. If I have the algorithm, I can get that to do the counting!.

So, does anybody have such an algorithm or have any ideas where to start?


PS: I know there has been quite a bit of discussion of permutations in the group - but nothing seems to fit what I want to do