
January 23rd, 2010, 07:44 AM
#1
generating non repeating permutations of a string
Hi
Hopefully, the title will attract the right people.
Given a string, say "HHAA", I want to generate all the permutations, without repetitions, so
HHAA
HAHA
AHAH
AAHH
HAAH
AHHA
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 "nonbalanced" 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?
Thanks
G
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
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
