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 "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?


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

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.

Quote:

---

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).

Quote:

---

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.

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 k-uple of decreasing integers m1,...,mk ( with 0<=mj<=k ) representing the position differences.
Conversely, to each such k-uple you'll get a unique home\away sequence.
Therefore, your problem is equivalent to enumerating such k-uples.

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...

Thanks all - I'll give this a go and report back. Might be a couple of weeks.

Cheers

G

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