January 23rd, 2010, 08:44 AM
generating non repeating permutations of a string
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.
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.
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
Tags for this Thread
Click Here to Expand Forum to Full Width