Turbo C - Permutation Algorithm
You can find the Turbo C source code for the permutation algorithm on this page. The number of combination for a string of N length characters is N!
However we can not simply go with the N! formula always. If we have a string with "ABC", then the number of combinations would be 3! = 6. But if we have a string with "AAA", then the combination would be just 1. You can find the source code for the algorithm which will take care of all the cases.
Related Links:
- Turbo C Permutation Algorithm
- Visual C++ Permutation Algorithm
- C# Permutation Algorithm
- Java Permutation Algorithm
Source Code
#include <stdio.h>
#include <string.h>
void sortchar(char *buffer, int len)
{
int i, j;
for(i = 1; i < len; i++)
{
for(j = 0; j < len - i; j++)
{
if(buffer[j] > buffer[j + 1])
{
char temp = buffer[j];
buffer[j] = buffer[j + 1];
buffer[j + 1] = temp;
}
}
}
}
int NextPermuation(char *p, int len)
{
int i,j,k;
int anchor, count;
char *tempptr;
char ch, newchar;
for(k = len - 1; k > 0; k--)
{
if(p[k - 1] >= p[k])
continue;
else
{
if(k <= len - 3)
{
newchar = p[k-1];
anchor = -1;
for(j = len - 1; j >= k; j--)
{
if(newchar < p[j])
{
anchor = j;
break;
}
}
if(anchor == -1)
return 0;
ch = p[k-1];
p[k-1] = p[anchor];
p[anchor] = ch;
// sort last remaining chars
sortchar(p+k,len - k);
return 1;
}
else
{
tempptr = &p[len-3];
count = 3;
for(i = count - 1; i > 0; i--)
{
if(tempptr[i - 1] >= tempptr[i])
continue;
else
{
if(i <= count - 2)
{
if(tempptr[i+1] > tempptr[i-1])
{
ch = tempptr[i+1];
tempptr[i+1] = tempptr[i];
tempptr[i] = tempptr[i-1];
tempptr[i-1] = ch;
}
else
{
ch = tempptr[i-1];
tempptr[i-1] = tempptr[i];
tempptr[i] = tempptr[i+1];
tempptr[i+1] = ch;
}
}
else
{
ch = tempptr[i];
tempptr[i] = tempptr[i-1];
tempptr[i-1] = ch;
}
return 1;
}
}
return 0;
}
}
}
return 0;
}
int main(int argc, char* argv[])
{
char buf[32];
int ret;
int count = 0;
printf("Enter a string to find permutation:");
scanf("%s", buf);
//sortchar(buf, strlen(buf));
while(1)
{
printf("%s\n", buf);
count++;
ret = NextPermuation(buf, strlen(buf));
if(ret == 0)
break;
}
printf("\n\nCount: %d\n\n\n", count);
return 0;
}
Output
Enter a string to find permutation: 123
123
132
213
231
312
321
Count: 6
Press any key to continue . . .
Enter a string to find permutation: 4123
4123
4132
4213
4231
4312
4321
Count: 6
Press any key to continue . . .
NOTE: If you use the sortchar function after the user input, then output would be changed to give always all possible combinations:
Enter a string to find permutation: 4123
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
Count: 24
Press any key to continue . . .
|
|