/********************************************************************
 * Matt Kretchmar
 * March 24, 2006
 * RecursionExamples.java
 * This program illustrates how to compute superSum(n) using two 
 * different methods: iterative and recursive.
 ********************************************************************/
import java.util.Scanner;

class AllPermutations
{
    /****************************************************************
     * main
     ****************************************************************/
    public static void main ( String args[] )
    {
        int a[] = new int[4];
        
        for ( int i = 0; i < a.length; i++ )
            a[i] = (i+1);
        
        permute(0,a);
    }
    
    /****************************************************************
     ****************************************************************/
    public static void print ( int a[] )
    {
        for ( int i = 0; i < a.length; i++ )
            System.out.print(a[i] + " ");
        System.out.println();
    }
    
    /****************************************************************
     ****************************************************************/
    public static void permute ( int spot, int a[] )
    {
        if ( spot == a.length ) 
            print(a);
        else
        {
            // how many spots left in array
            int numLeft = a.length - spot;
            for ( int i = spot; i < a.length; i++ )
            {
                // swap spot with i
                int temp = a[i];
                a[i] = a[spot];
                a[spot] = temp;
                
                // make recursive call
                permute(spot+1,a);
                
                // swap back
                temp = a[i];
                a[i] = a[spot];
                a[spot] = temp;
            }
        }
    }
}