Sheet 07 Task 5 Permutations

/**
 * Implementation of the permutation algorithm for the introduction into
 * programming lecture at the university of Mainz in summer term 2013 exercise
 * sheet 08 task 5.
 * 
 * @author Andr'e Gross, Institute of computer science Mainz
 * 
 */
public class Permutation {

	/**
	 * Verbose flag for debugging purposes
	 */
	private static boolean verbose = false;

	/**
	 * Counts calculated permutations, starts at one, cause the array itself is
	 * the identity permutation
	 */
	private static int count = 1;

	/**
	 * Method to swap the two values in a given array at the given indices
	 * 
	 * @param array
	 *            The array we want to swap two values
	 * @param i
	 *            Index of one element to swap
	 * @param j
	 *            Index of the other element to swap
	 */
	private static void swap(int[] array, int i, int j) {
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}

	/**
	 * Method to calculating all permutations of a given array starting at a
	 * given index (n) back to the first index (0)
	 * 
	 * @param n
	 *            Last value of the subset to be permutated
	 * @param array
	 *            The whole array
	 */
	private static void permutate(int n, int[] array) {
		// A singleton cant get permutated
		if (n == 0)
			return;
		// Permutation of the original array
		permutate(n - 1, array);
		// Permutate the last value through all of its possible permutations
		for (int i = 0; i < n; i++) {
			// count the permutation
			count++;
			// Make a single permutation (a permutation is a combination of
			// swaps)
			swap(array, i, n);
			// Print the permutated array if verbose
			if (verbose) {
				for (int j : array)
					System.out.print(j + ",");
				System.out.println();
			}
			// Permutate the subset of this single permutation
			permutate(n - 1, array);
			// Flip back for the next permutation
			swap(array, i, n);
		}
	}

	/**
	 * Used for debugging and introduction purposes
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		for (int N = 1; N <= 20; N++) {
			// Declare and initialize example array with given size
			int[] testArray = new int[N];
			for (int i = 0; i < testArray.length; i++)
				testArray[i] = i;
			// Call the permutation function to calculate all permutations
			permutate(testArray.length - 1, testArray);
			// Print out the permutations calculated
			System.out.println(count);
			// @see count
			count = 1;
		}
	}

}