class genPerms
{
	public static void copyAndDelete(int[] source, int[] dest, int i)
	{
		for(int j = 0; j < i; j++)
			dest[j] = source[j];

		for(int j = i+1; j <= dest.length; j++)
			dest[j-1] = source[j];
	}
	
	public static void printArray(int[] data, int n)
	{
		for(int i = 0; i < n; i++)
		{
			System.out.print(data[i]);
			System.out.print(" ");
		}
		
		System.out.println();
	}

	public static void recursiveGenPerms(int n, int[] perms, int m, int[] B)
	{

         	int rest = n - m; // number of elements in B
         	if (rest == 0)
         	{
               		printArray(perms, n);
               		return;
         	}
        	// for each element in B do
        	for(int i = 0; i < rest; i++)
        	{
              		int x = B[i];

              		// Place the element from B into position m+1 in perms
              		perms[m] = x;

              		// Make a temporary copy of B without the element x
			// So this function does both: copy and delete
              		int[] temp = new int[rest-1];
              		copyAndDelete(B, temp, i);

              		// Make the recursive call to generate all permutations
              		// of elements in perms
              		recursiveGenPerms(n, perms, m+1, temp);
         	}
	}


	public static void genPerms(int n)
	{
		// perm has size n, but initially nothing is
		// placed in it
		int[] perms = new int[n];

		int[] B = new int[n];
		
		// Initially B contains everything
		for(int i = 0; i < n; i++)
			B[i] = i+1; 
				
		recursiveGenPerms(n, perms, 0, B);
	}

	public static void main(String[] args)
	{
		genPerms(5);
	}
}