import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.ArrayList;

public class determin {
	/*
	 * union and intersection of sets
	 */
   public Set<Integer> union(Set<Integer> list1, Set<Integer> list2) {
        Set<Integer> set = new HashSet<Integer>();

        set.addAll(list1);
        set.addAll(list2);

        return set;
    }

   public Set<Integer> intersection(Set<Integer> list1, Set<Integer> list2) {
       Set<Integer> set = new HashSet<Integer>();

        for (Integer t : list1) {
            if(list2.contains(t)) {
                set.add(t);
            }
        }

        return set;
    }
   
   public Set<Set<Integer>> UNION(Set<Set<Integer>> list1, Set<Set<Integer>> list2) {
       Set<Set<Integer>> set = new HashSet<Set<Integer>>();

       set.addAll(list1);
       set.addAll(list2);

       return set;
    }   
   
   public Set<Integer> difference(Set<Integer> list1, Set<Integer> list2) {
	   Set<Integer> tmp = new HashSet<Integer>(list1);
	    tmp.removeAll(list2);
	    return tmp;
	  }
   
	/*
	 * The hyper-triangle is stored as this format:
	 * <v1, Ep, v2, Eq, v3, Er, v1>, all of them are integers
	 */
	public Set<ArrayList<Integer>> getHyperTriangleIndex(int[][] array)
	{
		Set<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>();
		int i, j, k, p, q, r;//i,k,q are for edge, j,p,r are for vertex

		int v1, e1, v2, e2, v3, e3;
		
		//int[] tempArray = new int[6];
		
		for(i = 0 ; i < array.length - 2; i++)
		{
			for ( j = 0 ; j < array[0].length ; j ++ )
			{
				if(array[i][j] == 1)
				{
					//v1 = j;
					for(k = 0; k < array.length-1; k ++ )
					{
						if((array[k][j] == 1) && (k != i))
						{
							//e1 = k;
							//find the second vertex
							for( p = 0; p < array[0].length; p++)
							{
								if((array[k][p] == 1) && (p != j))
								{
									//v2 = p;
									for(q = 0; q < array.length; q++)
									{
										if((array[q][p]==1) && ( q!= i ) && (q != k))
										{
											//e2 = q;
											for(r = 0 ; r< array[0].length; r++)
											{
												if((array[q][r]==1) && (array[i][r]==1) && (r != j) && (r!= p))
												{
													v1 = j; e1 = k;
													v2 = p; e2 = q;
													v3 = r; e3 = i;
													ArrayList<Integer> tempArray = new ArrayList<Integer>();
													//tempArray.add(0, v1+1);
													//tempArray.add(1, e1+315);
													///tempArray.add(2, v2+1);
													//tempArray.add(3, e2+315);
													//tempArray.add(4, v3+1);
													//tempArray.add(5, e3+315);
													tempArray.add(0, v1);
													tempArray.add(1, e1);
													tempArray.add(2, v2);
													tempArray.add(3, e2);
													tempArray.add(4, v3);
													tempArray.add(5, e3);
													set.add(tempArray);
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
		return set;
	}
	
	/*
	 * The index of star shape is stored as a set of vertices
	 * the vertex which has three or more edges related to it is in the index
	 */
	public Set<Integer> getHyperStarIndex(int[][] array)
	{
		Set<Integer> set = new HashSet<Integer>();
		int i, j, sum;
		for (i = 0; i < array[0].length; i ++)
		{
			sum = 0;
			for (j = 0; j < array.length; j ++)
			{
				if(array[j][i] == 1)
				{
					sum ++;
				}
					
			}
			if(sum > 2)
			{
				set.add(i+1);
			}
		}
		
		return set;
	}
	
	//the set of the permutation results
	private Set<ArrayList<Integer>> permutation = new HashSet<ArrayList<Integer>>();

	/*
	 * fullPermu() implements the permutation of an array, e.g 6 arrays for [1,2,3]:
	 * [[3, 2, 1], [3, 1, 2], [1, 3, 2], [2, 3, 1], [2, 1, 3], [1, 2, 3]]
	 */
	public Set<ArrayList<Integer>> fullPermu(int[] a, int[] b)
	{
		int i, j, k, m, n;
		int[] temp1 = a;
		int[] temp2 = b;
		if(temp2.length == 1)
		{
			ArrayList<Integer> result = new ArrayList<Integer>();
			for(int current: temp1)
				result.add(current);
			result.add(temp2[0]);
			permutation.add(result);
		}
		else for(i = 0; i<temp2.length;i++)
		{
			try{
				ArrayList<Integer> newArray = new ArrayList<Integer>();//prepare for second parameter

				for(j=0; j < i ; j++)
				{
					newArray.add(temp2[j]) ;
				}
				for(k = j+1; k < temp2.length; k++)
				{
					newArray.add(temp2[k]) ;
				}
				int[] tmp1 = new int[temp1.length + 1];

				if(temp1.length == 0)
					tmp1[0] = temp2[i];
				else
				{
					for(n = 0; n < temp1.length; n++)
					{
						tmp1[n] = temp1[n];
					}
					tmp1[n] = temp2[i];
				}

				int[] tmp2 = new int[newArray.size()];
				for(m = 0; m< newArray.size(); m++)
				{
					tmp2[m] = newArray.get(m);
				}
				fullPermu(tmp1, tmp2);
			}catch(IndexOutOfBoundsException e){
		          e.printStackTrace();
			}
		}
		return permutation;
	}

	/*
	 * getAllCombinations & combination give the permutation of m numbers out of n
	 */
	public static ArrayList<ArrayList<Integer>> Permutation(ArrayList<Integer> data, int length)
	{
		ArrayList<ArrayList<Integer>> allCombinations = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> initialCombination = new ArrayList<Integer>();
		combination(allCombinations, data, initialCombination, length);
		return allCombinations;
	}
	private static void combination(ArrayList<ArrayList<Integer>> allCombinations, ArrayList<Integer> data, 
		ArrayList<Integer> initialCombination, int length)
	{
		if(length == 1)
		{
			for(int i=0; i<data.size(); i++)
			{
				ArrayList<Integer> newCombination = new ArrayList<Integer>(initialCombination);
				newCombination.add(data.get(i));
				allCombinations.add(newCombination);
			}
		}

		else if(length > 1)
		{
			for(int i=0; i<data.size(); i++)
			{
				ArrayList<Integer> newCombination = new ArrayList<Integer>(initialCombination);
				newCombination.add(data.get(i));

				ArrayList<Integer> newData = new ArrayList<Integer>(data);
				for(int j=0; j<=i; j++)
					newData.remove(data.get(i));

				combination(allCombinations, newData, newCombination, length - 1);
			}
		}
	}
	
	/*
	 * create a hashtable based on an array, rows are keys, column= 1, add it to value
	 */
	public 	HashMap<Integer, Set<Integer>> array2hash(int[][] hyper)
	{
		HashMap<Integer, Set<Integer>> hash = new HashMap<Integer, Set<Integer>>();
		int m,n;
		for(m = 0; m < hyper.length; m++)
		{
			Set<Integer> s = new HashSet<Integer>();
			for(n = 0; n< hyper[0].length; n++)
			{
				if(hyper[m][n] == 1)
				{
					s.add(n);
				}
			}
			hash.put(m, s);
		}
		return hash;
	}

	
	/*
	 * determine if a hypergraph has a subgraph, ignore label
	 * give each vertex and edge a hash value to match to the hyper graph
	 * if there is a match, this subgraph is in the hypergraph, otherwise, no
	 */
	public Boolean determine(int[][] array, int[][] hyper){
		int m,n,o, p, q, size;
		int flag = 0;//flag should be 1 if there is a match
		int flg = 0;//test whether an edge is in otherV
		Set<ArrayList<Integer>> large = new HashSet<ArrayList<Integer>>();
		//mySet: the triangles got by subgraph
		Set<ArrayList<Integer>> mySet = new HashSet<ArrayList<Integer>>();

		//Set<Integer> others = new HashSet<Integer>(); 
		//unionSet: all vertices related to triangle edges other than the three in index
		Set<Integer> unionSet = new HashSet<Integer>(); 
		/*
		 * create hash table: paper-authors
		 */
		HashMap<Integer, Set<Integer>> paper_au = new HashMap<Integer, Set<Integer>>();
		paper_au = array2hash(hyper);
		ArrayList<Integer> allPaper = new ArrayList<Integer>(paper_au.keySet());
		Set<Integer> allA = new HashSet<Integer>();
		for(Integer currentPaper: allPaper)
		{
			for(Integer author: paper_au.get(currentPaper) )
				allA.add(author);
		}
		ArrayList<Integer> allAuthor = new ArrayList<Integer>(allA);

		
		HashMap<Integer, Integer> realVhash = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> realEhash = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> realOtherVhash = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> realOtherEhash = new HashMap<Integer, Integer>();
		HashMap<Integer, Integer> realZeroVhash = new HashMap<Integer, Integer>();

		large = getHyperTriangleIndex(hyper);
		mySet = getHyperTriangleIndex(array);
		
		if(mySet.size() > 0)
		{
			for(ArrayList<Integer> i: mySet)
			{
				for(ArrayList<Integer> j: large)
				{
					//otherV: vertices not in Triangle index, but related to this triangle
					//otherV , otherE , and zero V are all related to "array", not hyper
					ArrayList<Integer> otherV = new ArrayList<Integer>();
					ArrayList<Integer> otherE = new ArrayList<Integer>();
					//vertices not related to the triangle: test them to the other edges
					ArrayList<Integer> zeroV = new ArrayList<Integer>();

					//hash the sub graph's v and e to the large graph's v and e
					HashMap<Integer, Integer> vhash = new HashMap<Integer, Integer>();
					HashMap<Integer, Integer> ehash = new HashMap<Integer, Integer>();
					HashMap<Integer, Integer> otherVhash = new HashMap<Integer, Integer>();

					//triangle's edges and vertices hash from subgraph to large graph
					for(m = 0; m < 3; m++)
					{
						vhash.put(i.get(m*2), j.get(m*2));
						ehash.put(i.get(m*2+1), j.get(m*2+1));
					}
					
					//11111:pick the vertex not in triangle index(column of a vertex not all 0s)
					for(n = 0; n < array[0].length; n++)
					{
						if(!(vhash.keySet().contains(n)) 
								&& array[i.get(1)][n] + array[i.get(3)][n] + array[i.get(5)][n] > 0 )
						{
							otherV.add(n);
						}
					}
					//22222:pick the edges not in triangle 
					for(n = 0; n < array.length; n++)
					{
						if(!(ehash.keySet().contains(n)) )
						{
							otherE.add(n);
						}
					}
					//get all the related nodes of the three edges in triangle
					unionSet = union(paper_au.get(j.get(1)), 
							union(paper_au.get(j.get(5)),paper_au.get(j.get(3))));

					if(otherV.size() > unionSet.size())//if there are more related vertices: false
					{
						flag = 0;
						continue;
					}
					else
					{
						ArrayList<Integer> permu = new ArrayList<Integer>(unionSet);

						ArrayList<ArrayList<Integer>> permuResults = Permutation(permu,otherV.size());
						ArrayList<ArrayList<Integer>> newPermu = new ArrayList<ArrayList<Integer>>();
						
						//remove 
						for(ArrayList<Integer> currentPermu: permuResults)
						{
							//not including three triangle edges
							if( (!currentPermu.contains(j.get(0)))
									&&(!currentPermu.contains(j.get(2)))
									&&(!currentPermu.contains(j.get(4))) )
							{								
								newPermu.add(currentPermu);
							}
						}
						//Starting test each permutation to the three edges in triangle
						//othersArray.get(i) correspond permuResults[0].get(i)
						for(ArrayList<Integer> currentPermu: newPermu)
						{
							flag = 1;
							//test three triangle edges to other vertices if to triangle vertices are true
							for(o = 0 ; o < otherV.size(); o++)
							{
								//compare subgraph and whole graph
								if((array[i.get(1)][otherV.get(o)] <= hyper[ehash.get(i.get(1))][currentPermu.get(o)])
										&&(array[i.get(3)][otherV.get(o)] <= hyper[ehash.get(i.get(3))][currentPermu.get(o)])
										&&(array[i.get(5)][otherV.get(o)] <= hyper[ehash.get(i.get(5))][currentPermu.get(o)]))
								{
									otherVhash.put(otherV.get(o), currentPermu.get(o));
									flag = flag * 1;
								}
								else
								{
									flag = 0;
									break;
								}
							}
							//test non-triangle edges to all non zero vertices
							if((flag == 1) && (otherE.size() > 0))
							{
								//add the hashtable of "other" edges
								HashMap<Integer, Integer> otherEhash = new HashMap<Integer, Integer>();
								
								ArrayList<ArrayList<Integer>> otherEpermu = Permutation(allPaper,otherE.size());
								ArrayList<ArrayList<Integer>> newOtherEpermu = new ArrayList<ArrayList<Integer>>();
								
								//remove 
								for(ArrayList<Integer> currentEpermu: otherEpermu)
								{
									//not including three triangle edges
									if( (!currentEpermu.contains(j.get(1)))
											&&(!currentEpermu.contains(j.get(3)))
											&&(!currentEpermu.contains(j.get(5))) )
									{								
										newOtherEpermu.add(currentEpermu);
									}
								}
								for(ArrayList<Integer> currentEpermu: newOtherEpermu)
								{
									flag = 1;
									for(p = 0; p< otherE.size(); p++)
									{
										for(q = 0; q < otherV.size(); q++)
										{
											if( (array[otherE.get(p)][i.get(0)] <= hyper[currentEpermu.get(p)][vhash.get(i.get(0))])
												&&(array[otherE.get(p)][i.get(2)] <= hyper[currentEpermu.get(p)][vhash.get(i.get(2))])
												&&(array[otherE.get(p)][i.get(4)] <= hyper[currentEpermu.get(p)][vhash.get(i.get(4))])
												&&(array[otherE.get(p)][otherV.get(q)] <= hyper[currentEpermu.get(p)][otherVhash.get(otherV.get(q))]))
											{
												flag = flag * 1;
											}
											else
											{
												flag = 0;
												break;
											}
										}
										if(flag == 0)
										{
											break;
										}
										else
										{
											otherEhash.put(otherE.get(p), currentEpermu.get(p));
										}
									}
									if(flag == 1)
									{
										realOtherEhash = otherEhash;
										break;
									}
								}

								//DO THE MEMORY RELEASE
								for(size = 0 ; size < otherEpermu.size(); size++)
									otherEpermu.remove(size);
								otherEpermu.trimToSize();
								for(size = 0 ; size < newOtherEpermu.size(); size++)
									newOtherEpermu.remove(size);
								newOtherEpermu.trimToSize();
								
								//test zero edges
								if((flag == 1) && (otherE.size() > 0))
								{
									HashMap<Integer, Integer> zeroVhash = new HashMap<Integer, Integer>();

									for(p = 0; p< array[0].length; p++)
									{
										if( (!vhash.containsKey(p)) && (!otherVhash.containsKey(p)) )
											zeroV.add(p);
									}
									ArrayList<ArrayList<Integer>> zeroVpermu = Permutation(allAuthor,zeroV.size());
									ArrayList<ArrayList<Integer>> newZeroVpermu = new ArrayList<ArrayList<Integer>>();
									//remove triangle vertices and related vertices in the permutation
									for(ArrayList<Integer> currentZpermu: zeroVpermu)
									{
										//not including three triangle vertices and related vertices
										if( (!currentZpermu.contains(j.get(0)))
												&&(!currentZpermu.contains(j.get(2)))
												&&(!currentZpermu.contains(j.get(4))) )
										{							
											flg = 1;
											for(m = 0; m< otherV.size() ; m++)
											{
												if(!currentZpermu.contains(otherVhash.get(otherV.get(m))))
													flg = flg * 1;
												else
												{
													flg = 0;
													break;
												}
									
											}
											if(flg == 1)
												newZeroVpermu.add(currentZpermu);
										}
									}
									for(ArrayList<Integer> currentZpermu: newZeroVpermu)
									{
										flag = 1;
										for(q = 0; q < zeroV.size(); q++)
										{
											for(p = 0; p< otherE.size(); p++)
											{
												if(currentZpermu.get(q) == 13)
													System.out.print(currentZpermu.get(q));
												if(array[otherE.get(p)][zeroV.get(q)] <= hyper[otherEhash.get(otherE.get(p))][currentZpermu.get(q)])
												{
													flag = flag * 1;
												}
												else
												{
													flag = 0;
													break;
												}
											}
											if(flag == 0)
											{
												break;
											}
											else
											{
												zeroVhash.put(zeroV.get(q), currentZpermu.get(q));
											}
										}
										if(flag == 1)
										{
											realZeroVhash = zeroVhash;
											break;
										}
									}
									
								}
								else
								{
									break;
								}
							}
							if(flag == 1)
							{
								break;
							}
						}
						if(flag == 1)
						{
							realOtherVhash = otherVhash;
						}
					}
					if(flag == 1)
					{
						realEhash = ehash;
						realVhash = vhash;
						break;
					}
				}
				if(flag == 1)
				{
					break;
				}
			}

		}
		System.out.println("~~~");
		if(flag == 1)
		{
			System.out.print(realEhash);
			System.out.print(realVhash);
			System.out.print(realOtherEhash);
			System.out.print(realOtherVhash);
			System.out.print(realZeroVhash);
			return true;
		}
		else
			return false;
	}
}