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.
Related Links:
- Turbo C Permutation Algorithm
- Visual C++ Permutation Algorithm
- C# Permutation Algorithm
- Java Permutation Algorithm
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 = "";
InputStreamReader input = new InputStreamReader(System.in);
BufferedReader reader = new BufferedReader(input);
try
{
System.out.print("Enter a string to find permutation:");
inpstring = reader.readLine();
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 . . .
|
|