permutation algorithm

This is a discussion on permutation algorithm within the C Programming forums, part of the General Programming Boards category; Hi All, Can anyone suggest a simple algorithm for calculating the number of possible permutations of a string containing a ...

  1. #1
    Registered User
    Join Date
    Feb 2002
    Posts
    29

    permutation algorithm

    Hi All,

    Can anyone suggest a simple algorithm for calculating the number of possible permutations of a string containing a known number of different characters and of known length.

    eg nicole has 6 different chars and te string is 6 chars long

    How many possible permutations are possible ??


    Thanks,

    bigSteve
    bigSteve

  2. #2
    Registered User Moni's Avatar
    Join Date
    Oct 2002
    Location
    Dhaka, Bangladesh.
    Posts
    104
    Why don't you try with the STL?
    Though it's for C++ but I use it

    http://msdn.microsoft.com/library/de...t_permutation_(STL_Sample).asp

    I also have C code if you need I can give
    We all are the components of a huge program...... the programmer is always debugging us with His debugger.

  3. #3
    Registered User
    Join Date
    Oct 2003
    Posts
    49
    Are all characters different? In that case the number of characters and the length of the string are always identical.

    If the length is 6 the number of permutations is: 6*5*4*3*2=720.

    Code:
    int i,p,length;
    printf("Enter length of string: ");
    scanf("%d",&length);
    for(i=1, p=1; i<=length; i++) p*=i;
    printf("Number of permutations: %d",p);
    Last edited by DrZoidberg; 10-07-2003 at 12:13 PM.

  4. #4
    Registered User
    Join Date
    Feb 2002
    Posts
    29

    string permutations

    Thanks for the replies ..

    Problem is what about strings like aaaassffffff or abcabcabc
    where a character repeats itself. What algorithms could give the number of possible permutations then ?

    Thanks,

    bigSteve
    bigSteve

  5. #5
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,386
    You could use the indices instead of the characters themselves, every character in your string has its own unique index. For example, if you have the string "aaa", then you can use the indices 0, 1 and 2 of the characters to perform the permutations.

  6. #6
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    When there are n non-repeating letters, the number of possibilities can be defined as n!. All you need to do if there are multiple occurences of letters is, for each letter, sum up the number of occurences, and then divide n! by the factorial.

    Code:
    Example:
    
    aaabb
    
    10 permutations:
    aaabb
    aabab
    abaab
    baaab
    aabba
    ababa
    baaba
    abbaa
    babaa
    bbaaa
    
    1) 5! = 120
    2) Divide 120 by 3!, because there are 3 'a's.
    3) Divide the result by 2!, because there are 2 'b's.
    Last edited by XSquared; 10-15-2003 at 12:49 PM.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  7. #7
    Registered User
    Join Date
    Oct 2003
    Posts
    49
    But a factorial can become quite large.
    13! is already to large to fit into a 32bit variable.
    21! doesn't even fit in 64 bit.

    So you are limited to short strings.

    But you can rise the limit.

    Code:
    #include <stdio.h>
    #include <limits.h>
    #include <stdlib.h>
    
    long permut(short n, short k);
    
    int main() {
    int dl,i,n;
    int *nl;
    long p;
    long m;
    
    printf("\nEnter number of different letters (e.g. aaabb contains 2 different letters): ");
    scanf("%d",&dl);
    nl=malloc(sizeof(int)*dl);
    n=0;
    for(i=0; i<dl; i++) {
       printf("\nEnter number of %d. letter: ",i+1);
       scanf("%d",nl+i);
       n+=nl[i];
    }
    p=1;
    for(i=0; i<dl;i++) {
       m=permut(n, nl[i]);
       if( (LONG_MAX/m) < p) {
                    printf("Result is too big.");
                    exit(0);
                }
       p*=m;
       n-=nl[i];
    }
    printf("\nPermutations: %ld",p);
    }
    
    long permut(short n, short k) {
            long p=1;
            int i,j;
            if(n==k) return 1;
            for(i=1, j=k+1; j<=n; j++, i++) {
                if( (LONG_MAX/j) < p) {
                    printf("Result is too big.");
                    exit(0);
                }
                p*=j;
                p/=i;
            }
            return p;
    }
    this code has no problems with the string:
    "aabbbccddddefff" (15 letters)
    Last edited by DrZoidberg; 10-15-2003 at 02:10 PM.

  8. #8
    Obsessed with C chrismiceli's Avatar
    Join Date
    Jan 2003
    Posts
    501
    they have a programming exercise here at the website like this, and the solution:
    exercise:
    http://www.cprogramming.com/challenges/permute.html
    solution
    http://www.cprogramming.com/challenges/permutesol.html

    it is in c++ but can be easily converted.
    Help populate a c/c++ help irc channel
    server: irc://irc.efnet.net
    channel: #c

  9. #9
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,586
    There are 26 letters in the alphabet - if you cannot reuse the letters and you have 6 available slots the solution is this:

    26*25*24*23*22*21

    Because we will use 1 letter in the first slot, we cannot use that letter in the next slot, so the number of available letters is now 25 and so on and so on.

    If you can re-use the letters then the solution is this:

    26*26*26*26*26*26

    Because all available letters can be used in all available slots.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Permutation algorithm??
    By lris2005 in forum C++ Programming
    Replies: 1
    Last Post: 04-01-2006, 05:51 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Permutation algorithm
    By WarBaboon in forum C++ Programming
    Replies: 6
    Last Post: 03-18-2003, 09:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21