permutation algorithm

[bigSteve]

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

[Moni]

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

[DrZoidberg]

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.

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

[bigSteve]

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

[Shiro]

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.

[XSquared]

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.

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.

[DrZoidberg]

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.

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

[chrismiceli]

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.

[VirtualAce]

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.