import java.util.*;

public class Permute {


  public static void main(String[] args) {
    new Permute().doIt(args);
  }


  public void doIt(String[] args) {

    Node s = new Node(1, new Node(2, new Node(3, new Node(4, new Node(5, null)))));

    List<Node> perms = permute(s);

    System.out.println("int[][] permutations = new int[][] {");

    for (Node node: perms) {
      int[] x = Node.toArray(node);
      System.out.print( "{ " + x[0]);
      for (int i = 1; i < x.length; i++) {
	System.out.print( ", " + x[i]);
      }
      System.out.println("},");
    }
    System.out.println("};");
  }


  // this is the "meat"

  List<Node> permute(Node node) {
    List<Node> result = new ArrayList<Node>();
    if (node == null) {
      result.add(null);
    } else {
      for (int x: Node.toArray(node)) {
	Node rest = node.remove(x);
	List<Node> sub = permute(rest);
	for (Node rr: sub) {
	  result.add( new Node(x,rr));
	}
      }
    }
    return result;
  }


  //====================================================================== 
  // utility class
  //====================================================================== 

  static class Node {
    int n = 0;
    Node next = null;
    Node(int n, Node next) {
      this.n = n;
      this.next = next;
    }

    Node remove(int x) {
      if (n == x) return next;
      if (next == null) return this;
      return new Node( n, next.remove(x));
    }
  

    static int length(Node node) {
      int length = 0;
      while (node != null) {
	node = node.next;
	length++;
      }
      return length;
    }


    static int[] toArray(Node node) {
      int n = length(node);
      int[] a = new int[n];
      for (int i = 0; i < n; i++) {
	a[i] = node.n;
	node = node.next;
      }
      return a;
    }
  
  }
  
}