Problem Specification:
This is a project to print all the permutations of a given symmetric group. For instance, given a set {1, 2, 3} the Symmetric Group, S3 , is the group of permutations of the set. Here S3 = {(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 2,1), (3, 1, 2)}
Algorithm
To produce a list all the permutations of a given array of say three, four, five or even n elements.
Let us start with some simple permutations.
1. Consider the set {1, 2, 3}. We could create the permutations of this set as follows:
2. First list the numbers: (1, 2, 3).
3. Now swap the last two numbers: (1, 3, 2). Already we have a new permutation.
4. Swap back the numbers.
5. Create a circular array so that the third number becomes the first in the new array when we shift right. This shift right operation gives us another permutation and the swap we have from before yet another.
6. Another shift right gives us the next permutation, and followed by the swap we have the last.
Code
package permute;
import java.util.Scanner;
import java.lang.Math;
public class Permute {
public static void printArray (int a [ ], int n) {
System.out.print ("(");
System.out.print (" ");
for (int i = 0; i < n; i++ ) {
System.out.print (a [ i ]);
System.out.print (" ");
}
System.out.print (")");
}
public static void permute (int a [ ], int n) {
printArray (a, n);
int i, temp;
//swap last two
temp = a[n - 2];
a[n - 2] = a[n - 1];
a[n - 1] = temp;
printArray (a, n);
// Circlar array
temp = a [ 0 ];
a [ 0 ] = a [n - 1];
a [n - 1] = temp;
printArray (a, n);
//swap last two
temp = a[n - 2];
a[n - 2] = a[n - 1];
a[n - 1] = temp;
printArray (a, n);
// Circlar array
temp = a [ 0 ];
a [ 0 ] = a [n - 1];
a [n - 1] = temp;
printArray (a, n);
//swap last two
temp = a[ n - 2 ];
a[ n - 2 ] = a[ n - 1 ];
a[ n - 1 ] = temp;
printArray (a, n);
System.out.println();
}
public static void main (String args[]) {
System.out.println ("Symmetric Group");
int n; //the order of the Symmetric Group
// Read in the size of the Symmetric Group
Scanner datain = new Scanner (System.in);
System.out.print ("Enter n: "); n = datain.nextInt();
int[] a = new int [ n ];
// Initialising array
for (int i = 0; i < n; i++){
a [ i ] = i + 1;
}
// List the Permutations
permute (a, n);
}
}