Chris Pollett > Students > Yunxuan
[Bio] [Blog] [Final Step of Shor's and Grover's Algorithms] [Threshold of Error Correction] [Random-kSAT-Generator: Version 1] [Random-kQSAT-Generator: Version 2] [Random-kQSAT-Generator: Version 3] [Antiferromagnetic Heisenberg Model] [Random-kQSAT-Generator: Version 4] [Random-kQSAT-Generator: Version 5] [Random-kQSAT-Generator: Version 6] [Thesis] |
In version 2 and 3, I used a superposition of 8 forbidden vectors for each clause. In this version, version 4, I used 0-8 forbidden vectors for each clause. I did this because this is the only way I will get true null vectors. My overall impression is that the results are pretty good. This is the version with: permutator, no repeating variable, true null vectors w/ 0 energy. This Version has the best freezing point so far: 1.429. But I am not sure that I am actually allowed to zero away some terms in the 8 term clause.
import java.io.*; import static java.lang.Math.*; import java.util.*; public class QSATsolver4 { private int clausesize = 3; private int numvariable = 7; private int numclause = 10; private int numinstances = 50; private ArrayList<Integer> temp2var = new ArrayList <Integer> (); private ArrayList<ArrayList <Integer>> temp5var = new ArrayList <ArrayList<Integer>> (); private ArrayList<String> chain = new ArrayList<String>(); private ArrayList<String> stack = new ArrayList<String>(); private ArrayList<double[][]> piMatrixStack = new ArrayList<double[][]>(); private ArrayList<double[][]> realStack = new ArrayList<double[][]>(); private ArrayList<ArrayList<Double>>temp2= new ArrayList<ArrayList<Double>>(); private ArrayList<ArrayList<ArrayList<Double>>> temp5 = new ArrayList<ArrayList<ArrayList<Double>>>(); private ArrayList<Double>temp = new ArrayList<Double>(); private int netCount = 0; private int counter3=0; private int nullcount=0; private static final double Epsilon = 1e-10; public static void main(String[] args) { QSATsolver4 qs = new QSATsolver4(); qs.generate(); } public void generate(){ double length = 0; int max = (int)pow(2,numvariable); boolean []taken = new boolean [numvariable]; for(int i=0; i<taken.length; i++){ taken[i] = false; } for (int k = 0; k < numinstances; k++) { for (int j = 0; j < numclause; j++) { int v; for(int i = 0; i < clausesize; i++){ v = (int)(Math.random()*numvariable)+1; while(taken[v-1] == true){ v = (int)(Math.random()*numvariable)+1; } taken[v-1] = true; temp2var.add(new Integer(v)); } for(int i = 0; i < taken.length; i++){ taken[i] = false; } int max5 = (int)pow(2,clausesize); for (int i = 0; i < max5; i++){ int hasTerm =(int)(Math.random()*2); if(hasTerm==1) { double real = Math.random(); temp.add(new Double(real)); } else { //nullcount++; double real = 0; temp.add(new Double(real)); } temp2.add(temp); temp = new ArrayList<Double>(); } for (int i = 0; i < temp2.size(); i++){ ArrayList <Double> list = temp2.get(i); for (int g = 0; g < list.size(); g++){ double a = Double.parseDouble(""+list.get(g)); length+=a; } } if(length==0){ System.out.println("here"); length=1; } for (int i = 0; i < temp2.size(); i++){ ArrayList <Double> list = temp2.get(i); for (int g = 0; g < list.size(); g++){ double c = Double.parseDouble(""+list.get(g)); c = c/length; list.remove(g); list.add(g, new Double(c)); } } temp5.add(temp2); //15 items in these temp2 = new ArrayList<ArrayList<Double>>(); temp5var.add(temp2var); temp2var = new ArrayList <Integer> (); //chain = new ArrayList<String>(); length=0; } makeAllClauses(); if(calculateMatrix()){ netCount++; } piMatrixStack = new ArrayList<double[][]>(); realStack = new ArrayList<double[][]>(); temp5var = new ArrayList <ArrayList<Integer>> (); temp5 = new ArrayList<ArrayList<ArrayList<Double>>>(); System.out.println(counter3); //System.out.println(nullcount); counter3=0; } System.out.println("netCount"); System.out.println(netCount); } public boolean calculateMatrix(){ double[][] temp1, temp2; int max = (int)pow(2,numvariable); double [][]sumtemp1 = new double [max][max]; temp1= new double[max][max]; boolean success = false; for(int i=0; i<piMatrixStack.size(); i++){ double[][] one = piMatrixStack.get(i); double[][] two = realStack.get(i); double[][] invone = makeTranspose(one); temp1 = matMultiply(matMultiply(one,two),invone); for(int j = 0; j < temp1.length; j++){ for(int k = 0; k < temp1.length; k++){ sumtemp1[j][k] += temp1[j][k]; } } } boolean [] x= gaussianElimination(sumtemp1,1); success = nullvecExist(x); return success; } public boolean nullvecExist(boolean [] x){ for(int i=0; i<x.length-1; i++){ if(x[i]==true){ //System.out.print(i+" "); counter3++; } } //if(counter3!=0) //return true; if(x[128]==false) return true; /*for(int i=0; i<x.length-1; i++){ if(x[i]==true){ return true; } }*/ return false; } public boolean [] gaussianElimination(double [][]matrix, int type){ //int zerocount = 0; int max = matrix.length; double [] temp; int current = 0; double ratio = 1; boolean found = false; boolean []sol = new boolean [matrix.length+1]; int counter5=0; double [][]matrixcopy= new double[matrix.length][matrix.length]; for(int s=0; s<matrix.length; s++){ for (int t=0; t<matrix.length; t++){ matrixcopy[s][t]=matrix[s][t]; } } //current is the line number you have just fixed. //i is all the line numbers that you are working on still. //the point of this part is to order rows by increasing zero count. /*for(int i=0; i<max; i++){ System.out.print(zeroCount2(matrix[i])+" "); }*/ current=0; int currentCount=0; while(current<max){ for(int i = current; i < max; i++){ if(zeroCount2(matrix[i]) == currentCount){ temp = matrix[i]; matrix[i] = matrix[current]; matrix[current] = temp; current++; } } currentCount++; } //count is the number of zeros in the line you have //just done working on. You stop working and you increase //count when you get to a transition in the number of zeros //in your rows of the matrix. int count = zeroCount2(matrix[0]); while(count<max){ for(int i = count+1; i<max; i++){ int c = zeroCount2(matrix[i]); if(c==count) { ratio = matrix[i][c]/matrix[count][c]; for(int w = 0; w < matrix.length; w++){ matrix[i][w]-=matrix[count][w]*ratio; } } else if(c>count){ break; } } count++; } for(int i=0; i<sol.length; i++){ sol[i]=true; } for(int i=0; i<matrix.length; i++){ sol[zeroCount2(matrix[i])]=false; } /*for(int i=0; i<sol.length-1; i++){ if(sol[i]==true){ //System.out.print(i+" "); counter5++; } } if(counter5==127 && type==2){ System.out.println(sol[128]); for(int i=0; i<matrix.length;i++){ for(int j=0; j<matrix.length; j++){ System.out.print(matrix[i][j]+" "); } System.out.println(); } System.out.println(); System.out.println(); System.out.println(); for(int i=0; i<matrix.length;i++){ for(int j=0; j<matrix.length; j++){ System.out.print(matrixcopy[i][j]+" "); } System.out.println(); } System.exit(0); }*/ return sol; } public int zeroCount2 (double[] vec){ int temp = 0; for(int i = 0; i < vec.length; i++){ if(vec[i]==0){ temp++; } else { break; } } return temp; } public double[][] makeTranspose(double[][] mat){ double [][]temp = new double[mat.length][mat.length]; for(int i = 0; i < mat.length; i++){ for(int j = 0; j<mat[0].length; j++){ temp[i][j] = mat[j][i]; } } return temp; } public void makePi(){ int max = (int)pow(2,numvariable); for(int j = 0; j<max; j++) { String temp3 = Tobinary(j,""); temp3 = reverseString(temp3); if (temp3.length()<numvariable) { temp3 = addZero(temp3, numvariable); } chain.add(temp3); } } public void makeAllClauses(){ int max = (int)pow(2,numvariable); int[] temp1 = new int[clausesize]; int[] temp3 = new int[numvariable-clausesize]; boolean[] taken = new boolean[numvariable]; int[] path = new int[numvariable]; for(int i = 0; i < taken.length; i++){ taken[i] = false; } int max2 = (int)pow(2,clausesize); for(int i = 0; i<temp5var.size(); i++){ ArrayList<Integer> alist = temp5var.get(i); ArrayList<ArrayList<Double>> blist = temp5.get(i); for(int j = 0; j < alist.size(); j++){ int temp2 = (int)(Integer.parseInt(""+alist.get(j)))-1; temp1[j] = temp2; taken[temp2] = true; } int ind = 0; for(int j = 0; j < (numvariable); j++){ if(!taken[j]){ temp3[ind] = j; ind++; } } for(int j = 0; j < taken.length; j++){ taken[j] = false; } for(int j = 0; j < numvariable; j++){ if(j<clausesize){ path[j] = temp1[j]; }else { path[j] = temp3[j-clausesize]; } } double[][] onePi = makeProjector(path, i); piMatrixStack.add(onePi); double [][]oneClause=new double[max][max]; for(int u=0; u<max2; u++){ ArrayList<Double> list3= blist.get(u); double factor= Double.parseDouble(""+list3.get(0)); String str2 = Tobinary(u,""); str2 = reverseString(str2); if (str2.length()<clausesize) { str2 = addZero(str2, clausesize); } String str = getI()+""+reverseString(str2); double[][]one = makeSig(str); for(int l=0; l<one.length; l++){ for(int m=0; m<one.length; m++){ oneClause[l][m]+=factor*one[l][m]; } } } double length=0; for(int p=0; p<oneClause.length; p++){ length+=oneClause[p][p]; } if(length==0){ length=1; } for(int p=0; p<oneClause.length; p++){ oneClause[p][p]=oneClause[p][p]/length; } realStack.add(oneClause); } } public String getI(){ String temp = ""; for(int i = 0; i < numvariable-clausesize; i++){ temp = temp+"I"; } return temp; } public double[][] makeSig (String path){ char next; double a0 = 0; double a1 = 0; double a2 = 0; double a3 = 0; double[][]ul,ur,ll,lr; double [][] orig = new double[2][2]; if(path.charAt(path.length()-1)=='I'){ orig[0][0] = 1; orig[0][1] = 0; orig[1][0] = 0; orig[1][1] = 1; }else { if(path.charAt(path.length()-1)=='0'){ orig[0][0] = 1; orig[0][1] = 0; orig[1][0] = 0; orig[1][1] = 0; }else if(path.charAt(path.length()-1)=='1'){ orig[0][0] = 0; orig[0][1] = 0; orig[1][0] = 0; orig[1][1] = 1; } } for(int i = path.length()-2; i>=0; i--){ next = path.charAt(i); if(next=='I'){ a0 = 1; a1 = 0; a2 = 0; a3 = 1; }else { if(next=='0'){ a0 = 1; a1 = 0; a2 = 0; a3 = 0; }else if(next=='1'){ a0 = 0; a1 = 0; a2 = 0; a3 = 1; } } ul = multiply(a0, clone(orig)); ur = multiply(a1, clone(orig)); ll = multiply(a2, clone(orig)); lr = multiply(a3, clone(orig)); orig = makeLarge(ul, ur, ll, lr); } return orig; } public double[][] multiply(double c, double[][] mat){ double [][] temp = new double[mat.length][mat.length]; for (int i = 0; i<mat.length; i++){ for (int j = 0; j<mat[0].length; j++){ temp[i][j] = c*mat[i][j]; } } return temp; } public double[][] makeLarge(double[][] ul, double[][] ur, double[][] ll, double[][]lr){ double [][] temp = new double[ul.length*2][ul.length*2]; for(int i = 0; i<ul.length; i++){ for(int j = 0; j<ul.length; j++){ temp[i][j] = ul[i][j]; } } for(int i = 0; i<ul.length; i++){ for(int j = 0; j<ul.length; j++){ temp[i][j+ul.length] = ur[i][j]; } } for(int i = 0; i<ul.length; i++){ for(int j = 0; j<ul.length; j++){ temp[i+ul.length][j] = ll[i][j]; } } for(int i = 0; i<ul.length; i++){ for(int j = 0; j<ul.length; j++){ temp[i+ul.length][j+ul.length] = lr[i][j]; } } return temp; } public double[][] clone(double[][] mat){ double [][]temp = new double[mat.length][mat.length]; for (int i = 0; i<mat.length; i++){ for(int j = 0; j<mat[0].length; j++){ temp[i][j] = mat[i][j]; } } return temp; } public double[][] makeProjector(int [] path, int ind) { String str = ""; int zeroCount = 0; int max = (int)pow(2,numvariable); double [] row = new double[max]; double[][] matrix= new double[max][max]; int [] bits= new int [numvariable]; chain = new ArrayList<String>(); makePi(); for(int i=0; i<chain.size(); i++){ String temp1 = chain.get(i); for(int j = 0; j<path.length; j++){ bits[path[numvariable-1-j]]=Integer.parseInt(""+temp1.charAt(j)); } for(int j=bits.length-1; j>=0; j--){ str=str+""+bits[j]; } zeroCount = Todecimal(str); for(int j = 0; j<max; j++){ if(j==zeroCount){ row[j] = 1; }else { row[j] = 0; } } for(int j = 0; j<max; j++){ matrix[i][j] = row[j]; } str = ""; } /*for(int i=0; i<chain.size(); i++){ String temp1 = chain.get(i); for(int j = path.length-1; j>=0; j--){ str = str+temp1.charAt(numvariable-path[j]-1); } zeroCount = Todecimal(str); for(int j = 0; j<max; j++){ if(j==zeroCount){ row[j] = 1; }else { row[j] = 0; } } for(int j = 0; j<max; j++){ matrix[i][j] = row[j]; //if(i==1) //System.out.println(i); } str = ""; }*/ return matrix; } public double[][] matMultiply(double[][]mat1, double[][] mat2){ double[][]prod = new double[mat1.length][mat1.length]; for(int i = 0; i<prod.length; i++){ for(int j = 0; j<prod.length; j++) { prod[i][j] = 0; } } for(int i = 0; i<prod.length; i++){ for(int j = 0; j<prod.length; j++) { for(int k = 0; k<prod.length; k++){ prod[i][j] += mat1[i][k]*mat2[k][j]; } } } return prod; } public int Todecimal (String binary){ int sum=0; for (int i=binary.length()-1; i>=0; i--){ String bit = ""+binary.charAt(i); int bitval = Integer.parseInt(bit); int factor = (int)pow(2, binary.length()-1-i); sum += bitval*factor; } return sum; } public String reverseString(String st){ String temp = ""; for(int i = st.length()-1; i>=0; i--){ temp = temp+st.charAt(i); } return temp; } public String Tobinary(int decimal, String path){ int remainder; if(decimal<=1){ path = path+decimal; return path; } remainder = decimal % 2; path = path+remainder; return Tobinary(decimal>>1, path); } public String addZero(String s, int l){ int b = l-s.length(); for(int i = 0; i<b; i++){ s = "0"+""+s; } return s; } } |