Java - Permutation Algorithm

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

import java.io.*;

import java.lang.*;

import java.util.*;

class Permutation

{

static public 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;

}

}

}

}

static public boolean NextPermuation(char[] p, int len)

{

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

{

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

continue;

else

{

if (k <= len - 3)

{

char newchar = p[k - 1];

int anchor = -1;

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

{

if (newchar < p[j])

{

anchor = j;

break;

}

}

if (anchor == -1)

return false;

char ch = p[k - 1];

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

p[anchor] = ch;

char[] tbuffer = new char[len-k];

for (int m = 0; m < len - k; m++)

tbuffer[m] = p[k + m];

//sortchar(p+i,len - k);

sortchar(tbuffer, len - k);

for (int n = 0; n < len - k; n++)

p[k + n] = tbuffer[n];

return true;

}

else

{

char[] tempptr = new char[3];

tempptr[0] = p[p.length - 3];

tempptr[1] = p[p.length - 2];

tempptr[2] = p[p.length - 1];

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;

}

p[p.length - 3] = tempptr[0];

p[p.length - 2] = tempptr[1];

p[p.length - 1] = tempptr[2];

return true;

}

}

return false;

}

}

}

return false;

}

public static void main(String args[]) throws Exception

{

String inpstring = "";

try

{

System.out.print("Enter a string to find permutation:");

int len = inpstring.length();

inpstring = inpstring.toUpperCase();

}

catch (Exception e)

{

e.printStackTrace();

}

char[] buffer = inpstring.toCharArray();

// sortchar(buffer, buffer.length); // use it only if you require

int count = 0;

while (true)

{

System.out.println(buffer);

count++;

if (NextPermuation(buffer, buffer.length) == false)

break;

}

System.out.println("\nCount: " + count);

}

}

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