import java.util.ArrayList;
/**
 * Heap's algorithm to generate permutations
 *   http://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/
 *   
 *   Modified to return an ArrayList of int arrays
 *
 */
public class HeapAlgo {
   // Java program to print all permutations using
   // Heap's algorithm
   
   //Prints the array
   static void printArr(int a[], int n)
   {
       for (int i=0; i<n; i++)
           System.out.print(a[i] + " ");
       System.out.println();
   }
    
   //Create a collection for the possible permutations of the operands
   ArrayList<IntArray> permList = new ArrayList<IntArray>();
   
   //Generating permutation using Heap Algorithm
   ArrayList<IntArray> heapPermutation(int a[], int size, int n)
   {
      // if size becomes 1 then prints the obtained
      // permutation
      if (size == 1) {
         //printArr(a,n);
         permList.add(new IntArray(a,4));       //Add to ArrayList rather than print
      }
 
      for (int i=0; i<size; i++)
      {
         heapPermutation(a, size-1, n);
    
         // if size is odd, swap first and last
         // element
         if (size % 2 == 1)
         {
             int temp = a[0];
             a[0] = a[size-1];
             a[size-1] = temp;
         }
    
         // If size is even, swap ith and last
         // element
         else
         {
             int temp = a[i];
             a[i] = a[size-1];
             a[size-1] = temp;
         }
      }
      return permList;
   }
}
//     
//    // This code has been contributed by Amit Khandelwal.   }
//