# permutation algorithm

• 10-07-2003
bigSteve
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:(
• 10-07-2003
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 :)
• 10-07-2003
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.

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);```
• 10-15-2003
bigSteve
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:(
• 10-15-2003
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.
• 10-15-2003
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.

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.```
• 10-15-2003
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.

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)
• 10-15-2003
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.
• 10-16-2003
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.