import java.util.*;
public class last_algo {
	@SuppressWarnings("unused")
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [][] arr = {{21,32,10},{50,20,15}};
		adj_matrix(arr);
	}
	public static void adj_matrix(int [][] arr){
		/*
		 Store the WF and DF of everyone who is going up or down
		 */
		ArrayList<Integer> up_WF = new ArrayList<Integer>();
		ArrayList<Integer> up_DF = new ArrayList<Integer>();
		ArrayList<Integer> down_WF = new ArrayList<Integer>();
		ArrayList<Integer> down_DF = new ArrayList<Integer>();
		for (int i = 0; i<arr[0].length;i++) {
			if (arr[0][i]<arr[1][i] ) { //person is going up
				up_WF.add(arr[0][i]);
				up_DF.add(arr[1][i]);
			}else { //person is going down
				down_WF.add(arr[0][i]);
				down_DF.add(arr[1][i]);
			}
		}
		/*
		 Compute the min and max for each WF and DF
		 */

		int min_up_WF = Collections.min(up_WF);
		int max_up_DF = Collections.max(up_DF);
		int max_down_WF = Collections.max(down_WF);
		int min_down_DF = Collections.max(down_DF);

		// Create the complete list of
		ArrayList<Integer> floors = new ArrayList<Integer>();
		floors.add(min_up_WF);
		floors.add(max_up_DF);
		floors.add(max_down_WF);
		floors.add(min_down_DF);
		Collections.sort(floors);
		System.out.println("List of floors : " + floors);
		/*
		 Create the distance Matrix
		 */
		int inf = 99999; // a very large number that is disconnected to the potential costs.  Integer.MAX_VALUE gave issues
		Graph graph = new Graph(floors.size());
		graph.addEdge(floors.indexOf(min_up_WF),floors.indexOf(min_down_DF),Math.abs(min_up_WF-min_down_DF),true);
		graph.addEdge(floors.indexOf(min_up_WF), floors.indexOf(max_up_DF), Math.abs(min_up_WF-max_up_DF),false);
		graph.addEdge(floors.indexOf(min_up_WF), floors.indexOf(max_down_WF), inf, true);
		graph.addEdge(floors.indexOf(max_up_DF), floors.indexOf(max_down_WF), Math.abs(max_up_DF-max_down_WF), true);
		graph.addEdge(floors.indexOf(max_up_DF), floors.indexOf(min_up_WF), inf, false);
		graph.addEdge(floors.indexOf(max_up_DF), floors.indexOf(min_down_DF), inf, true);
		graph.addEdge(floors.indexOf(min_down_DF), floors.indexOf(max_down_WF), inf, false);
		graph.addEdge(floors.indexOf(max_down_WF), floors.indexOf(min_down_DF), Math.abs(max_down_WF-min_down_DF), false);
		graph.print_adjMatrix();
		ArrayList<Integer> sorted_floors = new ArrayList<Integer> (floors); //copy of the original list of floors
		int [][] adj_matrix = graph.getAdjMatrix();
		min_hamiltonian_path(floors,0,adj_matrix,sorted_floors);
		//permutingArray(floors, 0);
	}
	static void min_hamiltonian_path(ArrayList<Integer> arrayList, int element, int [][] adj_matrix, ArrayList<Integer> sorted_floors) {
		for (int i = element; i < arrayList.size(); i++) {
			Collections.swap(arrayList, i, element);
			min_hamiltonian_path(arrayList, element+1, adj_matrix, sorted_floors);
			Collections.swap(arrayList, element, i);
		}
		if (element == arrayList.size() -1 && arrayList.get(0)==sorted_floors.get(0)) {  //recursive base case && starting at the first floor always
			//System.out.println(Arrays.deepToString(arrayList.toArray()));
			helper(arrayList,adj_matrix, sorted_floors);
		}
	}
	// add a helper function
	static void helper(ArrayList<Integer> arrayList, int[][] adj_matrix, ArrayList<Integer> sorted_floors){
		System.out.println("New combination of values");
		int current_cost = 0;
		for (int i = 0; i < arrayList.size() -1; i++){
			current_cost += adj_matrix[sorted_floors.indexOf(arrayList.get(i))][sorted_floors.indexOf(arrayList.get(i+1))];
		}
		System.out.println("The path : " + arrayList + " Has a cost of : " + current_cost);
	}
}

class Graph{ // graph structure
	private static int[][] adjMatrix;
	@SuppressWarnings("unused")
	private int numVertices;
	public Graph(int numVertices){
		this.numVertices = numVertices;
		adjMatrix = new int[numVertices][numVertices];
	}
	public void addEdge (int source, int destination, int distance, boolean reverse) {
		if (reverse == true) { //Two edges between the vertices
			adjMatrix[source][destination] = distance;
			adjMatrix[destination][source] = distance;

		}else { //Directed graph to only one direction
			adjMatrix[source][destination] = distance;
		}
	}
	public void print_adjMatrix(){
		System.out.println("Distance Matrix : " + Arrays.deepToString(adjMatrix));
	}
	public static int [][] getAdjMatrix(){
		return adjMatrix;
	}
}