
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

January 23rd, 2010, 08:01 AM
#2
Re: generating non repeating permutations of a string
If you didn't want to hold the number of Hs and As equal, the number of possibilities would be 2^n where n is the total number of games, since it would essentially be equivalent to the total number of binary strings of length n (H is 0, A is 1).
That's just FYI, it's not actually useful given your constraint.
The std::next_permutation() algorithm (http://www.cplusplus.com/reference/a...t_permutation/) would probably do what you want. Note that you'll need to start at the lexicographically lowest arrangement, which I think would be AAHH (but verify that) in order to know when you've completed a full cycle through all possibilities.

January 23rd, 2010, 01:30 PM
#3
Re: generating non repeating permutations of a string
Originally Posted by gxkendall
So, does anybody have such an algorithm or have any ideas where to start?
So the number of H and A are equal and the sum is 20 or more?
One approach is to fill an array with the number of wanted H and A and then randomly shuffle it. Each shuffle will generate a valid permutation at random. You can get duplicates but it's highly unlikely because the total population of valid permutations is so big. And you're probably going to store the permutations somewhere which means you can check whether a newly generated permutation is already present.
STL has a shuffling algorithm called random_shuffle you can use.
A compact and very fast way to check for duplicates is to use an unordered_set<int>. (a permutation can easily be encoded as an int).
Last edited by nuzzle; January 23rd, 2010 at 01:53 PM.

January 23rd, 2010, 02:16 PM
#4
Re: generating non repeating permutations of a string
Originally Posted by gxkendall
I have two thoughts on the number of permutations.
Say you have N positions. You want to select N/2 positions and place an H there. In how many ways can you do that? (When the H have been placed the A are just put in the remaining empty positions).
The anwer is that there are N over N/2 ways. That's a binominal coefficient and I checked it out in a math handbook for N=20. It's 184756 so that's how many valid permutations you have with 10 H and 10 A. For N=30 it's 155117520. And for N=4, as in your example, it's 6 indeed.
Last edited by nuzzle; January 24th, 2010 at 01:29 AM.

January 24th, 2010, 03:08 AM
#5
Re: generating non repeating permutations of a string
If I got it right you want to enumerate each home\away sequence once;
well, consider that you can turn the sequence, say, HHHHHAAAAA into any such sequence by moving the kth H in the first seq to the position of the kth H of the second seq; thus you'll need to specify a kuple of decreasing integers m1,...,mk ( with 0<=mj<=k ) representing the position differences.
Conversely, to each such kuple you'll get a unique home\away sequence.
Therefore, your problem is equivalent to enumerating such kuples.
for example, the n=2,4 case
HA (0)
AH (1)
HHAA (0,0)
HAHA (0,1)
AHHA (1,1)
HAAH (0,2)
AHAH (1,2)
AAHH (2,2)
as you can see, you can easily write a function enumerating the n+2 case given the n case, thus solving the problem recursively.
EDIT: sorry, rereading Lindley's post I realized he already posted the solution the STL way ... maybe the function name "next_permutation" is a bit misleading...
Last edited by superbonzo; January 24th, 2010 at 03:24 AM.

January 24th, 2010, 05:53 AM
#6
Re: generating non repeating permutations of a string
Thanks all  I'll give this a go and report back. Might be a couple of weeks.
Cheers
G

January 24th, 2010, 10:07 AM
#7
Re: generating non repeating permutations of a string
Thanks all
Actually, I gave it a go and it works a treat. Here is my program, which generalises the one supplied by Lindley.
// next_permutation
#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char* argv[])
{
int lengthOfString = 20;
int ctr = 0;
char myints[] = {'A','A','A','A','A','A','A','A','A','A','H','H','H','H','H','H','H','H','H','H'};
cout << "The " << lengthOfString << "! possible permutations with " << lengthOfString << " elements:\n";
sort (myints,myints+lengthOfString);
do {
for(int i = 0; i < lengthOfString; i++) cout << myints[i] << " ";
cout << endl;
ctr++;
} while ( next_permutation (myints,myints+lengthOfString) );
cout << "This generated " << ctr << " permutations" << endl;
return 0;
}
The number of permutations can be calculated using (as well as the way nuzzle suggested  which are really the same)
n! / m! / m!
where n is the length of the string and m is half n (i.e. the number of 'H' and 'A').
Using this fomula you get
n= 4, No. of permutations = 6
n=10, No of permutations = 252
n= 20, No. of permutations = 184756 (as identified by nuzzle, above)
n= 22, No. of permutations = 705432
Thnaks again all.
G
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
This a Codeguru.com survey!
