Visual C++ - Permutation Algorithm

You can find the visual 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.

Source Code

#include <stdio.h>

#include <tchar.h>

#include <stdio.h>

#include <tchar.h>

#include <algorithm>

#include <string>

#include <iostream>

/***

1 = 1

2 = 2

3 = 6

4 = 24

5 = 120

6 = 720

7 = 5040

***/

void sortchar(char *buffer, int len)

{

for(int i = 1; i < len; i++)

{

for(int 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;

}

}

}

}

bool NextPermuation(char *p, int len)

{

for(int i = len - 1; i > 0; i--)

{

if(p[i - 1] >= p[i])

continue;

else

{

if(i <= len - 3)

{

char newchar = p[i-1];

int anchor = -1;

for(int j = len - 1; j >= i; j--)

{

if(newchar < p[j])

{

anchor = j;

break;

}

}

if(anchor == -1)

return false;

char ch = p[i-1];

p[i-1] = p[anchor];

p[anchor] = ch;

// sort last remaining chars

sortchar(p+i,len - i);

return true;

}

else

{

char *tempptr = &p[len-3];

int count = 3;

for(int 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])

{

char ch = tempptr[i+1];

tempptr[i+1] = tempptr[i];

tempptr[i] = tempptr[i-1];

tempptr[i-1] = ch;

}

else

{

char ch = tempptr[i-1];

tempptr[i-1] = tempptr[i];

tempptr[i] = tempptr[i+1];

tempptr[i+1] = ch;

}

}

else

{

char ch = tempptr[i];

tempptr[i] = tempptr[i-1];

tempptr[i-1] = ch;

}

return true;

}

}

return false;

}

}

}

}

int _tmain(int argc, _TCHAR* argv[])

{

char buf[32];

std::cout << "Enter a string to find permutation:";

std::cin >> buf;

// sortchar(buf, strlen(buf)); // use it only if you require

int count = 0;

while(1)

{

std::cout << buf << "\n";

count++;

bool bRetVal = NextPermuation(buf, strlen(buf));

if(bRetVal == false)

break;

}

std::cout << "\n\nCount: " << count << "\n";

std::cout << "\n\n";

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 . . .