generating non repeating permutations of a string
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: generating non repeating permutations of a string

  1. #1
    Join Date
    Sep 2006
    Posts
    13

    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

  2. #2
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Fairfax, VA
    Posts
    10,888

    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.

  3. #3
    Join Date
    May 2009
    Posts
    2,413

    Re: generating non repeating permutations of a string

    Quote Originally Posted by gxkendall View Post
    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.

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: generating non repeating permutations of a string

    Quote Originally Posted by gxkendall View Post
    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.

  5. #5
    Join Date
    Oct 2008
    Posts
    1,137

    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 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...
    Last edited by superbonzo; January 24th, 2010 at 03:24 AM.

  6. #6
    Join Date
    Sep 2006
    Posts
    13

    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

  7. #7
    Join Date
    Sep 2006
    Posts
    13

    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center